力扣Hot100系列19（Java）——[动态规划]总结（上）(爬楼梯，杨辉三角，打家劫舍，完全平方数，零钱兑换)

前言

本文记录力扣Hot100里面关于动态规划的五道题，包括常见解法和一些关键步骤理解，也有例子便于大家理解

一、爬楼梯

1.题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

2.代码

classSolution{publicintclimbStairs(intn){// 初始化三个变量，用来滚动计算斐波那契数intp=0,q=0,r=1;// 循环从1到n，逐步计算每一级台阶的方法数for(inti=1;i<=n;++i){p=q;// 把q的值赋给p（保存前前一个状态）此时q是前前一个q=r;// 把r的值赋给q（保存前一个状态）此时r是前一个r=p+q;// 计算当前状态：前两个状态之和（此时r是当前状态）}returnr;// 返回第n级台阶的方法数}}

3.理解

你要爬 n 级台阶，每次只能走1步或2步，问你从楼下到楼顶，一共有多少种不同的走法？

举个最笨的例子：

• 爬1级台阶：只能走1步 → 只有1种走法

• 爬2级台阶：① 走两次1步 ② 直接走2步 → 有2种走法

• 爬3级台阶：想走到第3级，最后一步只能是：
  1.从第2级走1步上来（爬2级有2种走法）
  2.从第1级走2步上来（爬1级有1种走法）
  → 总共 2+1=3种走法

• 爬4级台阶：最后一步要么从3级走1步（3种），要么从2级走2步（2种）→ 3+2=5种
  发现规律了吗？
  爬n级的走法数 = 爬n-1级的走法数 + 爬n-2级的走法数

二、杨辉三角

1.题目

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
动图展示

示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:
输入: numRows = 1
输出: [[1]]

2.代码

classSolution{publicList<List<Integer>>generate(intnumRows){// 1. 定义最终返回的结果：一个“装列表的列表”List<List<Integer>>ret=newArrayList<List<Integer>>();// 2. 外层循环：生成第0行到第numRows-1行（共numRows行）for(inti=0;i<numRows;++i){// 3. 定义当前行的列表，用来存这一行的数字List<Integer>row=newArrayList<Integer>();// 4. 内层循环：生成当前行的第0列到第i列（第i行有i+1个数字）for(intj=0;j<=i;++j){// 5. 规则1：每行第一个（j=0）或最后一个（j=i）数字是1if(j==0||j==i){row.add(1);}else{// 6. 规则2：中间数字 = 上一行第j-1个数字 + 上一行第j个数字row.add(ret.get(i-1).get(j-1)+ret.get(i-1).get(j));}}// 7. 把当前行添加到最终结果里ret.add(row);}// 8. 返回完整的杨辉三角returnret;}}

3.例子

以numRows=5 为例：

第一轮循环（i=0，生成第0行）

• 内层循环 j 从 0 到 0（只循环1次）：
  j=0 → 满足 j0 || j0 → row 添加 1 → row = [1]
• 把 row 加入 ret → ret = [[1]]

第二轮循环（i=1，生成第1行）

• 内层循环 j 从 0 到 1（循环2次）：
  j=0 → 满足条件 → row 添加 1 → row = [1]
  j=1 → 满足 j==i → row 添加 1 → row = [1, 1]
• 把 row 加入 ret → ret = [[1], [1, 1]]

第三轮循环（i=2，生成第2行）

• 内层循环 j 从 0 到 2（循环3次）：
  j=0 → 添加 1 → row = [1]
  j=1 → 不满足条件，取上一行（i-1=1）的 j-1=0 和 j=1 → 1+1=2 → row = [1, 2]
  j=2 → 添加 1 → row = [1, 2, 1]
• 把 row 加入 ret → ret = [[1], [1, 1], [1, 2, 1]]

第四轮循环（i=3，生成第3行）

• 内层循环 j 从 0 到 3（循环4次）：
  j=0 → 添加 1 → row = [1]
  j=1 → 上一行（i-1=2）的 j-1=0 和 j=1 → 1+2=3 → row = [1, 3]
  j=2 → 上一行的 j-1=1 和 j=2 → 2+1=3 → row = [1, 3, 3]
  j=3 → 添加 1 → row = [1, 3, 3, 1]
• 把 row 加入 ret → ret 新增这一行

第五轮循环（i=4，生成第4行）

• 内层循环 j 从 0 到 4（循环5次）：
  j=0 → 1 → row=[1]
  j=1 → 上一行j-1=0 + j=1 → 1+3=4 → row=[1,4]
  j=2 → 上一行j-1=1 + j=2 → 3+3=6 → row=[1,4,6]
  j=3 → 上一行j-1=2 + j=3 → 3+1=4 → row=[1,4,6,4]
  j=4 → 1 → row=[1,4,6,4,1]

把 row 加入 ret → 最终 ret 就是 5 行的杨辉三角

三、打家劫舍

1.题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

2.代码

classSolution{publicintrob(int[]nums){// 1. 获取房屋的总数nintn=nums.length;// 2. 定义dp数组：dp[i]表示偷前i个房屋的最大金额// 数组长度是n+1，因为要用到dp[0]（前0个房屋）到dp[n]（前n个房屋）int[]dp=newint[n+1];// 3. 初始化dp数组的基础值（边界条件）dp[0]=0;// 前0个房屋（没房子可偷），金额为0dp[1]=nums[0];// 前1个房屋（只有第1家），只能偷这一家，金额是nums[0]// 4. 从第2个房屋开始，逐步计算每个dp[i]for(inti=2;i<=n;i++){// 对于第i个房屋，有两种选择，选金额大的那个// 选择1：不偷第i个房屋 → 最大金额 = 偷前i-1个房屋的金额（dp[i-1]）// 选择2：偷第i个房屋 → 不能偷第i-1个，最大金额 = 偷前i-2个的金额 + 第i个房屋的金额（nums[i-1]）// （注意：nums[i-1]对应第i个房屋，因为nums数组下标从0开始，dp数组下标从1开始）dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i-1]);}// 5. dp[n]就是偷前n个房屋的最大金额，也就是最终答案returndp[n];}}

3.例子

以nums = [2,7,9,3,1]为例

1. 初始化基础值
房屋总数 n = nums.length = 5
定义dp数组长度为6（下标 0~5），初始值全 0
边界条件赋值：
dp[0] = 0（前 0 间房屋，无房可偷，金额为 0）
dp[1] = nums[0] = 2（前 1 间房屋，只能偷第 1 间，金额为 2）

2. 循环计算 dp [i]（i 从 2 到 5）
核心公式：dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1])
（不偷第 i 间的最大金额 vs 偷第 i 间的最大金额，取较大值）

• i=2（对应第 2 间房屋，nums [1]=7）：
  dp [2] = Math.max (dp [1]=2, dp [0]+7=0+7=7) = 7
  含义：前 2 间房屋最多偷 7（只偷第 2 间）。

• i=3（对应第 3 间房屋，nums [2]=9）：
  dp [3] = Math.max (dp [2]=7, dp [1]+9=2+9=11) = 11
  含义：前 3 间房屋最多偷 11（偷第 1+3 间）。

• i=4（对应第 4 间房屋，nums [3]=3）：
  dp [4] = Math.max (dp [3]=11, dp [2]+3=7+3=10) = 11
  含义：前 4 间房屋最多偷 11（不偷第 4 间，保留前 3 间的 11）。

• i=5（对应第 5 间房屋，nums [4]=1）：
  dp [5] = Math.max (dp [4]=11, dp [3]+1=11+1=12) = 12
  含义：前 5 间房屋最多偷 12（偷第 1+3+5 间）。

3. 最终结果
返回dp[5] = 12，即偷这 5 间房屋能获得的最大金额为 12。

四、完全平方数

1.题目

给你一个整数 n ，返回和为 n的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
输入：n = 12输出：3
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13输出：2
解释：13 = 4 + 9

2.代码

classSolution{publicintnumSquares(intn){// 1. f[i]表示组成数字i的最少完全平方数个数int[]f=newint[n+1];// 2. 外层循环：从1到n，逐个计算f[1]到f[n]for(inti=1;i<=n;i++){// 3. 初始化当前的最小值为“整数最大值”（表示一开始没找到更小值）intminn=Integer.MAX_VALUE;// 4. 内层循环：遍历所有可能的完全平方数j²，j² ≤ ifor(intj=1;j*j<=i;j++){// 5. 找最小值：f[i - j²] 表示“组成 i-j² 所需的最少个数”，加上当前j²（1个）就是组成i的一种可能minn=Math.min(minn,f[i-j*j]);}// 6. 组成i的最少个数 = 找到的最小值 + 1（加的1就是当前选的那个j²）f[i]=minn+1;}// 7. 返回组成n的最少个数returnf[n];}}

3.例子

以（输入：n = 12）为例

1. 初始化阶段

• 定义f数组，长度为n+1 = 13（下标0~12），初始值全为0
• f[0] = 0（组成数字0需要0个完全平方数，是天然的边界条件）

2. 外层循环计算f[1]到f[12]
对于每个数字i，遍历所有小于等于i的完全平方数j²，f[i] = min(f[i-j²]) + 1（+1是因为选了j²这个数）。

i = 1（计算f[1]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：j=1（1²=1 ≤ 1）
  • f[1 - 1²] = f[0] = 0→minn = min(MAX_VALUE, 0) = 0
• f[1] = 0 + 1 = 1（组成1最少需要1个：1）

i = 2（计算f[2]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：j=1（1²=1 ≤ 2）
  • f[2 - 1²] = f[1] = 1→minn = min(MAX_VALUE, 1) = 1
• f[2] = 1 + 1 = 2（组成2最少需要2个：1+1）

i = 3（计算f[3]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：j=1（1²=1 ≤ 3）
  • f[3 - 1²] = f[2] = 2→minn = min(MAX_VALUE, 2) = 2
• f[3] = 2 + 1 = 3（组成3最少需要3个：1+1+1）

i = 4（计算f[4]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[4-1] = f[3] = 3→minn = min(MAX_VALUE, 3) = 3
  • j=2：2²=4 ≤ 4 →f[4-4] = f[0] = 0→minn = min(3, 0) = 0
• f[4] = 0 + 1 = 1（组成4最少需要1个：4）

i = 5（计算f[5]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[5-1] = f[4] = 1→minn = min(MAX_VALUE, 1) = 1
  • j=2：f[5-4] = f[1] = 1→minn = min(1, 1) = 1
• f[5] = 1 + 1 = 2（组成5最少需要2个：4+1）

i = 6（计算f[6]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[6-1] = f[5] = 2→minn = min(MAX_VALUE, 2) = 2
  • j=2：f[6-4] = f[2] = 2→minn = min(2, 2) = 2
• f[6] = 2 + 1 = 3（组成6最少需要3个：4+1+1）

i = 7（计算f[7]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[7-1] = f[6] = 3→minn = min(MAX_VALUE, 3) = 3
  • j=2：f[7-4] = f[3] = 3→minn = min(3, 3) = 3
• f[7] = 3 + 1 = 4（组成7最少需要4个：4+1+1+1）

i = 8（计算f[8]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[8-1] = f[7] = 4→minn = min(MAX_VALUE, 4) = 4
  • j=2：f[8-4] = f[4] = 1→minn = min(4, 1) = 1
• f[8] = 1 + 1 = 2（组成8最少需要2个：4+4）

i = 9（计算f[9]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[9-1] = f[8] = 2→minn = min(MAX_VALUE, 2) = 2
  • j=2：f[9-4] = f[5] = 2→minn = min(2, 2) = 2
  • j=3：3²=9 ≤ 9 →f[9-9] = f[0] = 0→minn = min(2, 0) = 0
• f[9] = 0 + 1 = 1（组成9最少需要1个：9）

i = 10（计算f[10]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[10-1] = f[9] = 1→minn = min(MAX_VALUE, 1) = 1
  • j=2：f[10-4] = f[6] = 3→minn = min(1, 3) = 1
  • j=3：f[10-9] = f[1] = 1→minn = min(1, 1) = 1
• f[10] = 1 + 1 = 2（组成10最少需要2个：9+1）

i = 11（计算f[11]）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[11-1] = f[10] = 2→minn = min(MAX_VALUE, 2) = 2
  • j=2：f[11-4] = f[7] = 4→minn = min(2, 4) = 2
  • j=3：f[11-9] = f[2] = 2→minn = min(2, 2) = 2
• f[11] = 2 + 1 = 3（组成11最少需要3个：9+1+1）

i = 12（计算f[12]，最终目标）

• 初始化minn = Integer.MAX_VALUE
• 内层循环 j：
  • j=1：f[12-1] = f[11] = 3→minn = min(MAX_VALUE, 3) = 3
  • j=2：f[12-4] = f[8] = 2→minn = min(3, 2) = 2
  • j=3：f[12-9] = f[3] = 3→minn = min(2, 3) = 2
• f[12] = 2 + 1 = 3（组成12最少需要3个：4+4+4）

3. 最终结果
返回f[12] = 3，即组成数字12最少需要3个完全平方数（4+4+4）。

五、零钱兑换

1.题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11输出：3
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

2.代码

publicclassSolution{publicintcoinChange(int[]coins,intamount){// 1. 定义max：作为dp数组的初始值，设为amount+1（因为凑amount最多用amount枚1元硬币，amount+1表示“不可能”）intmax=amount+1;// 2. 定义dp数组：dp[i]表示凑出金额i的最少硬币数，长度为amount+1（覆盖0~amount）int[]dp=newint[amount+1];// 3. 初始化dp数组：所有值先设为max（表示初始时认为凑不出来）Arrays.fill(dp,max);// 4. 边界条件：凑金额0需要0枚硬币dp[0]=0;// 5. 外层循环：从1到amount，逐个计算dp[1]到dp[amount]for(inti=1;i<=amount;i++){// 6. 内层循环：遍历所有硬币面额，尝试用当前硬币凑金额ifor(intj=0;j<coins.length;j++){// 7. 只有当前硬币面额≤i时，才有可能用它凑金额iif(coins[j]<=i){// 8. 核心逻辑：凑i的最少硬币数 = min(当前dp[i], 凑i-coins[j]的最少硬币数 + 1枚当前硬币)dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);}}}// 9. 最终判断：如果dp[amount] > amount，说明凑不出来（因为最多需要amount枚1元），返回-1；否则返回dp[amount]returndp[amount]>amount?-1:dp[amount];}}

3.例子

示例（输入：coins = [1,2,5]，amount = 11）

1. 初始化阶段

• max = amount + 1 = 11 + 1 = 12（12表示“不可能凑出”，因为凑11元最多用11枚1元硬币）
• 定义dp数组，长度为12（下标0~11）
• 用Arrays.fill(dp, 12)初始化，此时dp = [12,12,12,12,12,12,12,12,12,12,12,12]
• 边界条件：dp[0] = 0（凑0元需要0枚硬币），此时dp = [0,12,12,12,12,12,12,12,12,12,12,12]

2. 外层循环计算dp[1]到dp[11]

对于每个金额i，遍历所有硬币面额coins[j]，若coins[j] ≤ i，则dp[i] = min(dp[i], dp[i-coins[j]] + 1)（+1是因为用了当前这枚硬币）。

i = 1（凑1元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 1 →dp[1] = min(12, dp[1-1]+1) = min(12, 0+1) = 1
  • j=1（硬币2）：2 > 1 → 跳过
  • j=2（硬币5）：5 > 1 → 跳过
• 最终dp[1] = 1（凑1元最少1枚：1）

i = 2（凑2元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 2 →dp[2] = min(12, dp[1]+1) = min(12, 1+1) = 2
  • j=1（硬币2）：2 ≤ 2 →dp[2] = min(2, dp[0]+1) = min(2, 0+1) = 1
  • j=2（硬币5）：5 > 2 → 跳过
• 最终dp[2] = 1（凑2元最少1枚：2）

i = 3（凑3元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 3 →dp[3] = min(12, dp[2]+1) = min(12, 1+1) = 2
  • j=1（硬币2）：2 ≤ 3 →dp[3] = min(2, dp[1]+1) = min(2, 1+1) = 2
  • j=2（硬币5）：5 > 3 → 跳过
• 最终dp[3] = 2（凑3元最少2枚：1+2）

i = 4（凑4元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 4 →dp[4] = min(12, dp[3]+1) = min(12, 2+1) = 3
  • j=1（硬币2）：2 ≤ 4 →dp[4] = min(3, dp[2]+1) = min(3, 1+1) = 2
  • j=2（硬币5）：5 > 4 → 跳过
• 最终dp[4] = 2（凑4元最少2枚：2+2）

i = 5（凑5元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 5 →dp[5] = min(12, dp[4]+1) = min(12, 2+1) = 3
  • j=1（硬币2）：2 ≤ 5 →dp[5] = min(3, dp[3]+1) = min(3, 2+1) = 3
  • j=2（硬币5）：5 ≤ 5 →dp[5] = min(3, dp[0]+1) = min(3, 0+1) = 1
• 最终dp[5] = 1（凑5元最少1枚：5）

i = 6（凑6元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 6 →dp[6] = min(12, dp[5]+1) = min(12, 1+1) = 2
  • j=1（硬币2）：2 ≤ 6 →dp[6] = min(2, dp[4]+1) = min(2, 2+1) = 2
  • j=2（硬币5）：5 ≤ 6 →dp[6] = min(2, dp[1]+1) = min(2, 1+1) = 2
• 最终dp[6] = 2（凑6元最少2枚：5+1）

i = 7（凑7元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 7 →dp[7] = min(12, dp[6]+1) = min(12, 2+1) = 3
  • j=1（硬币2）：2 ≤ 7 →dp[7] = min(3, dp[5]+1) = min(3, 1+1) = 2
  • j=2（硬币5）：5 ≤ 7 →dp[7] = min(2, dp[2]+1) = min(2, 1+1) = 2
• 最终dp[7] = 2（凑7元最少2枚：5+2）

i = 8（凑8元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 8 →dp[8] = min(12, dp[7]+1) = min(12, 2+1) = 3
  • j=1（硬币2）：2 ≤ 8 →dp[8] = min(3, dp[6]+1) = min(3, 2+1) = 3
  • j=2（硬币5）：5 ≤ 8 →dp[8] = min(3, dp[3]+1) = min(3, 2+1) = 3
• 最终dp[8] = 3（凑8元最少3枚：5+2+1）

i = 9（凑9元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 9 →dp[9] = min(12, dp[8]+1) = min(12, 3+1) = 4
  • j=1（硬币2）：2 ≤ 9 →dp[9] = min(4, dp[7]+1) = min(4, 2+1) = 3
  • j=2（硬币5）：5 ≤ 9 →dp[9] = min(3, dp[4]+1) = min(3, 2+1) = 3
• 最终dp[9] = 3（凑9元最少3枚：5+2+2）

i = 10（凑10元）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 10 →dp[10] = min(12, dp[9]+1) = min(12, 3+1) = 4
  • j=1（硬币2）：2 ≤ 10 →dp[10] = min(4, dp[8]+1) = min(4, 3+1) = 4
  • j=2（硬币5）：5 ≤ 10 →dp[10] = min(4, dp[5]+1) = min(4, 1+1) = 2
• 最终dp[10] = 2（凑10元最少2枚：5+5）

i = 11（凑11元，最终目标）

• 内层循环遍历硬币：
  • j=0（硬币1）：1 ≤ 11 →dp[11] = min(12, dp[10]+1) = min(12, 2+1) = 3
  • j=1（硬币2）：2 ≤ 11 →dp[11] = min(3, dp[9]+1) = min(3, 3+1) = 3
  • j=2（硬币5）：5 ≤ 11 →dp[11] = min(3, dp[6]+1) = min(3, 2+1) = 3
• 最终dp[11] = 3（凑11元最少3枚：5+5+1）

3. 最终结果判断
dp[11] = 3≤ 11，因此返回3。即凑11元最少需要3枚硬币（5+5+1）。

如果本篇文章对您有帮助，可以点赞，收藏或评论哦！！！关注主包不迷路，让我们一起向前进步吧！！