一、前言
在解决一些题目时,常常看到大佬们讨论用“动态规划”来解决问题,听着非常厉害,代码也非常简洁,但是自己碰到题目时却不知道如何下手,本文将通过两道简单的力扣真题带你入门动态规划
二、爬楼梯案例
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.代码测试
四、结语
本文的题目都是力扣里面简单的有关动态规划的题目,接下来的题目会较难一点,是进阶版动态规划的题目。如果文中有错误,欢迎在评论区指出