走楼梯——带权值走楼梯（二）

LeetCode_746_MinCostClimbingStairs

题目分析：

和上一题非常类似，只是层楼梯带了权值，并且求解不再是步数，而是最小花费。
现在我们开始试着用动态规划的思路来解决问题。

分析出状态转换方程
  dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1]) 
  dp[i]代表“到达”第i层所需最小花费--不包含cost[i]本身的花费
递推初始项
  dp[0] = dp[1] = 0
  根据dp[i]的含义，结合题意可以从任意第1和第2个位置开始，自然都是0

解法一：递归

/**
 * 关键:
 * 1.可以从0 或者 1位置为起始点！
 * 2.梯顶不是最后一个数 而是最后一个数后一个位置！
 * dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1]) (dp[i]代表“到达”第i层所需最小花费)
 * 自底向上(bottom-up)
 */
public static int minCostClimbingStairs_recursion(int n, int[] cost) {
    if(0 == n || 1 == n)
        return 0;

    return Math.min(minCostClimbingStairs_recursion(n-2, cost) + cost[n-2], minCostClimbingStairs_recursion(n-1, cost) + cost[n-1]);
}

解法二：递归-动态规划

/**
 * 关键:
 * 1.可以从0 或者 1位置为起始点！
 * 2.梯顶不是最后一个数 而是最后一个数后一个位置！
 * dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1]) (dp[i]代表“到达”第i层所需最小花费)
 * 自底向上(bottom-up)
 */
public static int minCostClimbingStairs_dp_recursion(int n, int[] cost, int[] dp) {
    if(0 == n || 1 == n)
        return 0;

    if(0 == dp[n])
        dp[n] = Math.min(minCostClimbingStairs_dp_recursion(n-2, cost, dp) + cost[n-2], minCostClimbingStairs_dp_recursion(n-1, cost, dp) + cost[n-1]);
    return dp[n];
}

解法三：循环-动态规划

/**
 * 关键:
 * 1.可以从0 或者 1位置为起始点！
 * 2.梯顶不是最后一个数 而是最后一个数后一个位置！
 * dp[i] = min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1]) (dp[i]代表“到达”第i层所需最小花费)
 * 自底向上(bottom-up)
 * 改为循环
 */
public static int minCostClimbingStairs_dp_loop(int[] cost) {
    int[] dp = new int[cost.length+1];
    for (int i = 2; i < cost.length + 1; ++i) {
        dp[i] = Math.min(dp[i-2] + cost[i-2], dp[i-1] + cost[i-1]);
    }
    return dp[cost.length];
}

解法四：循环-动态规划-内存优化

/**
 * 关键:
 * 1.可以从0 或者 1位置为起始点！
 * 2.梯顶不是最后一个数 而是最后一个数后一个位置！
 * dp[i] = cost[i] + min(dp[i- 1], dp[i-2]) (dp[i]代表“经过”第i层所需最小花费)
 * 自底向上(bottom-up)
 * 改为循环
 * 优化内存使用(滚动数组---只使用每一轮计算所需的缓存，通常是上一轮或者多轮的结果)
 * 分析可得 只需要两个int变量交替使用即可达到要求
 */
public static int minCostClimbingStairs_dp_otherWay_loop_lessMemory(int[] cost) {
    int temp1 = cost[0];
    int temp2 = cost[1];
    int res = 0;
    for (int i = 2; i < cost.length; ++i) {
        res = cost[i] + Math.min(temp1, temp2);
        temp1 = temp2;
        temp2 = res;
    }
    return Math.min(temp1, temp2);
}

总结

此题的状态装换方程稍有改变，其他都是一样的，
其实套路就是这么明显，只是不同的人的解答方式不同，有的递归，有的循环，有的优化内存了，有的没优化，
但都是动态规划。
举一反三：题目描述变一下，改成捡金币，就是求最大值了，你能做出来吗？

相应例题的 Github