一、动归五部曲
- 确定dp数组(dp table)以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
二、题目实战
2.1 基础题目
509. 斐波那契数
70. 爬楼梯
746. 使用最小花费爬楼梯这三道题目作为动归入门题目,主要是熟悉动归五部曲以及方法论
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int len = cost.size();
vector<int> dp(len, 0);
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < len; i++) {
dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
}
return min(dp[len - 1], dp[len - 2]);
}
};
// 这道题目其实主要是题意不太好理解,仔细理解题意,本身不难
2.2 路径题目
// 这道题是基础的二维dp数组题目,当然可以简化为一维的dp数组
// 二维的dp数组,注意第一行和第一列的初始化
// 递推公式如下:
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
// 将有障碍物的地方赋值为0。在初始化的时候要注意:障碍物之后都应该赋值0。
if (obstacleGrid[i][j] == 1) dp[i][j] = 0;
else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
2.3 343. 整数拆分
这道题目最难的地方在于递推公式:dp[i]取三者的最大值(dp[i],dp[i - j] j,(i - j) j)
可以理解为:j (i - j) 是单纯的把整数拆分为两个数相乘,而j dp[i - j]是拆分成两个以及两个以上的个数相乘。
for (int i = 3; i <= n ; i++) {
for (int j = 1; j < i - 1; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
2.4 96. 不同的二叉搜索树
这道题目还是很难的,递归公式需要找规律,很难。
dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
2.5 0-1背包问题
416. 分割等和子集
将问题转化为0-1背包问题:
- 背包的体积为sum / 2
- 背包要放入的商品(集合里的元素)重量为 元素的数值,价值也为元素的数值
- 背包如果正好装满,说明找到了总和为 sum / 2 的子集。
背包中每一个元素是不可重复放入。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0;
for (int i : nums) {
sum += i;
}
if (sum % 2 != 0) return false;
int target = sum / 2;
vector<int> dp(target + 1, 0);
for (int i = 0; i < nums.size(); i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
return dp[target] == target ? true : false;
}
};
1049. 最后一块石头的重量 II
这道题跟上一道几乎一样,唯一不同在于最后的答案求解
int ans = sum - 2 * dp[target];
重点题目! 这道题虽然也是0-1背包问题,但是求解的是”方式数目“。递推公式需要做出改变。
对问题进行转化:
- left组合 - right组合 = target
- left + right = sum
left = (target + sum) / 2
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (auto i : nums) {
sum += i;
}
// 两种特殊情况,要额外进行考虑
// 尤其是第一个,测试用例中专门考察了
if (abs(target) > sum) return 0;
if ((target + sum) % 2 != 0) return 0;
int bag = (target + sum) / 2;
vector<int> dp(bag + 1, 0);
dp[0] = 1; // 为0的时候方案初始化为一种
for (int i = 0; i < nums.size(); i++) {
for (int j = bag; j >= nums[i]; j--) {
// 要求方案的数目,递推公式一般都是类似这种形式
dp[j] += dp[j - nums[i]];
}
}
return dp[bag];
}
};
二维0-1背包问题,即背包有两个
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
// 二维0-1背包
// 如果设置为(m, n)的大小,则必须对dp[0][0]初始化;为了避免这一麻烦的步骤,因此设置为
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
// 先遍历物品
for (int k = 0; k < strs.size(); k++) {
int numZero = 0, numOne = 0;
for (auto c : strs[k]) {
if (c == '0') numZero++;
else numOne++;
}
// 倒向遍历背包1
for (int i = m; i >= numZero; i--) {
// 倒向遍历背包2
for (int j = n; j >= numOne; j--) {
// 当子串c能够放进去的时候,最大子集的长度 + 1
dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1);
}
}
}
return dp[m][n];
}
};
2.6 完全背包问题
完全背包问题,物品和背包的问题都是正向遍历// 对于纯完全背包问题,物品和背包的遍历顺序是可以颠倒的
但是在求装满背包有几种方案的时候,遍历顺序非常关键 如果求组合数就是外层for循环遍历物品,内层for遍历背包。 如果求排列数就是外层for遍历背包,内层for循环遍历物品。
组合不强调元素之间的顺序,排列强调元素之间的顺序。
// 这道题求 完全背包问题的组合数
// 先遍历物品,再遍历背包
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
// dp[0]一定要初始化
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
// 求几种方案的递推公式
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
// 完全背包问题的排列数
int combinationSum4(vector<int>& nums, int target) {
// 根据示例可知,本题实际上是求解排列个数
vector<int> dp(target + 1, 0);
dp[0] = 1;
// 先遍历背包,再遍历物品
for (int i = 1; i <= target; i++) {
for (int j = 0; j < nums.size(); j++) {
// 确保i >= nums[j]
// 这道题目中有个测试用例超出了INT_32的范围
if (i >= nums[j] && dp[i] < INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
这道题求 最少的硬币个数,属于完全背包的组合问题。
// 难点在于递推公式和初始化
int coinChange(vector<int>& coins, int amount) {
// 递推公式为 min(),所以需要初始化为int型最大值
vector<int> dp(amount + 1, INT32_MAX);
// dp[0]必须初始化为0,根据递推公式得来
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) {
for (int j = coins[i]; j <= amount; j++) {
// 判断此种情况下没必要更新,并且避免dp[j - coins[i]] + 1超出int范围
if (dp[j - coins[i]] != INT32_MAX) {
// 如果硬币能够放进去,则数目 + 1
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == INT32_MAX ? -1 : dp[amount];
}