手机网站建设公司哪家好,虹桥街道网站建设,银川网站建设公司哪家不错,合肥建站优化DP 1 70. 爬楼梯
70. 爬楼梯
一次做#xff0c;AC代码#xff1a;
疑问#xff1a;怎么判断用搜索还是dp#xff1f;这题#xff0c;我没有受过dp训练所以第一反应是用dfs搜索#xff0c;找到所有符合要求的叶子。 class Solution {
public:int dp[50]; // step1AC代码
疑问怎么判断用搜索还是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) {// 这题我的第一感觉是搜索 什么时候用dpdp[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:vectorvectorint ans;vectorvectorint generate(int numRows) {vectorint 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(vectorint 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_MAXij模拟——*/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, vectorint 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(vectorint 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, vectorstring 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(vectorint 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(vectorint 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顺序fori中forj模拟一下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顺序fori中forj模拟一下3*30 1 11 -1 11 1 1*/int uniquePathsWithObstacles(vectorvectorint 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(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] 1 || obstacleGrid[0][0] 1) //如果在起点或终点出现了障碍直接返回0return 0;vectorvectorint dp(m, vectorint(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)表示从起点出发到ij的路径数字总和最小的数/*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]ij*/int minPathSum(vectorvectorint 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
