一、前言
在解决一些题目时，常常看到大佬们讨论用“动态规划”来解决问题，听着非常厉害，代码也非常简洁，但是自己碰到题目时却不知道如何下手，本文将通过两道简单的力扣真题带你入门动态规划
二、爬楼梯案例
1.题目
LeetCode70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1 阶 + 1 阶
2 阶
示例 2： 输入：n = 3 输出：3
解释：有三种方法可以爬到楼顶。
1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶
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]; } }
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]; } }
4.代码测试
四、结语
本文的题目都是力扣里面简单的有关动态规划的题目，接下来的题目会较难一点，是进阶版动态规划的题目。如果文中有错误，欢迎在评论区指出
