动态规划思想

  • 将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
  • 对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。
  • 动态规划算法将问题的解决方案视为一系列决策的结果。

DP数组应该保存什么？

题目要求解爬到楼梯顶部的最低花费，这个最低花费和前面台阶的最低花费有关，因此DP数组应该保存每个台阶的最低花费。

最优子结构

最终台阶的最低花费可以由前面台阶的最低花费得出。

最小子问题

  • cost[i]表示的是从第i个台阶向上爬需要支付的费用，而不是登上第i个台阶所需要的最低花费。而初始时只能选择第0个或者第1个台阶，最小子问题为第0个和第1个台阶的最低花费，DP数组需要先计算出这两个子问题的结果。
  • 由于可以直接从第0个或第1个开始，因此这两个台阶的花费都直接为0。

如何思考状态转移方程？

由自顶向下思路分析，思考当前状态是如何由前面状态得到的。当前台阶要么是由前一级台阶向上一步得到，要么是由前两级台阶向上两步得到，因此当前台阶的最低花费应该是前面两种情况花费的最小值。状态转移方程为：$dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])$

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param cost int整型一维数组 
 * @return int整型
 */
function minCostClimbingStairs( cost ) {
    // write code here
    let dp = new Array(cost.length).fill(0);

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

    return dp[cost.length];
}
module.exports = {
    minCostClimbingStairs : minCostClimbingStairs
};