leetcode 刷题 log day 46（背包总结篇

• 139. 单词拆分
  【思路】s 看作背包，wordDict 里的每个元素看作物品，看是否能放满背包，因为可以重复选择元素，所以为完全背包问题。截取 s 中与 wordDict 元素相同长度的字符串，然后比对，如果相同，则为 true。

  var wordBreak = function(s, wordDict) {
      let dp = new Array(s.length + 1).fill(false);
      dp[0] = true;
  
      for (let i = 0; i <= s.length; i++) {
          for (let j = 0; j < wordDict.length; j++) {
              if (i >= wordDict[j].length) {
                  if (s.slice(i - wordDict[j].length, i) === wordDict[j] && dp[i - wordDict[j].length]) dp[i] = true 
              }
          }
      }
  return dp[s.length];
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13

【背包总结】

• 动规五部曲
  1. 确定 dp 数组及其下标的含义；
  2. 确定递推公式；
  3. dp 数组如何初始化；
  4. 确定遍历顺序；
  5. 举例推导 dp 数组

• 确定地推公式

  • 问能否装满背包或最多装多少：dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i])
  • 问装满背包有几种方法：dp[j] += dp[j - nums[i]]
  • 问装满背包最大价值：dp[j] = Math.max(dp[j], dp[j - nums[i]] + value[i])
  • 问装满背包所需的最少数量：dp[j] = Math.min(dp[j], dp[j - conis[i]] + 1)

• 遍历顺序

  • 01 背包： 二维数组解法中，先遍历物品和先遍历背包都可以，且第二层 for 循环是从前到后遍历，一维滚动数组是必须先遍历物品后遍历背包，且背包从后往前遍历；
  • 完全背包求个数： 先遍历背包或先遍历物品都可以，且内层循环从左往右遍历；
  • 完全背包求组合： 先遍历物品后遍历背包；
  • 完全背包求排列： 先遍历背包后遍历物品；