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

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

一、前言


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


二、爬楼梯案例


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.测试代码


4d215fa20db245cbbf12276ab02ba9ae.png


三、斐波那契数案例


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.代码测试


2c0c9d08209240f887f04de5853c71ac.png


四、结语


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

相关文章
|
5月前
|
机器学习/深度学习 存储 算法
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
LeetCode 题目 95:从递归到动态规划实现 不同的二叉搜索树 II
|
5月前
|
缓存
力扣每日一题 6/14 动态规划+数组
力扣每日一题 6/14 动态规划+数组
32 1
|
5月前
|
算法 数据挖掘 开发者
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
LeetCode题目55:跳跃游戏【python5种算法贪心/回溯/动态规划/优化贪心/索引哈希映射 详解】
|
5月前
|
存储 算法 数据可视化
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
深入解析力扣161题:相隔为 1 的编辑距离(逐字符比较与动态规划详解)
|
5月前
|
存储 算法 数据可视化
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
LeetCode 题目 96:从动态规划、递归到卡塔兰数实现不同的二叉搜索树
|
5月前
|
存储 算法 数据可视化
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
LeetCode 132题详解:使用动态规划与中心扩展法解决分割回文串 II 的最少分割次数问题
|
5月前
|
存储 算法 数据可视化
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
LeetCode 131题详解:高效分割回文串的递归与动态规划方法
|
5月前
|
存储 SQL 算法
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
优化解码方法:记忆化搜索和空间优化动态规划的实用指南 【LeetCode 题目 91】
|
5月前
|
算法 索引
力扣每日一题 6/28 动态规划/数组
力扣每日一题 6/28 动态规划/数组
48 0
|
5月前
|
存储
力扣每日一题 6/19 排序+动态规划
力扣每日一题 6/19 排序+动态规划
29 0