五部曲(代码随想录)

1.确定 dp 数组以及下标含义
2.确定递推公式
3.确定 dp 数组初始化
4.确定遍历顺序
5.debug

入门题

1.斐波那契数

思路

1.f[i]:第 i 个数的值
2.f[i] = f[i – 1] + f[i – 2]
3.f[0] = 0, f[1] = 1
4.顺序遍历
5.记得特判 n == 0 的时候,因为初始化了 f[1]

class Solution {public:int fib(int n) {if(n == 0) return n;vector<int> f(n + 1);f[0] = 0, f[1] = 1;for(int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];return f[n];}};

2.爬楼梯

思路

每次可以从下面一个台阶或者下面两个台阶处上来

1.f[i]:爬到第 i 阶楼梯有多少种方法
2.f[i] = f[i – 1] + f[i – 2]
3.f[0] = 1, f[1] = 1
4.顺序遍历

class Solution {public:int climbStairs(int n) {vector<int> f(n + 1);f[0] = 1, f[1] = 1;for(int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];return f[n];}};

3.使用最小花费爬楼梯

思路

可以从 0 或 1 处开始爬楼梯,需要爬到第 n 阶楼梯

1.f[i]:爬到第 i 阶楼梯需要的最小花费
2.f[i] = min(f[i – 1] + cost[i – 1], f[i – 2] + cost[i – 2)
3.f[0] = 0, f[1] = 0
4.顺序遍历

class Solution {public:int minCostClimbingStairs(vector<int>& cost) {int n = cost.size();vector<int> f(n + 1);f[0] = 0, f[1] = 0;for(int i = 2; i <= n; i++){f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);}return f[n];}};

4.不同路径

思路

1.f[i][j]: 走到 (i, j) 总共的路径
2.f[i][j] = f[i – 1][j] + f[i][j – 1]
3.f[i][1] = 1, f[1][i] = 1
4.顺序遍历

class Solution {public:int uniquePaths(int m, int n) {vector<vector<int>> f(n + 1, vector<int>(m + 1));for(int i = 0; i <= n; i++) f[i][1] = 1;for(int i = 0; i <= m; i++) f[1][i] = 1;for(int i = 2; i <= n; i++){for(int j = 2; j <= m; j++){f[i][j] = f[i - 1][j] + f[i][j - 1];}}return f[n][m];}};

5.不同路径 II

思路

1.f[i][j]: 走到 (i, j) 总共的路径
2.f[i][j] = f[i – 1][j] + f[i][j – 1]
3.f[i][0] = 1, f[0][i] = 1, 其他 = 0
4.顺序遍历

class Solution {public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int n = obstacleGrid.size();int m = obstacleGrid[0].size();vector<vector<int>> f(n, vector<int>(m, 0));for(int i = 0; i < n && !obstacleGrid[i][0]; i++) f[i][0] = 1;for(int i = 0; i < m && !obstacleGrid[0][i]; i++) f[0][i] = 1;for(int i = 1; i < n; i++){for(int j = 1; j < m; j++){if(!obstacleGrid[i][j]){f[i][j] = f[i - 1][j] + f[i][j - 1];}}}return f[n - 1][m - 1];}};

6.整数拆分

思路

1.f[i]: 拆数字 i 可得到的最大乘积
2.拆分成 j * (i – j) 或 j * f[i – j],f[i] = max(f[i], max(j * (i – j), j * [i – j]))
3.f[0] = 0, f[1] = 1
4.顺序遍历

class Solution {public:int integerBreak(int n) {vector<int> f(n + 1);f[0] = 0, f[1] = 1;for(int i = 2; i <= n; i++){for(int j = 0; j < i; j++){f[i] = max(f[i], max(j * (i - j), j * f[i - j]));}}return f[n];}};

7.不同的二叉搜索树

思路

dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

1.f[i]: 由 1 到 i 个节点的二叉搜索树个数
2.f[i] += f[j – 1] * f[i – j]
3.f[0] = 1
4.顺序遍历

class Solution {public:int numTrees(int n) {vector<int> f(n + 1);f[0] = 1;for(int i = 1; i <= n; i++){for(int j = 1; j <= i; j++){f[i] += f[j - 1] * f[i - j];}}return f[n];}};

背包问题

1.01背包问题

思路

1.f[i][j]: 前 i 个物品在容量为 j 的情况下的最大价值
2.f[i][j] = max(f[i – 1][j], f[i – 1][j – v[i]] + w[i])
3.全部 = 0
4.顺序遍历

#includeusing namespace std;const int N = 1e3 + 10;int f[N][N], v[N], w[N];int n, m;int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);for(int i = 1; i <= n; i++){for(int j = 0; j <= m; j++){// 不选f[i][j] = f[i - 1][j];// 选if(v[i] <= j) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);}}printf("%d", f[n][m]);return 0;}// 滚动数组优化#includeusing namespace std;const int N = 1e3 + 10;int f[N], v[N], w[N];int n, m;int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d%d", &v[i], &w[i]);for(int i = 1; i <= n; i++){for(int j = m; j >= v[i]; j--){f[j] = max(f[j], f[j - v[i]] + w[i]);}}printf("%d", f[m]);return 0;}

2.分割等和子集

思路

分割成两个等和子集,即找到是否存在和为 sum / 2 的子集,转化为 01 背包,背包容量为 sum / 2

1.f[j]: 背包容量为 i,放入物品后的最大重量
2.f[j] = max(f[j], f[j – nums[i]] + nums[i])
3.全部 = 0
4.倒序遍历

class Solution {public:bool canPartition(vector<int>& nums) {int n = nums.size(), sum = 0;for(int i = 0; i < n; i++) sum += nums[i];if(sum % 2) return false;vector<int> f(10001, 0);for(int i = 0; i < n; i++){for(int j = sum / 2; j >= nums[i]; j--){f[j] = max(f[j], f[j - nums[i]] + nums[i]);if(f[j] == sum / 2) return true;}}return false;}};

3.最后一块石头的重量 II

思路

尽可能分成两堆重量相同,使得相撞后重量最小

1.f[j]: 容量为 j 的背包,最大价值
2.f[j] = max(f[j], f[j – stones[i]] + stones[i])
3.全部 = 0
4.倒序遍历

class Solution {public:int lastStoneWeightII(vector<int>& stones) {int n = stones.size(), sum = 0;for(int i = 0; i < n; i++) sum += stones[i];vector<int> f(1501, 0);for(int i = 0; i < n; i++){for(int j = sum / 2; j >= stones[i]; j--){f[j] = max(f[j], f[j - stones[i]] + stones[i]);}}return (sum - f[sum / 2]) - f[sum / 2];}};

4.目标和

思路

pos – neg = tar 得 pos – (sum – pos) = tar 得 pos = (sum + tar) / 2
转换为背包容量为 pos,有多少种情况装满
无解的情况:pos 为奇数,tar 的绝对值大于 sum
只要搞到 nums[i],凑成 f[j] 就有 f[j – nums[i]] 种方法。
例如:f[j],j 为5,
已经有一个1(nums[i])的话,有 f[4]种方法 凑成 容量为5的背包。
已经有一个2(nums[i])的话,有 f[3]种方法 凑成 容量为5的背包。
已经有一个3(nums[i])的话,有 f[2]中方法 凑成 容量为5的背包
已经有一个4(nums[i])的话,有 f[1]中方法 凑成 容量为5的背包
已经有一个5(nums[i])的话,有 f[0]中方法 凑成 容量为5的背包
那么凑整 f[5] 有多少方法呢,也就是把 所有的 f[j – nums[i]] 累加起来。

1.f[j]:填满 j 背包有多少种情况
2.f[j] += f[j – nums[i]]
3.f[0] = 1,其他 = 0
4.倒序遍历

class Solution {public:int findTargetSumWays(vector<int>& nums, int target) {int n = nums.size(), sum = 0;for(int i = 0; i < n; i++) sum += nums[i];if((sum + target) % 2 || abs(target) > sum) return 0;int pos = (sum + target) / 2;vector<int> f(pos + 1, 0);f[0] = 1;for(int i = 0; i < n; i++){for(int j = pos; j >= nums[i]; j--){f[j] += f[j - nums[i]];}}return f[pos];}};

5.一和零

思路

可以等价为两个 01 背包,一个装 0,一个装 1

1.f[i][j]: 最多有 i 个 0 和 j 个 1 的最长子集大小
2.f[i][j] = max(f[i][j], f[i – zero][j – one] + 1)
3.全部 = 0
4.倒序遍历

class Solution {public:int findMaxForm(vector<string>& strs, int m, int n) {vector<vector<int>> f(m + 1, vector<int>(n + 1, 0));for(auto str : strs){int zero = 0, one = 0;for(int i = 0; i < str.size(); i++){if(str[i] == '0') zero++;else one++;}for(int i = m; i >= zero; i--){for(int j = n; j >= one; j--){f[i][j] = max(f[i][j], f[i - zero][j - one] + 1);}}}return f[m][n];}};

6.完全背包


思路

01 背包是一个物品只能选一个,所有滚动数组要倒序遍历,完全背包则是一个物品可以选无限个,所以滚动数组正序遍历即可,先遍历物品或者背包容量都可以,因为与顺序无关

#includeusing namespace std;const int N = 1e3 + 10;int f[N], v[N], w[N];int n, m;int main(){scanf("%d%d", &n, &m);for(int i = 0; i < n; i++) scanf("%d%d", &v[i], &w[i]);for(int i = 0; i < n; i++){for(int j = v[i]; j <= m; j++){f[j] = max(f[j], f[j - v[i]] + w[i]);}}printf("%d", f[m]);return 0;}

7.零钱兑换 II


思路

先遍历物品,再遍历背包容量是组合数,因为物品顺序是有序的
先遍历背包容量,再遍历物品时排列数,因为物品是无序的

1.f[j]: 容量为 j 的背包有多少种组合情况
2.f[j] += f[j – coins[i]]
3.f[0] = 1,其他 = 0
4.先物品,再背包,顺序遍历

class Solution {public:int change(int amount, vector<int>& coins) {int n = coins.size();vector<int> f(amount + 1, 0);f[0] = 1;// 遍历物品for(int i = 0; i < n; i++){// 遍历背包for(int j = coins[i]; j <= amount; j++){f[j] += f[j - coins[i]];}}return f[amount];}};

8.组合总和 Ⅳ


思路

求的是排列数,那就先遍历背包,再遍历物品,要特判总和大于 INT32_MAX 的情况

1.f[j]: 背包容量为 j 的排列情况数量
2.f[j] += f[j – nums[i]]
3.f[0] = 1,其他 = 0
4.先背包,再物品,顺序遍历

class Solution {public:int combinationSum4(vector<int>& nums, int target) {int n = nums.size();vector<int> f(target + 1, 0);f[0] = 1;for(int j = 0; j <= target; j++){for(int i = 0; i < n; i++){if(nums[i] <= j && f[j] < INT32_MAX - f[j - nums[i]]){f[j] += f[j - nums[i]];}}}return f[target];}};

9.爬楼梯


思路

求的是排列数,先背包,再物品

1.f[j]: 容量为 j 的背包,有多少种排列情况
2.f[j] += f[j – i]
3.f[0] = 1,其他 = 0
4.先背包,再物品,顺序遍历

#includeusing namespace std;const int N = 50;int f[50];int n, m;int main(){scanf("%d%d", &n, &m);f[0] = 1;for(int j = 0; j <= n; j++){for(int i = 1; i <= m; i++){if(j >= i) f[j] += f[j - i];}}printf("%d", f[n]);return 0;}

10.零钱兑换

思路

求的是硬币的最小个数,与顺序无关,不影响硬币的个数,排列组合都可以

1.f[j]: 容量为 j 的背包,物品最少数量
2.f[j] = min(f[j], f[j – nums[i]] + 1)
3.f[0] = 0,其他 = 1e9
4.都可以,顺序遍历

class Solution {public:int coinChange(vector<int>& coins, int amount) {int n = coins.size();vector<int> f(amount + 1, 1e9);f[0] = 0;for(int i = 0; i < n; i++){for(int j = coins[i]; j <= amount; j++){f[j] = min(f[j], f[j - coins[i]] + 1);}}return f[amount] == 1e9 " />-1 : f[amount];}};

11.完全平方数

思路

求的完全平方数的最少数量,与顺序无关,排列组合都可以

1.f[j]:背包容量为 j 的最少物品数
2.f[j] = min(f[j], f[j – i * i] + 1)
3.f[0] = 0,其他 = 1e9
4.都可以,顺序遍历

class Solution {public:int numSquares(int n) {int m = sqrt(n);vector<int> f(n + 1, 1e9);f[0] = 0;for(int i = 1; i <= m; i++){for(int j = i * i; j <= n; j++){f[j] = min(f[j], f[j - i * i] + 1);}}return f[n];}};

12.单词拆分


思路

如果确定 f[i] 是 true,且 [i, j] 这个区间的子串出现在字典里,那么 f[i] 一定是 true
所以递推公式是 if([i, j] 这个区间的子串出现在字典里 && f[i]是true) 那么 dp[j] = true
求的是排列数

1.f[j]: 长度为 j 的字符串是否可以拆分为字典里出现的单词
2.if([i, j] 这个区间的子串出现在字典里 && f[i]是true) 那么 dp[j] = true
3.f[0] = true,其他 = false
4.先背包,再物品,顺序遍历

class Solution {public:bool wordBreak(string s, vector<string>& wordDict) {// 存储在无序哈希表中,方便查找unordered_set<string> us(wordDict.begin(), wordDict.end());int n = s.size();vector<bool> f(n + 1, false);f[0] = true;for(int j = 1; j <= n; j++){for(int i = 0; i < j; i++){// 起始位置,截取的个数string t = s.substr(i, j - i);if(us.find(t) != us.end() && f[i]){f[j] = true;}}}return f[n];}};

13.携带矿石资源


思路

多重背包,类似 01 背包,不过就是物品数量变多了

1.f[j]: 背包容量为 j 的最大价值
2.f[j] = max(f[j], f[j – z * w[i]] + z * v[i])
3.全部 = 0
4.倒序遍历

#includeusing namespace std;const int N = 1e4 + 10;int w[N], v[N], k[N];int f[N];int c, n;int main(){scanf("%d%d", &c, &n);for(int i = 0; i < n; i++) scanf("%d", &w[i]);for(int i = 0; i < n; i++) scanf("%d", &v[i]);for(int i = 0; i < n; i++) scanf("%d", &k[i]);for(int i = 0; i < n; i++){for(int j = c; j >= w[i]; j--){for(int z = 1; z <= k[i] && j >= z * w[i]; z++){f[j] = max(f[j], f[j - z * w[i]] + z * v[i]);}}}printf("%d", f[c]);return 0;}

打家劫舍

1.打家劫舍

思路

如果偷第 i 个房屋,则不可以偷第 i – 1 个房屋,可以偷第 i – 2 个房屋

1.f[i]: 下标为 i 之内的房屋可以偷盗的最大金额
2.f[i] = max(f[i – 1], f[i – 2] + nums[i])
3.f[0] = nums[0], f[1] = max(nums[0], nums[1])
4.顺序遍历

class Solution {public:int rob(vector<int>& nums) {int n = nums.size();if(n == 1) return nums[0];vector<int> f(n, 0);f[0] = nums[0], f[1] = max(nums[0], nums[1]);for(int i = 2; i < n; i++){f[i] = max(f[i - 1], f[i - 2] + nums[i]);}return f[n - 1];}};

2.打家劫舍 II

思路

头尾的房屋不可以同时偷,分两种情况,偷头和头尾,然后比大小

1.f[i]: 下标为 i 之内的房屋可以偷盗的最大金额
2.f[i] = max(f[i – 1], f[i – 2] + nums[i])
3.f[0] = nums[0], f[1] = max(nums[0], nums[1])
4.顺序遍历,倒序遍历

class Solution {public:int rob(vector<int>& nums) {int n = nums.size();if(n == 1) return nums[0];if(n == 2) return max(nums[0], nums[1]);vector<int> f(n, 0), dp(n, 0);f[0] = nums[0], f[1] = max(nums[0], nums[1]);for(int i = 2; i < n - 1; i++){f[i] = max(f[i - 1], f[i - 2] + nums[i]);}dp[n - 1] = nums[n - 1], dp[n - 2] = max(nums[n - 1], nums[n - 2]);for(int i = n - 3; i > 0; i--){dp[i] = max(dp[i + 1], dp[i + 2] + nums[i]);}return max(f[n - 2], dp[1]);}};

3.打家劫舍 III


思路

偷当前节点,就不能偷它的子节点

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public:vector<int> f(TreeNode* cur){if(cur == NULL) return {0, 0};vector<int> left = f(cur -> left);vector<int> right = f(cur -> right);int res1 = cur -> val + left[0] + right[0];int res2 = max(left[0], left[1]) + max(right[0], right[1]);return {res2, res1};}int rob(TreeNode* root) {vector<int> res = f(root);return max(res[0], res[1]);}};

买卖股票

1.买卖股票的最佳时机

思路

只能买卖一次,所以买入股票时,利润只能是 -1 * prices[i]

1.f[i][0]:第 i 天持有股票所得的最大利润,f[i][0]:第 i 天不持有股票所得的最大利润
2.f[i][0] = max(f[i – 1][0], -1 * prices[i]), f[i][1] = max(f[i – 1][1], f[i – 1][0] + prices[i])
3.f[0][0] = -1 * prices[0], f[0][1] = 0,其他 = 0
4.正序遍历

class Solution {public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(2, 0));f[0][0] = -1 * prices[0], f[0][1] = 0;for(int i = 1; i < n; i++){f[i][0] = max(f[i - 1][0], -1 * prices[i]);f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);}return f[n - 1][1];}};

2.买卖股票的最佳时机 II


思路

股票可以多次买卖,所以买入股票的时候,可能会有之前的利润,即 f[i – 1][1] – prices[i]

1.f[i][0]: 第 i 天持有股票的最大利润,f[i][1]: 第 i 天不持有股票的最大利润
2.f[i][0] = max(f[i – 1][0], f[i – 1][1] – prices[i]), f[i][1] = max(f[i – 1][1], f[i – 1][0] + prices[i])
3.f[0][0] = -1 * prices[0], f[0][1] = 0
4.顺序遍历

class Solution {public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(2, 0));f[0][0] = -1 * prices[0], f[0][1] = 0;for(int i = 1; i < n; i++){f[i][0] = max(f[i - 1][0], f[i - 1][1] - prices[i]);f[i][1] = max(f[i - 1][1], f[i - 1][0] + prices[i]);}return f[n - 1][1];}};

3.买卖股票的最佳时机 III


思路

1.f[i][0]:不操作,f[i][1]:第一次持有股票的最大利润,f[i][2]:第一次不持有股票的最大利润,f[i][3]:第二次持有股票的最大利润,f[i][4]:第二次不持有股票的最大利润
2.f[i][1] = max(f[i – 1][1], f[i – 1][0] – prices[i]), f[i][2] = max(f[i – 1][2], f[i – 1][1] + prices[i]), f[i][3] = max(f[i – 1][3], f[i – 1][2] – prices[i]), f[i][4] = max(f[i – 1][4], f[i – 1][3] + prices[i])
3.f[0][1] = -1 * prices[0], f[0][2] = 0, f[0][3] = -1 * prices[0], f[0][4] = 0,其他 = 0
4.顺序遍历

class Solution {public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(5, 0));f[0][1] = -1 * prices[0], f[0][2] = 0;f[0][3] = -1 * prices[0], f[0][4] = 0;for(int i = 1; i < n; i++){f[i][1] = max(f[i - 1][1], f[i - 1][0] - prices[i]);f[i][2] = max(f[i - 1][2], f[i - 1][1] + prices[i]);f[i][3] = max(f[i - 1][3], f[i - 1][2] - prices[i]);f[i][4] = max(f[i - 1][4], f[i - 1][3] + prices[i]);}return f[n - 1][4];}};

4.买卖股票的最佳时机 IV

思路

类似上一题,总结规律即可

1.f[i][0]:不操作,f[i][奇数]:买入股票的最大利润,f[i][偶数]:卖出股票的最大利润
2.f[i][j] = max(f[i – 1][j], f[i – 1][j – 1] – prices[i]), f[i][j + 1] = max(f[i – 1][j + 1], f[i – 1][j] + prices[i])
3.for(int i = 1; i < 2 * k; i += 2) f[0][i] = -1 * prices[0]
4.顺序遍历

class Solution {public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(2 * k + 1, 0));for(int i = 1; i < 2 * k; i += 2) f[0][i] = -1 * prices[0];for(int i = 1; i < n; i++){for(int j = 1; j < 2 * k; j += 2){f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] - prices[i]);f[i][j + 1] = max(f[i - 1][j + 1], f[i - 1][j] + prices[i]);}}return f[n - 1][2 * k];}};