题解 | #64.最小花费爬楼梯#

dp dp 你看我长得像dp吗？ 刚抄了一道题，还是不太懂dp，dp难dp易，dp就是放狗屁，快点去下地

可以用一个数组记录每次爬到第i阶楼梯的最小花费，然后每增加一级台阶就转移一次状态，最终得到结果

每次到一个台阶，只有两种情况，要么是它前一级台阶向上一步，要么是它前两级的台阶向上两步，因为在前面的台阶花费我们都得到了，因此每次更新最小值即可，转移方程为：$dp[i]=min(dp[i\mathrm{-}1]+cost[i\mathrm{-}1],dp[i\mathrm{-}2]+cost[i\mathrm{-}2])dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])$

function minCostClimbingStairs( cost ) {
  /*
  *  dp数组记录每次爬到第i阶楼梯的最小花费
  *  dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
  *  dp[0] = 0  dp[1] = 0;
  *
  */
  let dp = [0,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];
}