html5网站单页模板,亚马逊电商运营新手入门,余姚网站建设余姚,江西省建设部网站这几天晚上看比赛#xff0c;就把刷题耽误了。还好是开新章节#xff0c;前面的题都比较简单。
然后周天做完了又忘记发了
动态规划
确定dp数组#xff08;dp table#xff09;以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数 Day37前两道题太简单…这几天晚上看比赛就把刷题耽误了。还好是开新章节前面的题都比较简单。
然后周天做完了又忘记发了
动态规划
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数 Day37前两道题太简单了我们从第三道题开始
leetcode.746.使用最小花费爬楼梯 class Solution {
public:int minCostClimbingStairs(vectorint cost) {vectorint dp(cost.size()8);//dp数组存储当前点位的最优解dp[0]0;dp[1]0;for(int i2;icost.size();i){dp[i]min(dp[i-1]cost[i-1],dp[i-2]cost[i-2]);//这是dp公式到达第i阶的最优解肯定是i-1阶的最优解从i-1的花费和i-2阶的最有解从i-2阶段的花费中小的那一个}return dp[cost.size()];}};
leetcode.62.不同路径 class Solution {
public:int uniquePaths(int m, int n) {int dp[105][105];dp[0][0]0;for(int i1;im;i){dp[i][1]1;}for(int i1;in;i){dp[1][i]1;}for(int i2;im;i){for(int j2;jn;j){dp[i][j]dp[i][j-1]dp[i-1][j];}}return dp[m][n];}
}; leetcode.63.不同路径Ⅱ class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {
int m obstacleGrid.size();int n obstacleGrid[0].size();vectorvectorint dp(m, vectorint(n, 0));//注意最好用vector容器。都初始化为0/*if(obstacleGrid[0][0]1||obstacleGrid[m-1][n-1]1){//如果开始或终点有障碍那直接返回障碍return 0;}*/for(int i0;im;i){if(obstacleGrid[i][0]1){//如果在边界的两条线上有障碍那从障碍开始一下路径数都为0break;}dp[i][0]1;}for(int i0;in;i){ if(obstacleGrid[0][i]1){break;}dp[0][i]1;}for(int i1;im;i){for(int j1;jn;j){if(obstacleGrid[i][j]0)dp[i][j]dp[i][j-1]dp[i-1][j];//如果碰不到障碍就进行dp保证障碍处路径为0}}return dp[m-1][n-1];}
};
leetcode.416.分割等和子集 class Solution {
public:bool canPartition(vectorint nums) {sort(nums.begin(),nums.end());int sum0;for(int i0;inums.size();i){sumnums[i];}vectorint dp(11111,0);//这里数组尽量开大点不然过不了if (sum % 2 1) return false;sum sum / 2;//能够分成两个子集的元素和相等说明有一部分元素相加的和是总和的一半//那么元素个数是种类sum/2是容量的01背包问题就出现了for(int i0;inums.size();i){for(int jsum;jnums[i];j--){dp[j] max(dp[j], dp[j - nums[i]] nums[i]);}}if(dp[sum]sum){return true;}return false;}
};
leetcode.1049.最后一块的石头重量 class Solution {
public:
//和分割等和子列类似int lastStoneWeightII(vectorint stones) {vectorint dp(10010,0);int sum0;for(int i0;istones.size();i){sumstones[i];}int sum1sum;sumsum/2;for(int i0;istones.size();i){for(int jsum;jstones[i];j--){dp[j]max(dp[j],dp[j-stones[i]]stones[i]);}}return sum1-2*dp[sum];}
};
leetcode.494.目标和
假设加法的总和为x那么减法对应的总和就是sum - x。
所以我们要求的是 x - (sum - x) target
x (target sum) / 2
此时问题就转化为用nums装满容量为x的背包有几种方法 不放物品i即背包容量为j里面不放物品i装满有dp[i - 1][j]中方法。 放物品i 即先空出物品i的容量背包容量为j - 物品i容量放满背包有 dp[i - 1][j - 物品i容量] 种方法。 if (nums[i] j) dp[i][j] dp[i - 1][j]; //说明背包容量装不下 物品i所以此时装满背包的方法值 等于 不放物品i的装满背包的方法
举例推导dp数组
输入nums: [1, 1, 1, 1, 1], target: 3
bagSize (target sum) / 2 (3 5) / 2 4
dp数组状态变化如下 那么最上行dp[0][j] 如何初始化呢
dp[0][j]只放物品0 把容量为j的背包填满有几种方法。
只有背包容量为 物品0 的容量的时候方法为1正好装满。
其他情况下要不是装不满要不是装不下。
所以初始化dp[0][nums[0]] 1 其他均为0 。
表格最左列也要初始化dp[i][0] : 背包容量为0 放物品0 到 物品i装满有几种方法。
都是有一种方法就是放0件物品。
即 dp[i][0] 1
如果有两个物品物品0为0 物品1为0装满背包容量为0的方法有几种。
放0件物品放物品0放物品1放物品0 和 物品1
此时是有4种方法。
其实就是算数组里有t个0然后按照组合数量求即 2^t
遍历顺序
在明确递推方向时我们知道 当前值 是由上方和左上方推出。
那么我们的遍历顺序一定是 从上到下从左到右。
因为只有这样我们才能基于之前的数值做推导。 for (int i 0; i nums.size(); i) {if (nums[i] 0) numZero;dp[i][0] (int) pow(2.0, numZero);}
class Solution {
public:
int count0;int findTargetSumWays(vectorint nums, int target) {int sum0;for(int i0;inums.size();i){sumnums[i]; }if (abs(target) sum) return 0; sumtarget;if(sum%21){return 0;} sumsum/2;int bagSizesum;vectorvectorint dp(nums.size(), vectorint(10010, 0));// 初始化最上行if (nums[0] bagSize) dp[0][nums[0]] 1; // 初始化最左列最左列其他数值在递推公式中就完成了赋值dp[0][0] 1; int numZero 0;for (int i 0; i nums.size(); i) {if (nums[i] 0) numZero;dp[i][0] (int) pow(2.0, numZero);}// 以下遍历顺序行列可以颠倒for (int i 1; i nums.size(); i) { // 行遍历物品for (int j 0; j bagSize; j) { // 列遍历背包if (nums[i] j) dp[i][j] dp[i - 1][j]; else dp[i][j] dp[i - 1][j] dp[i - 1][j - nums[i]];}}return dp[nums.size() - 1][bagSize];}
};
一维数组版
二维DP数组递推公式 dp[i][j] dp[i - 1][j] dp[i - 1][j - nums[i]];
去掉维度i 之后递推公式dp[j] dp[j] dp[j - nums[i]] 即dp[j] dp[j - nums[i]]
遍历物品放在外循环遍历背包在内循环且内循环倒序为了保证物品只使用一次。 class Solution {
public:int findTargetSumWays(vectorint nums, int target) {int sum 0;for (int i 0; i nums.size(); i) sum nums[i];if (abs(target) sum) return 0; // 此时没有方案if ((target sum) % 2 1) return 0; // 此时没有方案int bagSize (target sum) / 2;vectorint dp(bagSize 1, 0);dp[0] 1;for (int i 0; i nums.size(); i) {for (int j bagSize; j nums[i]; j--) {dp[j] dp[j - nums[i]];}}return dp[bagSize];}
};
深搜遍历做法
class Solution {
public:
int count0;void backtrack(vectorint nums,int target,int index,int sum){if(indexnums.size()){if(sumtarget){count;}}else{backtrack(nums,target,index1,sumnums[index]);backtrack(nums,target,index1,sum-nums[index]);}}int findTargetSumWays(vectorint nums, int target) {backtrack(nums,target,0,0);return count; }
};
leetcode.474.一零和.. 本题中strs 数组里的元素就是物品每个物品都是一个
而m 和 n相当于是一个背包两个维度的背包。
理解成多重背包的同学主要是把m和n混淆为物品了感觉这是不同数量的物品所以以为是多重背包。
但本题其实是01背包问题
只不过这个背包有两个维度一个是m 一个是n而不同长度的字符串就是不同大小的待装物品。
开始动规五部曲
确定dp数组dp table以及下标的含义
dp[i][j]最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。
确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来strs里的字符串有zeroNum个0oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] 1。
然后我们在遍历的过程中取dp[i][j]的最大值。
所以递推公式dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);
此时大家可以回想一下01背包的递推公式dp[j] max(dp[j], dp[j - weight[i]] value[i]);
对比一下就会发现字符串的zeroNum和oneNum相当于物品的重量weight[i]字符串本身的个数相当于物品的价值value[i]。
这就是一个典型的01背包 只不过物品的重量有了两个维度而已。
dp数组如何初始化
01背包的dp数组初始化为0就可以。
因为物品价值不会是负数初始为0保证递推的时候dp[i][j]不会被初始值覆盖。
确定遍历顺序
01背包一定是外层for循环遍历物品内层for循环遍历背包容量
那么本题也是物品就是strs里的字符串背包容量就是题目描述中的m和n。相当于之前的一维dp采用了滚动数组)
倒序遍历是为了保证物品i只被放入一次。但如果一旦正序遍历了那么物品0就会被重复加入多次
那么问题又来了为什么二维dp数组遍历的时候不用倒序呢
因为对于二维dpdp[i][j]都是通过上一层即dp[i - 1][j]计算而来本层的dp[i][j]并不会被覆盖 class Solution {
public:int findMaxForm(vectorstring strs, int m, int n) {vectorvectorint dp(m 1, vectorint (n 1, 0)); // 默认初始化0for (string str : strs) { // 遍历物品int oneNum 0, zeroNum 0;for (char c : str) {if (c 0) zeroNum;else oneNum;}for (int i m; i zeroNum; i--) { // 遍历背包容量且从后向前遍历for (int j n; j oneNum; j--) {dp[i][j] max(dp[i][j], dp[i - zeroNum][j - oneNum] 1);}}}return dp[m][n];}
};
