动态规划解题思路

动态规划的前身

动态规划一般来说都是用于求最值问题，比如最长增长子序列，最小移动距离等等，求最值那一定是要得到所有的答案，然后再从中找出最大值或者最小值，这是毋庸置疑的。

但是求最值的过程中，往往会涉及到很多子问题，比如最长公共子序列问题，最短路径问题，背包问题等等；出现重复计算的过程，动态规划的思想就是把这些子问题的解存储下来，避免重复计算，从而提高效率。

我们怎么把子问题和当前问题关联起来，就是动态规划的核心。

所以动态规划一般的思路如下：

• 确定 dp 的含义，这个一般和题目要求相关，比如最长增长子序列， dp[i] 表示以 i 结尾的最长子序列的长度。
• 确定基础状态，这个一般是 dp[0] = 0，表示空字符串的最长子序列长度为 0。
• 确定状态转移方程，这个步骤一般涉及子问题的拆解，就是这个题目中，我们暴力解法的时候哪些步骤是重复的

动态规划的核心是要知道暴力解法是怎么处理的，然后分析重叠子问题，从而写出状态转移方程。

暴力解法

比如背包问题，我们要暴力穷举所有的组合场景，得到所有的结果才能知道那个答案是最佳，可以先用回溯的模板处理

/**
 * @param {number[]} weights
 * @param {number[]} values
 * @param {number} bagW
 */
var forcePackage = function(weights,values,bagW) {
  let used = []
  let totalWeight = 0
  const res = []
  function backtrace(index) {
    if (totalWeight > bagW) {
      // 存储本次结果
      res.push(...used)
      // 回溯结束
      used = []
      totalWeight = 0
      return
    }
    used.push(weights[index])
    totalWeight+=weights[index]
    for(let i = 0;i<weights.lenght) {
      // 不允许重复拿
      if (used.incudes(weights(i))) continue
      backtrace(i)
    }
  }
}

回溯求的是排列，我们题目要求的是组合，因为是计算物品的最大价值，与顺序无关，那么回溯就多出：

• 重复的排列，比如 我们物品1,2,3的重量有 [3，4，5]，价值[1,3,2],那么回溯就可能 6 种相同的计算，而我们实际只需要其中一种结果，我们可以假设，如果没有放物品 3，物品1 和 2 最大价值就是 4。
• 在放某物品的场景下，背包减去物品重量还能装的价值和不放的场景相比，取最大值，就不需要重复计算体积小的时候的数值