算法训练营day33 | {509.斐波那契数, 70.爬楼梯, 746.使用最小花费爬楼梯}

第九章动态规划part01，用动态五部曲分析问题，打通雾霭。

0. 理论基础

动态规划（Dynamic Programming），简称DP，用DP解决问题是从前一个状态推导出来的，而贪心是局部直接选最优的。

0.1 动态规划五部曲

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

0.2 动态规划debug

做动规的题目，写代码之前一定要把状态转移在dp数组上模拟一遍，心中有数是想要的结果；然后写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样：

  • 如果不一样那就是代码实现细节有问题；
  • 如果一样，那就是自己的递推公式、初始化或者遍历顺序出问题了。

0.3 动态规划刷题大纲

DP刷题

509. 斐波那契数

1.1 解题分析

动规五部曲：

  1. 确定dp数组以及下标的含义：dp[i]的定义为下标为i的斐波那契数列数值是dp[i]
  2. 确定递推公式：dp[i] = dp[i - 1] + dp[i - 2]
  3. dp数组如何初始化: dp[0] = 0, dp[1] = 1
  4. 确定遍历顺序: 因为dp[i]依赖dp[i - 1]和dp[i - 2]，所以从前往后遍历
  5. 举例推导dp数组: 0 1 1 2 3 5 8 13 …
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

进一步，因为本题只要求dp[n]，可以进行状态压缩，只维护两个数值就可以了，不需要记录整个序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        if (n == 0 || n == 1) return n;
        int[] dp = new int[2];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];;
            dp[1] = sum; 
        }
        return dp[1];
    }
}

70. 爬楼梯

2.1 解题分析

动规五部曲：

  1. 确定dp数组以及下标的含义：dp[i]的定义为爬到第i层楼梯有dp[i]种不同的方法
  2. 确定递推公式：dp[i] = dp[i - 1] + dp[i - 2]
  3. dp数组如何初始化: dp[1] = 1, dp[2] = 2
  4. 确定遍历顺序: 因为dp[i]依赖dp[i - 1]和dp[i - 2]，所以从前往后遍历
  5. 举例推导dp数组: 1 2 3 5 8 13 …
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

746. 使用最小花费爬楼梯

3.1 解题分析

动规五部曲：

  1. 确定dp数组以及下标的含义：dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]
  2. 确定递推公式：dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
  3. dp数组如何初始化: dp[0] = 0 dp[1] = 0
  4. 确定遍历顺序: 因为dp[i]依赖dp[i - 1]和dp[i - 2]，所以从前往后遍历
  5. 举例推导dp数组: 例如cost[]数组[10,15,20]：0 0 10 15
1
2
3
4
5
6
7
8
9
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int[] dp = new int[cost.length + 1];
        for (int i = 2; i <= cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.length];
    }
}
Leetcode > 动态规划
#Java #代码随想录
算法训练营day33 | {509.斐波那契数, 70.爬楼梯, 746.使用最小花费爬楼梯}
http://paopaotangzu.xyz/cn/day33_leetcode/
作者
PROTON TANG
发布于
2026年1月19日
许可协议