动态规划

动态规划： 「Dynamic Programming」

• 198. 打家劫舍 I
• 198. 打家劫舍 II
• 面试题 17.16. 按摩师
• 746. 使用最小花费爬楼梯
• 740. 删除并获得点数

以上三个问题都是 dp 的一类问题，解法也一样。

dp 的解题思路最重要的就是寻找「状态转移方程」

状态转移方程往往依赖上一个结果的计算值：比如 斐波那契 以及 杨辉三角

对于「斐波那契」

f(n) = f(n - 1) + fn(n - 2)

对于「杨辉三角」(排除边界 case 1)

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

动规总能以一个数学公式进行表达

但 这并不是动规的精髓所在，寻在「状态转移方程」往往需要寻找「最优子结构」：可以从子问题的最优结果推出更大规模问题的最优结果。

刷了一些题目之后就会发现：基本上就是从一个小规模内求一个最大最小值。「一看就会，一写就废」

以 「使用最小花费爬楼梯」为例：

1. 爬楼梯要么从第 0 步 开始，要么从 第 1 步开始。
2. 对于第 i 次解决方案而言，要么是从 i - 1 过来，要么是从 i - 2 过来。那么 dp[i] 的最优解为

dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i]

3. 对于结果而言，要么是从最后一步，要么是从前两步过来，因为最优的结果是：

Math.min(dp[dp.length - 2], dp[dp.length - 1])

/**
 * @param {number[]} cost
 * @return {number}
 */
var minCostClimbingStairs = function(cost) {
  if (!cost || !cost.length) {
    return 0
  }
  let dp = []
  dp[0] = cost[0]
  dp[1] = cost[1]

  for (var i = 2; i < cost.length; i++) {
    dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i]
  }
  return Math.min(dp[dp.length - 2], dp[dp.length - 1])
}