动态规划
70. 爬楼梯
假设你正在爬楼梯。需要 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 阶
提示：
1 <= n <= 45
动态规划，结构固定
动规五部曲
- 定义：明确数组下标含义以及数组元素含义
- 定式：明确递归公式
- 定初值：确定递归共识初始值
- 定序：确定遍历顺序
- 定中值：举例推导数组（Debug 用）
class Solution {
public:
int climbStairs(int n) {
// 一定要写，虽然没有递归，但是要提前返回，否则 for 循环不会执行，还可能出现下标越界
if(n < 2) return n;
// 1. 定义：明确数组下标含义以及数组元素含义
vector<int> dp(n+1); // dp[i]表示爬到第i层的方法数
// 2. 定式：明确递归公式
// 爬到第i层的方法数等于爬到第i-1层的方法数加上爬到第i-2层的方法数
// 即 dp[i] = dp[i-1] + dp[i-2]
// 3. 定初值：确定递归共识初始值
dp[1] = 1; // 爬到第1层只有1种方法
dp[2] = 2; // 爬到第2层有2种方法
// 4. 定序：确定遍历顺序
// 由于要计算的是dp[n]，所以需要从小到大遍历
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
};
118. 杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
1 <= numRows <= 30
class Solution {
public:
vector<vector<int>> generate(int numRows) {
// 定义：triangle是一个二维数组，表示杨辉三角形
// 数组的行数为numRows
vector<vector<int>> triangle(numRows);
for(int i = 0; i < numRows; i++) {
// 定义：杨辉三角形中第i行的元素个数为i+1
triangle[i].resize(i + 1);
// 定初值：杨辉三角形中每一行的第一个元素均为1
triangle[i][0] = 1;
// 定初值：杨辉三角形中每一行的最后一个元素均为1
triangle[i][i] = 1;
for(int j = 1; j < i; j++) {
// 定式：杨辉三角形中除了第一个和最后一个元素外，
// 其余元素等于上一行中对应位置元素和前一个位置元素之和
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j];
}
}
return triangle;
}
};
198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 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 。
提示：
1 <= nums.length <= 1000 <= nums[i] <= 400
// 1. 定义：dp[i] 表示偷窃前 i 间房屋能够获取的最大金额
// 2. 定式：dp[i] = max(dp[i-1], dp[i-2]+nums[i])
// 当前房屋 i 可以选择偷窃或者不偷窃
// 如果偷窃房屋 i，则最大金额为 dp[i-2]+nums[i]
// 如果不偷窃房屋 i，则最大金额为 dp[i-1]
// 3. 定初值：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
// 只有一间房屋时只能偷窃该房屋，两间房屋时偷窃金额为较大的一间
// 4. 定序：从小到大遍历
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
} else if (n == 1) {
return nums[0];
} else if (n == 2) {
return max(nums[0], nums[1]);
}
vector<int> dp(n, 0);
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; i++) {
dp[i] = max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[n-1];
}
};
279. 完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
提示：
1 <= n <= 104
特殊动态规划：01 背包
相较于一般动态规划，模板性更强
- 判断问题为 01 背包问题：背包容量有限，每个物品只能选择取或不取，目标是在限定背包容量的情况下，选择物品使得总价值最大化。
- 识别物品和背包
- 明确嵌套 for 循环顺序
- 套用 01 背包模板
class Solution {
// 数作物品，和作背包
// 求最少数量 → 非组合非排列 → 复用 01 背包 → 外物品，内背包
public:
int numSquares(int n) {
// dp[容量]
// min 非零下标取 INT_MAX，零下标取 0
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for(int i = 1; i * i <= n; i++){ // 外物品
for(int j = i * i; j <= n; j++){
dp[j] = min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
};
322. 零钱兑换
给你一个整数数组 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
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
class Solution {
public:
// 数作物品，和作背包
// 硬币任取 → 完全背包 → 内正序
// 最小个数 → 非组合非排列 → 复用 01 背包嵌套顺序：外物品，内背包
int coinChange(vector<int>& coins, int amount) {
// dp[容量]
// 取最值，min 非零下标取 INT_MAX，零下标取 0
vector<int> dp(amount + 1, INT_MAX); // 能取 amount
dp[0] = 0; //凑 0 金额，不用硬币，故为 0
for(int i = 0; i < coins.size(); i++){//外物品，内背包
for(int j = coins[i]; j <= amount; j++){
if(dp[j-coins[i]] != INT_MAX){
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
}
if(dp[amount] == INT_MAX) return -1;
return dp[amount];
}
};