HOT100打卡—day10—【DP+多维DP】—最新8.29（剩6题）

DP

---

1 70. 爬楼梯

70. 爬楼梯

一次做，AC代码：

疑问：怎么判断用搜索还是dp？这题，我没有受过dp训练所以第一反应是用dfs搜索，找到所有符合要求的叶子。

class Solution {
public:int dp[50];    // step1：含义： 对于下标i  有多少种方案到第i层/*step2：状态转移方程 dp[i] = dp[i-2] + dp[i-1]step3: dp数组初始化 dp[1] = 1 , dp[2] = 2step4: 遍历顺序 i递增step5: 模拟 1,2,3(1 1 1 + 2 1 +1 2 ),5*/ int climbStairs(int n) {// 这题我的第一感觉是搜索 什么时候用dp？？？？dp[1] = 1;dp[2] = 2;for(int i = 3; i <= n; i++)dp[i] = dp[i-1] + dp[i-2];return dp[n];}
};

2 118. 杨辉三角

118. 杨辉三角

简单，AC:

class Solution {
public:vector<vector<int>> ans;vector<vector<int>> generate(int numRows) {vector<int> tmp;tmp.push_back(1);ans.push_back(tmp);if(numRows == 1)return ans;tmp.clear();tmp.push_back(1);tmp.push_back(1);ans.push_back(tmp);if(numRows == 2)return ans;for(int i = 3; i <= numRows;i++){tmp.clear();tmp.push_back(1);for(int j = 0; j < ans[ans.size()-1].size()-1;j++){tmp.push_back(ans[ans.size()-1][j] + ans[ans.size()-1][j + 1]);}tmp.push_back(1);ans.push_back(tmp);}return ans;}
};

3 198. 打家劫舍

198. 打家劫舍

就按照五部曲思考，AC代码：

class Solution {
public:int dp[120]; // 从左往右偷  偷到第i个房子（不包含本房子）时候已经赚了的最多钱/*dp[i] = max(dp[i-1] + 0,dp[i-2]+nunms[i-2])dp[0] = 0dp[1] = 0升序模拟 样例2=== 0 0 2 7 11*/int rob(vector<int>& nums) {dp[0] = 0;dp[1] = 0;if(nums.size() == 1)return nums[0];int i = 2;for(; i < nums.size();i++)dp[i] = max(dp[i-1] + 0,dp[i-2]+nums[i-2]);return max(dp[i-1] + nums[i - 1],dp[i-2]+nums[i-2]);  // 这里的return 和状态转移方程不太一样}
};

4 279. 完全平方数

279. 完全平方数

之前没学多重背包之前看到题目是蒙的，现在学完完全背包很自然就做出来了，AC代码：

class Solution {
public:int dp[10010];  // dp[1]表示 凑成i的完全平方数最少需要的数目/*转成完全背包物品：i = 1....sqrt(n)背包：ndp[j] = min(dp[j- i]+1,dp[j])装i   不撞idp[0] = 0 其他非0下标全设为INT_MAXi++j++模拟——*/int numSquares(int n) {dp[0] = 0;for(int j = 1; j <= n; j++)dp[j] = INT_MAX;for(int i = 1; i*i <= n; i++){for(int j = 0; j <= n; j++){if(j >= i*i)dp[j] = min(dp[j- i*i]+1,dp[j]);else dp[j] = dp[j];}// for(int j = 0; j <= n; j++) cout << dp[j] << ' ';// puts("");}return dp[n];}
};

5 518. 零钱兑换 II + 322. 零钱兑换

518. 零钱兑换 II

根据上面学的理论，一次AC代码：

class Solution {
public:int dp[5005];   // 能正好装满i的背包的方式数目/*dp[j] += dp[j - coins[i]];dp[0] = 1;i++ j++模拟——*/int change(int amount, vector<int>& coins) {dp[0] = 1;for(int i = 0; i < coins.size(); i++)for(int j = 0; j <= amount; j++)if(j >= coins[i])dp[j] += dp[j - coins[i]];return dp[amount];}
};

322. 零钱兑换

类似的一题：

class Solution {
public:long long dp[10005];   // 能正好装满i的背包的最少硬币个数/*dp[j] = min(dp[j],dp[j - coins[i]] + 1)不装i  装idp[0] = 0;其他非0下标初始化为INT_MAXi++ j++模拟——0 1 2 3 4 5 6 7 8 9 10 11 0 1 1 2 2 3 3 4 4 5 5 6 0 1 1 2 2 1 2 2 3 3 2 3 */int coinChange(vector<int>& coins, int amount) {dp[0] = 0;for(int i = 1; i <= amount; i++)dp[i] = INT_MAX;for(int i = 0; i < coins.size(); i++){for(int j = 0; j <= amount; j++)if(j >= coins[i])dp[j] = min(dp[j],dp[j - coins[i]] + 1);// for(int j = 0; j <= amount; j++)cout << dp[j] << ' ';// cout << endl;}if(dp[amount] == INT_MAX)return -1;else return dp[amount];}
};

6 139. 单词拆分

139. 单词拆分

做了很久...估计2h 一开始我的思路卡死了 + 看题解之后的思路的详解见注释，

我的写法和carl 答案在一些微小的细节上略有不同，我的更好理解，但他的解法更简单。

我写的过程中，需要注意下标和字符串大小的关系要不要+1-1，而且dp[] 需要从1开始到n有意义，dp[0] 不管它。不可以只有0,...,n-1 这样会忽略s = "a" Dict = ["b"] 这样的样例，因为dp[0] 恒为1。

AC代码：

class Solution {
public://多重背包且排列/*一开始我的思路——物品:字典里面str背包:容量为？的背包  求装满时候的情况dp[wordDict.size()][s.size()]如果n = wordDict.size() m = s.size()  又感觉要考虑每个字符和Dict中每个字符串的关系 很麻烦        *//*看了题解，才知道我纠结的地方 每个字符和Dict中每个字符串的关系 很麻烦，但其实可以用substr函数考虑背包的s的子串和Dict中每个字符串来比较，这样就变得很简单了。而且之前思考时候不知道dp[]存的值要是int还是char什么东西其实就题目结果反推，dp[] = trur/flase*/bool dp[310];   //以i结尾的字符串是否可以利用字典中出现的单词拼接出来/*dp[j] = dp[j - wordDict[i].size()] && substr(s,j - wordDict[i].size(),wordDict[i].size()) == wordDict[i];dp[0] = 1;多重背包+排列背包j++ 物体i++模拟——6 7 8 9 10 11j = 11 size = 5 dp[6]*/bool wordBreak(string s, vector<string>& wordDict) {dp[0] = 1;bool tmp[100][100];for(int j = 0; j <= s.size();j++){for(int i = 0; i　< wordDict.size();i++){if(j == wordDict[i].size())  // 能装下一个dp[j] =  (s.substr(j  - wordDict[i].size(),wordDict[i].size()) == wordDict[i]) || dp[j];else if(j > wordDict[i].size() )    // 能至少装2个 dp[j] = dp[j  - wordDict[i].size()] && (s.substr(j - wordDict[i].size(),wordDict[i].size()) == wordDict[i]) || dp[j];}}// for(int i = 0; i　< wordDict.size();i++)// {//     for(int j = 0; j < s.size();j++)//         cout << tmp[i][j] << ' ';//     cout << endl;// }return dp[s.size() ];}
};

7

8

9 01背包应用题——416. 分割等和子集

416. 分割等和子集

一开始看到题目，想用贪心——排序+双指针 每次都把当前相对小的放进小的sum中，写完之后发现过不了：[1,1,2,2]这样的样例。错误代码：

class Solution {
public:/*左边的sum 小于 右边的sum l++，左边的sum+=左边的sum 大于 同理如果等于左边前进 1,2,3,4, 5,6,7,8,9, 10*/bool canPartition(vector<int>& nums) {// 解法1:排序+双指针if(nums.size() == 1)return 0;sort(nums.begin(),nums.end());int l = 0;int r = nums.size() - 1;int leftsum = 0;int rightsum = 0;while(l <= r){if(leftsum <= rightsum){leftsum += nums[l++];}else{rightsum += nums[r--];}}cout << l << "  " << r << endl;cout << leftsum << "  " << rightsum;if(leftsum == rightsum)return 1;else return 0;}
};

要明确本题中我们要使用的是01背包，因为元素我们只能用一次。

回归主题：首先，本题要求集合里能否出现总和为 sum / 2 的子集。

那么来一一对应一下本题，看看背包问题如何来解决。

只有确定了如下四点，才能把01背包问题套到本题上来。

• 背包的体积为sum / 2
• 背包要放入的商品（集合里的元素）重量为 元素的数值，价值也为元素的数值
• 背包如果正好装满，说明找到了总和为 sum / 2 的子集。
• 背包中每一个元素是不可重复放入。

具体分析过程见注释， AC代码：

class Solution {
public:// 找到一个背包 能够装nums.total（所有物体重量总和）/2的东西int dp[10005];    // 容积为i的背包 根据现有的物体重量情况最多能装的物体的重量/*转换成01背包问题：假设有一个nums.total/2的背包有若干个物体，每个物体的重量就是nums[i] 本题可以舍弃价值这个概念就是问一个nums.total/2的背包最多能够装的物体的重量是多少 能不能达到nums.total/2if(j < nums[i])dp[j] = dp[j];else dp[j] = max(dp[j] , dp[j - nums[i]]+nums[i]);dp[0] = 0;其他默认是0for物体i++ for容积j--模拟——*/bool canPartition(vector<int>& nums) {dp[0] = 0;int total = 0;for(auto i : nums)total += i;if(total % 2 == 0)total /= 2;else return 0;for(int i = 0; i < nums.size();i++){for(int j = total ; j >= 0; j--){if(j < nums[i])dp[j] = dp[j];else dp[j] = max(dp[j] , dp[j - nums[i]]+nums[i]);}}if(dp[total] == total)return 1;else return 0;}
};

10

多维DP

---

1 62. 不同路径

62. 不同路径

自己试着写写，二维dp数组，还是五步曲，AC代码：

class Solution {
public:int dp[105][105];//  (i,j) 表示到达这个格子最多几条不同的路径/*状态转移：dp[i][j] = dp[i-1][j] + dp[i][j-1];dp数组初始化（初始化 第一行和第一列）dp[0][0] = 0dp[0][x] = 1dp[x][0] = 1顺序：for（i++）中for（j++）模拟一下2*30 1 11 2 3*/int uniquePaths(int m, int n) {// 原来 用dp 不用搜索 是因为怕超时dp[0][0] = 0;for(int i = 1; i < n; i++)dp[0][i] = 1;for(int i = 1; i < m; i++)dp[i][0] = 1;for(int i = 1; i < m;i++)for(int j = 1; j < n; j++)dp[i][j] = dp[i-1][j] + dp[i][j-1];if(m == 1 && n == 1)return 1;  // 特殊处理return dp[m-1][n-1];}
};

1.2 63. 不同路径 II（有障碍物版本的上一题）

63. 不同路径 II

有障碍物就是加一堆if-else ，自己写的 ，然后debug半天很多边界通过反复提交才试出来，比如：

if(m == 1 && n == 1)return obstacleGrid[0][0] ^ 1;  // 因为dp[0]设置为0  所以要特殊处理

if(obstacleGrid[0][0] || obstacleGrid[n-1][m-1] || dp[n-1][m-1] == -1)return 0;  //特殊处理起点有障碍物 、终点有障碍物、 终点不可达（三种情况）

AC代码：

class Solution {
public:int dp[105][105];//  (i,j) 表示到达这个格子最多几条不同的路径 -1表示不可达/*状态转移：if(obs[i-1][j] == 0 && dp[i-1][j] != -1)  // 上一个不是障碍物且可达dp[i][j] += dp[i-1][j]if(obs[i][j-1] == 0 && dp[i][j-1] != -1)  // 左边一个不是障碍物且可达dp[i][j] += dp[i][j-1]if((obs[i-1][j] == 1 || dp[i-1][j] == -1) && (obs[i][j-1] == 1 || dp[i][j-1] == -1))if(obstacleGrid[i][j])  // 两个都不能达到我 或者我本身是障碍物dp[i][j] = -1dp数组初始化（初始化 第一行和第一列）dp[0][0] = 0dp[0][x] = 1 这一行第一个障碍物 后面的格子都不可达 设为-1dp[x][0] = 1 这一列第一个障碍物 下面的格子都不可达 设为-1顺序：for（i++）中for（j++）模拟一下3*30  1  11  -1 11  1  1*/int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {dp[0][0] = 0;int n = obstacleGrid.size();   // 行int m = obstacleGrid[0].size();int x = 1;for(int i = 1; i < n; i++){if(obstacleGrid[i][0] == 1)x = -1;dp[i][0] = x;}x = 1;for(int i = 1; i < m; i++){if(obstacleGrid[0][i] == 1)x = -1;dp[0][i] = x;}for(int i = 1; i < n;i++)for(int j = 1; j < m; j++){if(obstacleGrid[i-1][j] == 0 && dp[i-1][j] != -1)dp[i][j] += dp[i-1][j];if(obstacleGrid[i][j-1] == 0 && dp[i][j-1] != -1)dp[i][j] += dp[i][j-1];if((obstacleGrid[i-1][j] == 1 || dp[i-1][j] == -1) && (obstacleGrid[i][j-1] == 1 || dp[i][j-1] == -1)) // 两个都满dp[i][j] = -1;if(obstacleGrid[i][j])dp[i][j] = -1;}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++)cout << dp[i][j] << " ";cout << endl;}if(m == 1 && n == 1)return obstacleGrid[0][0] ^ 1;  // 因为dp[0]设置为0  所以要特殊处理if(obstacleGrid[0][0] || obstacleGrid[n-1][m-1] || dp[n-1][m-1] == -1)return 0;  //特殊处理起点有障碍物 、终点有障碍物、 终点不可达return dp[n-1][m-1];}
};

看了题解，思路差不多，就是它遇到障碍dp[i][j]保持0，然后状态转移方程就可以写的很简单。

直接复制粘贴的代码：

class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍，直接返回0return 0;vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};

2 64. 最小路径和

64. 最小路径和

和62.不同路径差不多。

AC代码：

class Solution {
public:int dp[210][210]; // (i,j)表示从起点出发到（i，j）的路径数字总和最小的数/*dp[i][j] = min(d[i-1][j]+grid[i][j] , d[i][j-1]+grid[i][j])dp[0][0] = grid[0][0]dp[0][j] += grid[0][j]dp[i][0] += grid[i][0]i++j++*/int minPathSum(vector<vector<int>>& grid) {int n = grid.size();int m = grid[0].size();dp[0][0] = grid[0][0];for(int j = 1; j < m; j++)dp[0][j] = dp[0][j-1]+grid[0][j];for(int i = 1;i < n; i++)dp[i][0] = dp[i-1][0]+grid[i][0];for(int i = 1; i < n; i++)for(int j = 1; j < m; j++ )dp[i][j] = min(dp[i-1][j]+grid[i][j] , dp[i][j-1]+grid[i][j]);return dp[n-1][m-1];}
};

3

4

5