这几天晚上看比赛，就把刷题耽误了。还好是开新章节，前面的题都比较简单。
然后周天做完了又忘记发了
动态规划
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数
Day37前两道题太简单了，我们从第三道题开始
leetcode.746.使用最小花费爬楼梯
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size()+8);//dp数组存储当前点位的最优解
dp[0]=0;
dp[1]=0;
for(int i=2;i<=cost.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 i=1;i<=m;i++){
dp[i][1]=1;
}
for(int i=1;i<=n;i++){
dp[1][i]=1;
}
for(int i=2;i<=m;i++){
for(int j=2;j<=n;j++){
dp[i][j]=dp[i][j-1]+dp[i-1][j];
}
}
return dp[m][n];
}
};leetcode.63.不同路径Ⅱ
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));//注意最好用vector容器。都初始化为0
/*if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1){//如果开始或终点有障碍那直接返回障碍
return 0;
}*/
for(int i=0;i<m;i++){
if(obstacleGrid[i][0]==1){//如果在边界的两条线上有障碍，那从障碍开始一下路径数都为0
break;
}
dp[i][0]=1;
}
for(int i=0;i<n;i++){
if(obstacleGrid[0][i]==1){
break;
}
dp[0][i]=1;
}
for(int i=1;i<m;i++){
for(int j=1;j<n;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(vector<int>& nums) {
sort(nums.begin(),nums.end());
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
vector<int> dp(11111,0);//这里数组尽量开大点，不然过不了
if (sum % 2 == 1) return false;
sum= sum / 2;//能够分成两个子集的元素和相等说明，有一部分元素相加的和是总和的一半
//那么元素个数是种类，sum/2是容量的01背包问题就出现了
for(int i=0;i<nums.size();i++){
for(int j=sum;j>=nums[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(vector<int>& stones) {
vector<int> dp(10010,0);
int sum=0;
for(int i=0;i<stones.size();i++){
sum+=stones[i];
}
int sum1=sum;
sum=sum/2;
for(int i=0;i<stones.size();i++){
for(int j=sum;j>=stones[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 count=0;
int findTargetSumWays(vector<int>& nums, int target) {
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
if (abs(target) > sum) return 0;
sum+=target;
if(sum%2==1){
return 0;
}
sum=sum/2;
int bagSize=sum;
vector<vector<int>> dp(nums.size(), vector<int>(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(vector<int>& 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;
vector<int> 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 count=0;
void backtrack(vector<int>& nums,int target,int index,int sum){
if(index==nums.size()){
if(sum==target){
count++;
}
}else{
backtrack(nums,target,index+1,sum+nums[index]);
backtrack(nums,target,index+1,sum-nums[index]);
}
}
int findTargetSumWays(vector<int>& 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个0，oneNum个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数组遍历的时候不用倒序呢？
因为对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖！
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化0
for (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];
}
};
