LeetCode 热题100之 动态规划1
对于动态规划的问题，解题步骤有以下几部(总结为动态规划五部曲：参考代码随想录动态规划
- 确定dp数组以及下标的含义；
- 确定递推公式；
- dp数组如何初始化；
- 确定遍历顺序；
- 举例推导dp数组
下面的解题思路分析都将从以上动规五部曲展开。
1.爬楼梯
思路分析：动规五部曲
- dp[i]:达到i阶楼梯有i种方法；
- 递推公式;由于当前状态可以由前一种状态走一步到达也可以由前两的状态走两步到达，所以dp[i] = dp[i - 1] + dp[i - 2];
- 初始化：题目中n是正整数，所以初始化：dp[1] = 1,dp[2] = 2即可；
- 遍历顺序：因为要保证计算的时候所用的dp[i-1]和dp[i-2]是更新后的，所以要从前往后遍历；
- 打印dp数组（debug）：1，2，3，5，8…
具体实现代码（详解版）：
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 1,0);
if(n == 1) return 1;
if(n == 2) return 2;
dp[1] = 1,dp[2] = 2;//初始化
for(int i = 3; i <= n ; i ++){
dp[i] = dp[i - 1] + dp[i - 2];//递推公式
}
return dp[n];
}
};
当然，实际上，我们只关心 dp[i-1] 和 dp[i-2]，因此可以将数组的空间复杂度从 O(n) 降到 O(1)，使用两个变量来存储最近的两个结果。
class Solution {
public:
int climbStairs(int n) {
int p = 0 ,q = 0 ,r = 1;
for(int i = 1 ; i <= n ; i ++){
p = q;
q = r;
r = p + q;
}
return r;
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
2.杨辉三角
思路分析：动规五部曲
- dp数组：dp[i][j]表示杨辉三角第i+1行第j+1列的元素。其中i从0-numRows，j从0~i
- 递推公式：每行的第一个和最后一个元素是 1，其他元素是上一行相邻两个元素之和。所以递推公式为dp[i][j] = dp[i - 1][j] +dp[i - 1][j - 1]；
- 初始化当前行：dp[i][0] = 1,dp[i][i] = 1;
- 遍历顺序：由于是从上往下依次填充元素，所以应该从第0行从前往后遍历；
- 举例推导dp数组
[
[1],
[1, 1],
[1, 2, 1],
[1, 3, 3, 1],
[1, 4, 6, 4, 1]
]
具体实现代码（详解版）：
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> dp(numRows);
for(int i = 0 ; i < numRows ; i ++){
//初始化当前行
dp[i].resize(i + 1);
dp[i][0] = dp[i][i] = 1;
//计算中间元素：上一行相邻元素之和
for(int j = 1 ; j < i ; j ++){
dp[i][j] = dp[i - 1][j] +dp[i - 1][j - 1];//递推公式
}
}
return dp;
}
};
- 时间复杂度： O ( n u m R o w s 2 ) O(numRows^2) O(numRows2)
- 空间复杂度： O ( n u m R o w s 2 ) O(numRows^2) O(numRows2)，存储杨辉三角的所有元素
3.打家劫舍
思路分析：动归五部曲
- dp[i]：表示抢劫到第i家的最大金额；
- 递推公式：这道题目可以分为两种情况
- 不抢第i家，则此时最大金额为dp[i - 1];
- 抢第i家，则此时最带金额为dp[i - 2] + nums[i],即加上 i 家的金额和不抢相邻的 i-1 家的最大金额；
- 最终递推公式：d[i] = max(dp[i - 1],dp[i - 2] + nums[i]);
- 初始化：dp[0]=nums[0],这是直接抢劫第一家；dp[1] = max(nums[0],nums[1]),是取第一家和第二家中较大的金额，因为你不能同时抢劫第一家和第二家。
- 遍历顺序：从前往后，因为后面的金额与前面的金额有关系，且确保是计算过的值参与后续的更新；
- 打印DP数组：可以debug
具体实现代码（详解版）：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size(); // 获取nums数组的大小
vector<int> dp(n); // 创建一个dp数组，长度为n，用来保存到每个位置的最大抢劫金额
// 边界条件：
if (n == 0) return 0; // 如果数组为空，返回0
if (n == 1) return nums[0]; // 如果只有一个房子，直接返回它的金额
// 初始化前两个位置的dp值
dp[0] = nums[0]; // 第一个房子的最大抢劫金额就是nums[0]
dp[1] = max(nums[0], nums[1]); // 第二个房子的最大抢劫金额是nums[0]和nums[1]中的较大值
// 动态规划状态转移：从第3个房子开始计算
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]); // 选择是否抢劫第i个房子
}
// 返回最大抢劫金额，即最后一个房子对应的dp值
return dp[n - 1];
}
};
其实我们只需要记录 dp[i-1] 和 dp[i-2]，而不需要完整的 dp 数组。我们可以将 dp[i-1] 和 dp[i-2] 分别存储在两个变量中，从而不再需要 dp 数组：
具体实现代码（详解版）：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
// 初始化：first代表dp[i-2]，second代表dp[i-1]
int first = nums[0]; // dp[0]，即第一个房子可以抢到的金额
int second = max(nums[0], nums[1]); // dp[1]，即第二个房子可以抢到的最大金额
// 从第3个房子开始，更新状态
for (int i = 2; i < n; i++) {
int current = max(second, first + nums[i]); // 当前房子的最大抢劫金额
first = second; // 更新dp[i-2]
second = current; // 更新dp[i-1]
}
return second; // 最终返回second，即最大抢劫金额
}
};
- 时间复杂度：O(n)
- 空间复杂度：O(1)
4.完全平方数
思路分析：动规五部曲
- dp[i]:表示和为i的最少完全平方数的个数
- 递推公式：
- 完全平方数的特点是：如果一个数可以被表示为若干个完全平方数之和，那么它的最小完全平方数的个数应该是通过某种方式组合这些完全平方数的最小数量。
- 假设我们已经知道 dp[i - j^2]，其中 j 是一个整数，表示一个完全平方数。那么 dp[i] 就可以通过 dp[i - j^2] + 1 来更新，表示通过加上一个完全平方数 j^2 来达到总和 i。
- 那么递推公式就是：dp[i] = min(dp[i], dp[i - j^2] + 1),其中，j^2 是小于等于 i 的所有完全平方数。
- 初始化：dp[0] = 0;表示和为0的最小数量为0
- 遍历顺序：
- 外层循环遍历所有 i 从 1 到 n。
- 内层循环遍历所有可能的完全平方数 j^2（即 j 从 1 开始，直到 j^2 大于 i）。
- 打印dp数组：debug
具体实现代码（详解版）：
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0; // 0 需要 0 个完全平方数
for (int i = 1; i <= n; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);//递推公式
}
}
return dp[n];
}
};
- 时间复杂度：O(n * sqrt(n))，其中 n 是输入的整数。每个 i 的计算需要遍历所有小于等于 i 的完全平方数，最多进行 sqrt(n) 次操作。
- 空间复杂度：O(n)，我们使用了一个长度为 n+1 的数组来保存状态。
5.零钱兑换
- dp[i]:组成金额为i所需的最少硬币数；
- 递推公式：
- 对于每一个金额 i（从 1 到 amount），你会检查每种硬币面额 coins[j].如果硬币面额 coins[j] 小于或等于当前金额 i，则可以通过 dp[i - coins[j]] 来获得剩余金额的最小硬币数，再加上当前硬币得到新的结果。
- dp[i] = min(dp[i], dp[i - coins[j] + 1)，其中 coins[j] 为当前考虑的硬币面额。
- 初始化：
- dp(amount + 1,amount + 1)；这里初始化为amount + 1很重要，amount + 1是因为最多也就是amount个1相加，再多就不可能了 使用INT_MAX也可以做到，但是一旦遇到 dp[i - coin] + 1 就会导致int范围溢出，需要额外判断，或者使用其他类型比如long long，或者也可以取数据范围外的特殊值，但都取特殊值的了话还不如用这个amount + 1
- dp[0]=0;表示组成金额为0不需要任何硬币；
- 遍历顺序：
- 外层循环遍历所有金额 i 从 1 到 amount；
- 内存循环遍历每个硬币，对每个金额i，我们都要检查每种硬币是否能参与组成该金额（即coins[j] <= i),进而更新dp[i].
- 打印dp数组：debug
具体实现代码（详解版）：
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1,amount + 1);
dp[0] = 0;
for(int i = 1 ; i <= amount ; i ++){
for(int j = 0 ; j < coins.size() ; j ++){
if(coins[j] <= i){//硬币面额不超过当前金额
dp[i] = min(dp[i],dp[i - coins[j]] + 1);
}
}
}
//因为初始化为amount + 1，若没更新就是没找到组合方式，判断即可。
return dp[amount] > amount ? -1 : dp[amount];
}
};
- 时间复杂度：O(amount *m),其中其中 amount 是目标金额，m 是硬币的种类数。外层循环遍历金额 1 到 amount，内层循环遍历所有硬币，导致总的时间复杂度为 O(amount * m)。
- 空间复杂度：O(amount)，我们使用一个长度为 amount + 1 的 dp 数组来保存每个金额所需的最少硬币数。