70. 爬楼梯
题目链接：力扣
思路
本题也是动态规划的简单题，但是从这一道题目就可以发现动态规划的难点就在于去发现递推公司，这道题目本质上是一道斐波那契数列，但是发现并不容易，推导起来也不是很好想
题目中要求的每次可以爬1或者2个台阶，也就是说，最终到达n阶台阶有两种方式，一个是爬1阶台阶到达（对应的是从n-1阶台阶开始），那么另一个就是爬2阶台阶到达（对应的是从n-2阶台阶开始爬），而爬n-1阶和n-2阶台阶的方法有dp[n - 1]，dp[n - 2]个。所以最终爬n阶台阶的方法种类就是dp[n -1 ]+dp[n -2]。其实也就是从n-1和n-2阶爬上去，探究的是几种走法，而不是几步
台阶 几种方法
1 1
2 2
3 3
4 5
5 8
从二阶到四阶的那二阶一步和从三阶到四阶的一阶一步本身没有产生新方法，所以是从二阶达到四阶和从三阶达到四阶的两种方式相加
所以推导的过程是：
在到达第n层的上一步，我们只有两个选择，走一步，或者走两步。
如果是走一步，我们需要先通过 f(n-1)种方式到达 n-1 层
如果是走两步， 我们需要通过 f(n-2)种方式到达第 n - 2 层
所以综上有 f(n) = f(n-2) + f(n-1)
至于要如何初始化dp[0] = 1还是dp[1] = 1 .我倒觉得这个不是大问题，只不过是在对代码的意义上的解释不同，dp[1] = 1更能体现出动态思路的意义，dp[0] = 1也没啥问题
爬楼梯
动态规划(优化数组)
class Solution { public int climbStairs(int n) { if (n <= 2) { return n; } // 创建dp数组 int[] dp = new int[3]; // 初始化数组 dp[1] = 1; dp[2] = 2; // 遍历更新数组 for (int i = 3; i <= n; i++) { int sum = dp[1] + dp[2]; dp[1] = dp[2]; dp[2] = sum; } return dp[2]; } }
动态规划(变量替代数组)
class Solution { public int climbStairs(int n) { if (n <= 2) { return n; } int dp1 = 1; int dp2 = 2; for (int i = 3; i <= n; i++) { int temp = dp1 + dp2; dp1 = dp2; dp2 = temp; } return dp2; } }
746. 使用最小花费爬楼梯
题目链接：力扣
思路
确定dp数组、确定递推公式、初始化dp真的是不容易呀
1、明确数组
本体要求的是爬到某一台阶需要的最小花费，随意我们明确dp[]数组为 最小花费数组，其中下标i上的数代表到大第 i 层台阶需要花费的最小费用为 dp[i]
2、递推公式
数组明确之后，就是考虑怎么获取数组中的值，也就是怎么求取每个台阶的最小花费值。这里dp[i] 是有两种情况的
第一种情况是从前一个台阶跳上来，那最小花费 = 到达前一个台阶的最小花费 + 前一个台阶对应的费用，也就是 dp[i] = dp[i - 1] + cost[i - 1]
第二种情况是从前两个台阶跳上来，那最小花费 = 到达前两个台阶的最小花费 + 前两个台阶对应的费用，也就是 dp[i] = dp[i - 2] + cost[i - 2]
那这两种情况中最小的，就是我们要求的当前台阶对应的最小的费用
3、初始化dp数组
首先要明确一点就是，当站在下标【0】和下标【1】的时候是不消耗费用的，只有向上跳才会消耗费用，所以这里的初始化是比较重要的，要不然后面的结果也就不同了
使用最小花费爬楼梯
动态规划(使用数组)
class Solution { public int minCostClimbingStairs(int[] cost) { // 定义数组 int[] dp = new int[cost.length + 1]; // 初始化数组 dp[0] = 0; dp[1] = 0; // 遍历填充dp数组 for (int i = 2; i < dp.length; i++) { dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i -2] + cost[i-2]); } return dp[cost.length]; } }
动态规划(使用变量)
class Solution { public int minCostClimbingStairs(int[] cost) { // 初始化 int dp0 = 0; int dp1 = 0; // 遍历更新 for (int i = 2; i <= cost.length; i++) { int dpi = Math.min(dp1 + cost[i-1],dp0 + cost[i-2]); dp0 = dp1; dp1 = dpi; } return dp1; } }
