【代码随想录训练营】【Day38】第九章｜动态规划｜理论基础｜509. 斐波那契数｜70. 爬楼梯｜746. 使用最小花费爬楼梯

理论基础

动态规划与贪心的区别并不是学习动态规划所必须了解的，所以并不重要。

想要了解动态规划算法题的特点，可以直接做下面三道入门简单题练练手感，找找感觉，很快就能体会到动态规划的解题思想。

总结成一句话就是：动态规划就是利用已知解求未知解，利用之前得到的结果得到下一个结果的过程。

详细的基础理论知识可查阅：《代码随想录》— 动态规划 — 理论基础

---

斐波那契数

题目详细：LeetCode.509

动态规划入门题，详细的题解可查阅：《代码随想录》— 斐波那契数

Java解法（动态规划）：

class Solution {public int fib(int n) {if(n < 2){return n;}int[] dp = new int[n + 1];dp[0] = 0;dp[1] = 1;for(int i = 2; i < n + 1; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

---

爬楼梯

题目详细：LeetCode.70

动态规划入门题，思路和解法跟上一题斐波那契数很相似，详细的题解可查阅：《代码随想录》— 爬楼梯

Java解法（动态规划）：

class Solution {public int climbStairs(int n) {if(n < 3){return n;}int[] dp = new int[n + 1];dp[1] = 1;dp[2] = 2;for(int i = 3; i < n + 1; i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

---

使用最小花费爬楼梯

题目详细：LeetCode.746

又是一道简单题，练手非常过瘾，解题思路也十分简单，由题可知：

• 爬楼梯可以从下标为0或1的台阶开始爬楼梯
• 每一次花费后，可选择向上爬一个或者两个台阶

如果那么根据规律，假如我们爬上第三个台阶，会有两种情况：

• 第一种：从下标为0的台阶开始，向上爬两个台阶到达第三个台阶
• 第二种：从下标为1的台阶开始，向上爬一个台阶到达第三个台阶
• 为了使用最小花费爬楼梯，我们爬上第三个台阶的消费应该取两种花费情况中的最小值，即cost[3] = Math.min(cost[1] + cost[3], cost[2] + cost[3]);
• 同理我们可以得到后序各个台阶花费情况，即本题的递推公式为cost[i] = Math.min(cost[i - 1] + cost[i], cost[i - 2] + cost[i]);

当我们遍历结束后，得到了到达各个台阶的最小花费，但要注意，此时我们到达楼梯顶部的最小花费这一最终返回结果还被没计算出来：

• cost[cost.length - 1]的值仅表示到达第cost.length - 1个台阶的最小花费而已
• cost[cost.length - 2]的值仅表示到达第cost.length - 2个台阶的最小花费而已
• 那么当我们到达第cost[cost.length - 1]或 cost[cost.length - 2]个台阶后，也可以选择向上爬一个或者两个台阶
• 所以我们最后还需要通过比较cost[cost.length - 1]和cost[cost.length - 2]，取两者之间的最小值来作为到达楼梯顶部的最小花费

Java解法（动态规划）：

class Solution {public int minCostClimbingStairs(int[] cost) {for(int i = 2; i < cost.length; i++){cost[i] = Math.min(cost[i - 1] + cost[i], cost[i - 2] + cost[i]);}return Math.min(cost[cost.length - 1], cost[cost.length - 2]);}
}

---