leetcode刷题详解八

• 将 i 拆分成 j和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是j×(i−j)；

• 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是j×dp[i−j]。

  一个大小为i的数可以分为j和i-j
  ----------------------
  |    j    |   (i-j)  |
  ----------------------
  

int integerBreak(int n) {
    vector<int> dp(n+1);
    dp[0] = 0;
    dp[1] = 0;
    for(int i = 2; i < n + 1; i++){
        int MAX = 0;
        //注意这里j<i，其实j<=(i/2)也是可以的
        //因为i-j是逐步变小的，当i-j小于i/2的时候就自然舍弃掉了
        for(int j = 1; j < i; j++){
            MAX = max(max(j*(i-j),j*dp[i-j]), MAX);
        }
        dp[i] = MAX;
    }
    return dp[n];
}

• 注意事项

  这道题第二次做了还忘了，切记！！！

int numTrees(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for(int i = 2; i < n + 1; i++){
        for(int j = 1; j <= i; j++){
            //记住，j是作为根节点的，所以j要从1开始
            dp[i] += dp[j-1] * dp[i-j];
        }
    }
    return dp[n];
} 

排列组合问题，这道题还可以这样翻译：

楼梯的阶数一共为target，一次可以走的步数为nums[i]。 一共有多少种走法？

int combinationSum4(vector<int>& nums, int target) {
    int n = nums.size();
    vector<int> dp(target + 1, 0);
    dp[0] = 1;
    for(int i  = 0; i < target + 1; i++){
        for(auto num : nums){
            if(i - num >= 0 && dp[i] < INT_MAX - dp[i -num]){
                dp[i] += dp[i - num];
            }
        }
    }
    return dp[target];
}

第518题使用二维数组写的，其实可以改写为1维数组，背包问题就用一维数组来做！

• 易错点

  主要在于数组越界问题，这道题很巧妙，可以参考一下。

+++

• 解题思路

  首先，能分成两个相同的子集表明一个问题：这个集合中元素的和是偶数！！！。因此这道题就是01背包问题，即设计方案使得元素集合达到sum/2。

• 代码

  bool canPartition(vector<int>& nums) {
          int n = nums.size();
          int sum = 0;
      	//for循环的另一种写法，比较简单
          for(int& i : nums){
              sum += i;
          }
          if(sum%2 != 0){
              return false;
          }
          int target = sum / 2;
      	//动态规划的关键是对dp数组的定义
      	//本题中dp数组表示把第i个物品放入背包，此时背包重量为j的bool值
      	//物品就是给的数组，重量就是对应的和的一半
          vector<vector<bool>> dp(n+1, vector<bool>(target+1, false));
      	//当背包重量为0的时候，永远为true，这个要想一想
          for(int i = 0; i < n+1; i++){
              dp[i][0] = true;
          }
          for(int i =1 ; i < n + 1; i++){
              for(int j = 1; j < target + 1; j++){
                  if(j - nums[i-1] < 0 ){
                      dp[i][j] = dp[i - 1][j];
                  }else{
                      //状态转移方程如下：
                      //1.如果不把这第i个物品装入背包，那么能够恰好装满背包取决于上一个状态dp[i-1][j]，继承之前的结果。
                      //2.如果把这第i个物品装入了背包，那么是否能够恰好装满背包，取决于状态dp[i - 1][j-nums[i-1]]。
                      dp[i][j] = dp[i - 1][j] || dp[i-1][j - nums[i-1]];
                  }
                  
              }
          }
          return dp[n][target];
      }
  

• 解题思路

  这道题的难点就在于为什么能够转化成01背包问题。最后求的是数组中石头的可能最小重量，那是不是可以转换成如果是最小数量，那就把数组分成两堆，同时这两堆的差值最小！这本质就是个脑筋急转弯！

  整个题目，每个回合数两两抽出来比较，两个数之差将被再一次扔到数组里面，继续上面的过程。每个回合都会丢失掉两个数字，加入一个新的数字，这个数字就是两个数的差。相当于来说，就是少了a和b，但是多了一个a-b，a,b就此消失，但是在下一回合，a-b可能又被抓出去pk，pk后a-b就此再消失了，又产生了新的一个差。那么每一步来说，其实就相当于a,b没有真正意义消失。 到了最后一回合，我们可以知道，其实找出两个最接近的数字堆。

  总： （26+31+21） - （40+33） 这就是找出两个总和接近的两个堆。 如何让两个堆接近呢？ 那就是沿着中间分两半，找左右各自那一半，那么思路就来到了找出一半堆这里。那么就自然而然地来到取不取的问题，就是01背包问题。

  近一步想：把数组分成两堆，那么总数组和为sum，这两堆的差如果要最小，是不是应该每一堆都要接近sum/2？

  在想一步：我们就需要让每一堆都尽可能接近sum/2，这样不就能保证两堆差最小

  可以得出结论：两堆中出现一个最大值max_weight，那么最后的值就是sum-2*max_weight

• 代码

  int lastStoneWeightII(vector<int>& stones) {
          int sum = accumulate(stones.begin(), stones.end(), 0);
          int target = sum / 2;
          int n = stones.size();
          //dp数组的含义非常重要！
          //按照01背包典型的dp定义
          //即前i个物品，背包容量为j
          vector<vector<int>> dp(n+1, vector<int>(target+1, 0));
          for(int i = 1; i < n + 1; i++){
              for(int j = 1; j < target + 1; j++){
                  if(j - stones[i -1] < 0){
                      dp[i][j] = dp[i -1][j];
                  }else{
                      //注意，第i个物品的索引值是stone[i-1]!!!
                      dp[i][j] = max(dp[i -1][j], dp[i -1][j - stones[i -1]] + stones[i - 1]);
                  }
              }
          }
          cout<<sum<<endl;
          cout<<target<<endl;
          cout<<dp[n][target]<<endl;
          return sum - 2 * dp[n][target];
      }
  

• 注意点

  1. std::accumulate这个要会用，很方便
  2. 01背包这个模板要回，就按照这个dp数组的定义走

• 思路

  这道题又他妈是移到脑筋急转弯，感觉碰到数组的题全是脑筋急转弯啊！

  一般碰到这种数组题目，都要想一想

  我们设有m个“+”，有n个“-”

  所以正好之和绝对值为x，负号之和绝对值为y，有如下式子：

  x+y=sum，x-y=target

  可以得出x=(sum+target)/2

  也就是说，有(sum+target)/2个正号即当前正号全部加起来为x时可以得到target，转换成01背包就是从数组中拿(sum+target)/2个达到target的重量

• 代码

  int findTargetSumWays(vector<int>& nums, int target) {
      int len = nums.size();
      int sum = std::accumulate(nums.begin(), nums.end(), 0);
      //注意点1：由于(sum+target)/2是表示所有+符号的和，也就是说这个数不能是奇数，必须是偶数
      if((sum < target) || (sum + target) % 2 != 0){
          return 0; 
      }
      int goal = (target + sum) / 2;
      //注意点2：[100],target=-200的情况下，需要判断一下goal的正负
      if(goal < 0){
          return 0;
      }
      vector<vector<int>> dp(len+1, vector<int>(goal+1, 0));
      //dp[i][0]=1因为目标是0的话不选就行，在这里goal表示的是所有+之和所以如果目标是0就是说前i个数全变成负号就行
      dp[0][0] = 1;
      for(int i = 1; i < len + 1; i++){
          for(int j = 0; j < goal +1; j++){
              if(j - nums[i-1] < 0){
                  dp[i][j] = dp[i-1][j];
              }else{
                  dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]; 
              }
          }
      }
      return dp[len][goal];
  }
  

• 注意事项

  在01背包问题中一定要明去dp数组的含义啊。

  比如dp数组代表的是重量，则状态表达式可以是
  $$\begin{gathered} dp[i][j]=dp[i-1][j],j<nums[i-1] \\ dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]]+nums[i-1],j\ge nums[i] \end{gathered}$$
  如果dp数组表示的是组合数，比如dp[i][j]前i个数使得背包重量为j的个数这种，则状态表达式为
  $$\begin{gathered} dp[i][j]=dp[i-1][j],j<nums[i-1] \\ dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]],j\ge nums[i] \end{gathered}$$

思路：把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量。

//用一个两个容量的数组保存0和1的值，绝了！
vector<int> count_one_zero(string& strs){
    vector<int> dp(2, 0);
    int n = strs.size();
    for(int i = 0; i < n; i++){
        if(strs[i] == '0'){
            dp[0]++;
        }
        else if(strs[i] == '1'){
            dp[1]++;
        }
    }
    return dp;
}
int findMaxForm(vector<string>& strs, int m, int n) {
    int len = strs.size();
    vector<vector<vector<int>>> dp(len+1,vector<vector<int>>(m+1,vector<int>(n+1, 0)));
    for(int i = 1;i < len + 1; i++){
        vector<int> count_arr = count_one_zero(strs[i -1]);
        int zero_count = count_arr[0];
        int one_count =  count_arr[1];
        for(int j = 0; j < m + 1; j++){
            for(int w = 0; w < n+1; w++){
                if(j - zero_count >= 0 && w - one_count >= 0){
                    dp[i][j][w] = max(dp[i - 1][j][w],dp[i - 1][j - zero_count][w - one_count]+1);
                }else{
                    dp[i][j][w] = dp[i - 1][j][w];
                }
            }
        }
    }
    return dp[len][m][n];
}

/************************************************************************/
class Solution {
public:
    vector<int> count(string& strs){
        vector<int> vec(2, 0);
        for(auto tmp : strs){
            if(tmp == '0'){
                vec[0]++;
            }
            if(tmp == '1'){
                vec[1]++;
            }
        }
        return vec;
    }

    int findMaxForm(vector<string>& strs, int m, int n) {
        int len = strs.size();
        vector<vector<vector<int>>> dp(len+1, vector<vector<int>>(m+1, vector<int>(n+1, 0)));
        for(int i = 1; i < len + 1; i++){
            vector<int> vec = count(strs[i-1]);
            int zero = vec[0];
            int one = vec[1];
            //易错点2：必须从0开始，所以以后再有这些问题看看是否是从0开始的
            for(int j = 0; j < m + 1; j++){
                for(int z = 0; z < n + 1; z++){
                    //易错点1：必须是或，只要有一个越界就不行
                    if(j-zero < 0 || z - one  < 0){
                        dp[i][j][z] = dp[i-1][j][z];
                    }else{
                        dp[i][j][z] = max(dp[i-1][j][z], dp[i-1][j-zero][z-one] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }
};