两道力扣真题带你入门动态规划

一、前言

在解决一些题目时，常常看到大佬们讨论用“动态规划”来解决问题，听着非常厉害，代码也非常简洁，但是自己碰到题目时却不知道如何下手，本文将通过两道简单的力扣真题带你入门动态规划

二、爬楼梯案例

1.题目

LeetCode70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2： 输入：n = 3 输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

2.分析

• 首先我们来定义一下，设dp[n]的含义为：跳上n阶楼梯一共有dp[n]种方法
• 定义一个数组来记录历史数据，由于n从0开始计数，所以数组的长度为 n+1
• 假设最后一阶楼梯是dp[n]的话，有两种方式可以到达，一种是跨两阶楼梯，从dp[n-2]到达，另一种是跨一阶楼梯，从dp[n-1]到达，即 dp[n] = dp[n-1] + dp[n-2]
• 但是如果 n=0 或 n=1 时n-1或n-2就为负数了，所以要将dp[0]和dp[1]赋值，当只有一阶楼梯或者没有楼梯的时候，只有一种方法，所以 dp[0] = dp[1] = 1
• 返回 dp[n] 的值

3.代码实现

class Solution {
    public int climbStairs(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];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

4.测试代码

三、斐波那契数案例

1.题目

LeetCode509. 斐波那契数
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给定 n ，请计算 F(n) 。

示例 1：
输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：
输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：
输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

2.分析

• 和上一题一样，要先定义dp[n]：代表F(n)，即输出的数
• 定义一个数组来记录历史数据，由于n从0开始计数，所以数组的长度为 n+1
• 给定的 dp[0] = 0，dp[1] = 1，即dp[n] = n
• 由题目可以知道， dp[n] = dp[n-1] + dp[n-2]
• 返回dp[n]的值

3.代码实现

class Solution {
    public int fib(int n) {
        //为提高代码效率，所以直接返回值可以不用经过下列的操作
        if(n <= 1){
            return n;
        }
        //定义数组，存储历史数据
        int[] dp = new int [n+1];
        //由于数组内每个下标要用对应值，所以要再初始化一遍
        dp[0] = 0;
        dp[1] = 1;
        //求数
        for(int i = 2; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        //返回求出来的数
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

4.代码测试

四、结语

本文的题目都是力扣里面简单的有关动态规划的题目，接下来的题目会较难一点，是进阶版动态规划的题目。如果文中有错误，欢迎在评论区指出