代码随想录算法训练营第三十三天|509. 斐波那契数 ，● 70. 爬楼梯 ， 746. 使用最小花费爬楼梯

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

代码随想录

视频：从此再也不怕动态规划了，动态规划解题方法论大曝光 ！| 理论基础 |力扣刷题总结| 动态规划入门_哔哩哔哩_bilibili

 509. 斐波那契数 

代码随想录

视频：手把手带你入门动态规划 | LeetCode：509.斐波那契数_哔哩哔哩_bilibili

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

 70. 爬楼梯   

代码随想录

视频：带你学透动态规划-爬楼梯（对应力扣70.爬楼梯）| 动态规划经典入门题目_哔哩哔哩_bilibili

class Solution {public int climbStairs(int n) {//1.确定dp数组（dp table）以及下标的含义: dp[i]达到i阶有dp[i]种方法//2.确定递推公式：dp[i] = dp[i - 1] + dp[i - 2]//3.dp数组如何初始化: dp[0] = 1,(意义上说不通，代码跑的通) 所以，dp[1] = 1， dp[2] = 2//4.确定遍历顺序： 从前往后，因为后面要依赖前面的//5.举例推导dp数组： 查错int arr[] = new int[n];int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for (int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

 746. 使用最小花费爬楼梯 

代码随想录

视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯_哔哩哔哩_bilibili

class Solution {public int minCostClimbingStairs(int[] cost) {//(站上面不花钱，开始跳才花钱)// 确定dp数组（dp table）以及下标的含义： 到达i的位置所需要的花费dp[i]// 确定递推公式： dp[i] = dp[i - 1] + cost[i - 1] / dp[i - 2] + cost[i - 2]// dp数组如何初始化: dp[1] dp[0]// 确定遍历顺序: 从前到后，后面的元素是依据前面的元素推导的// 举例推导dp数组int arr[] = new int[cost.length + 1];arr[0] = 0;arr[1] = 0;for (int i = 2; i < arr.length; i++) {arr[i] = Math.min(arr[i - 1] + cost[i - 1], arr[i - 2] + cost[i - 2]);}return arr[cost.length]; }
}

解释cost.length + 1

• 数组长度为cost.length：表示楼梯的每一步都有一个上升的成本。但是，这个数组不直接提供到达楼梯顶部（即最后一个台阶之后的位置）的成本。
• 额外的+ 1位置：用于代表楼梯顶端的位置。这不是一个实际的台阶，而是一个达到所有台阶之后的终点位置。通过为这个终点位置分配一个状态，我们可以更简单地计算出达到这一点的最小成本。