代码随想录算法训练营第三十三天|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位置：用于代表楼梯顶端的位置。这不是一个实际的台阶，而是一个达到所有台阶之后的终点位置。通过为这个终点位置分配一个状态，我们可以更简单地计算出达到这一点的最小成本。