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
