目录
❄技巧
🌼爬楼梯
🍔杨辉三角
🌊打家劫舍
🐎完全平方数
🌼零钱兑换
🌼单词拆分
❄技巧
动态规划dp-CSDN博客
👆花 5 分钟快速刷一遍
花 10 分钟浏览一下 线性DP + 背包DP👇
30个题型+代码(冲刺2023蓝桥杯)(下)_挑战程序设计竞赛代码-CSDN博客
🌼爬楼梯
70. 爬楼梯 - 力扣（LeetCode）
/*
dp[i] : 爬到第 i 层的方法数
dp[i] = max(dp[i - 2] + dp[i - 1]) 每次爬 1 或 2 台阶
初始化 dp[0], dp[1]
前到后遍历
*/
class Solution {
public:int climbStairs(int n) {if (n <= 3)return n;int dp[n + 1];dp[0] = 1, dp[1] = 2;// 类似斐波那契for (int i = 2; i < n; ++i)dp[i] = dp[i - 1] + dp[i - 2];return dp[n - 1];}
};🍔杨辉三角
118. 杨辉三角 - 力扣（LeetCode）
/*
dp[i][j] : 第 i 行, 第 j 列的数字
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
观察可得：初始化 dp[i][0], dp[i][i] 左右边界的两条边 = 1
*/
class Solution {
public:vector<vector<int>> generate(int numRows) {vector<vector<int>> ans;int dp[31][31];for (int i = 0; i < numRows; ++i)dp[i][0] = 1, dp[i][i] = 1;ans.push_back({1});if(numRows >= 2)ans.push_back({1, 1});for (int i = 2; i < numRows; ++i) {vector<int> temp;temp.push_back(1);for (int j = 1; j < i; ++j) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];temp.push_back(dp[i][j]);}temp.push_back(1);ans.push_back(temp);}return ans;}
};🌊打家劫舍
198. 打家劫舍 - 力扣（LeetCode）
/*
dp[i] : 只偷前 i 号房屋的最大值, i 从 0 开始
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
初始化 : dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
*/
class Solution {
public:int rob(vector<int>& nums) {int n = nums.size();int dp[101];if (n == 1) return nums[0];if (n == 2) return max(nums[0], nums[1]);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. 完全平方数 - 力扣（LeetCode）
本题完全背包 -- 同 “零钱兑换”
01 背包，每个物品只选 1 个或不选；完全背包，每个物品可以选无数个
时间 O(*
)
/*
dp[i] : 完全平方数的和为 i 的最少数量dp[i] = min(dp[i], dp[i - j*j] + dp[j*j])
即 dp[i] = min(dp[i], dp[i - j*j] + 1)
和为 i 的最小个数 =
min(当前最大个数 dp[i], 和为 i - j*j 的最小个数 + 1)初始化 : dp[i] = 1+1+1+... = i 取最大值
*/
class Solution {
public:int numSquares(int n) {int dp[10001];dp[0] = 0; // 防止 dp[16 - 4*4] 没有for (int i = 1; i <= n; ++i) {dp[i] = i; // 初始化最大值for (int j = 1; j*j <= i; ++j)dp[i] = min(dp[i], dp[i - j*j] + 1);}return dp[n];}
};// 0 1 2 3 4 5 6 7 8 9（初始化）🌼零钱兑换
322. 零钱兑换 - 力扣（LeetCode）
完全背包，同上一题 “完全平方数”
坑
auto x : 数组，不会改变原数组的值，只能遍历，无法改变原数组的值
改变原数组的值直接数组访问 a[i]
时间 O(Sn)，S是 amount，n 是 coins 数量
/*
dp[i] : 金额总和为 i 的最少数量
dp[i] = min(dp[i], dp[i - coins[j]] + 1)
初始化 : dp[0] = 0
*/
class Solution {
public:int coinChange(vector<int>& coins, int amount) {int dp[amount + 10];for (int i = 1; i <= amount; ++i)dp[i] = amount + 1; // 初始化最大值dp[0] = 0; for (int i = 1; i <= amount; ++i)for (int j = 0; j < coins.size(); ++j)if (i >= coins[j])dp[i] = min(dp[i], dp[i - coins[j]] + 1);return dp[amount] == amount + 1 ? -1 : dp[amount];}
};🌼单词拆分
139. 单词拆分 - 力扣（LeetCode）
注意，s.substr(i, j) 表示下标 i 开始，连续的 j 个字符
时间 O(n^2)
/*
dp[i] : s 的前 i 位是否可以用 wordDict 中的字符串表示
dp[i] = dp[j] && hash.find(s.substr(j, i - j)) != hash.end()
解释：前 j 位可以找到，且 [j, i] 能用 wordDict 中字符串表示
初始化 : dp[0] = true
*/
class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {int n = s.size();// 转化为哈希表，便于查找unordered_set<string> hash(wordDict.begin(), wordDict.end());vector<bool> dp(n + 1, false);dp[0] = true;for (int i = 1; i <= n; ++i) // 前 i 位（1开始）for (int j = 0; j < i; ++j) // 左边界if (dp[j] && hash.find(s.substr(j, i-j)) != hash.end() ) {dp[i] = true;break;}return dp[n];}
};