代码随想录算法训练营第四十五天 | 1049. 最后一块石头的重量 II、494. 目标和、474.一和零

1049. 最后一块石头的重量 II

视频讲解： 动态规划之背包问题，这个背包最多能装多少？LeetCode：1049.最后一块石头的重量II_哔哩哔哩_bilibili

代码随想录

解题思路

直接将这一些石头，分为两堆，让他们尽可能相似，然后再相撞，就是最小值

1. dp[j] 背包容量为j所背的最大价值

2.dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

3.初始化，全为0即可

4.先遍历物品，再遍历背包，因为只选取一次因此倒序遍历

5. return (sum - dp[target]) - dp[target];   前面是剩下的一堆，后面是检到背包里的一堆 

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
         int sum =0;    //背包的重量
         if(stones.size()<=1) return stones[0];   //只有一块石头，就直接返回重量
         for(int i: stones)
            sum+=i;
        int target = sum /2;
        vector<int> dp(target+1 , 0);            //dp数组
        //初始化
        for(int i = 0; i<stones.size();i++)
        {
            for(int j=target; j>=stones[i]; j--)
            {
                dp[j] = max( dp[j] ,dp[j-stones[i]] + stones[i]);
            }
        }
        return (sum - dp[target]) - dp[target]; 
    }
};

• 时间复杂度：O(m × n) , m是石头总重量（准确的说是总重量的一半），n为石头块数
• 空间复杂度：O(m)

 494. 目标和

视频讲解： https://www.bilibili.com/video/BV1o8411j73x

https://programmercarl.com/0494.%E7%9B%AE%E6%A0%87%E5%92%8C.html

解题思路

我们假定加法集合left，减法集合right

left + right  = 所有元素的和

left - right = target

可以得到 left = (target + sum) /2 ,如果不能整除则凑不成target

那就将问题转换为有多少种方法可以将这个背包装满

1.dp[j]  容量为j的背包有多少种方法

2.递推公式

这题的公式和不同路径的思想是很像的

只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

例如：dp[j]，j 为5，

• 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
• 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
• 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
• 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
• 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来

求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

3.初始化

dp[0] =1  ; 装满容量为0的背包有1种方法

4.先物品再背包，倒序遍历

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
           int sum = 0;
           for(int i: nums)
           sum+=i;
           if(abs(target)>sum) return 0;
           if((target+sum)%2 != 0)  return 0;
           int left = (target+sum) /2;
           vector<int> dp(left+1,0);
           dp[0] = 1;
           for(int i =0 ; i<nums.size(); i++)
           {
                for(int j= left ; j>=nums[i] ; j--)
                {
                     dp[j] += dp[j - nums[i]];
                }
           }
           return dp[left];
    }
};

 474.一和零

视频讲解： 动态规划之背包问题，装满这个背包最多用多少个物品？| LeetCode：474.一和零_哔哩哔哩_bilibili

代码随想录

解题思路

这题不一样的点就是维度多了一个

1.dp[i][j] i个0，j个1， 最大背多少个物品

2. dp[i][j] = max( dp[i-x][j-y] + 1 ,  dp[i][j] )      重量就是x个0，y个1 ， 价值就是个数

3. dp[0][0] = 0;

    非初始下标也都是0，因为非0的一个正整数可能会覆盖掉递推哪个大

4.先物品再背包，倒序遍历 

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
          vector<vector<int>> dp(m+1 , vector<int>(n+1,0));
          for(string s: strs)
          {
              int x =0;
              int y=0;
              for(char c : s)
              {
                 if(c=='0') x++;
                 else y++;
              }

              for(int i = m; i>=x ; i--)
              {
                 for(int j = n ;j>=y ; j-- )
                 {
                    dp[i][j] = max(dp[i][j],dp[i-x][j-y]+1);
                 }
              }
          }
          return dp[m][n];
    }
};

收获

稀里糊涂的