目录

❄技巧

🌼爬楼梯

🍔杨辉三角

🌊打家劫舍

🐎完全平方数

🌼零钱兑换

🌼单词拆分

---

❄技巧

动态规划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];}
};