【每日算法】动态规划(简单)

简介: 动态规划

16fb98eea012ef0cb446588ddc50662.png

题目

剑指 Offer 10- I. 斐波那契数列

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

示例:

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
复制代码

分析

本题可以算是动态规划题型的基础,基本其它复杂的题目都是由它演变而来,需要牢牢掌握

动态规划的题目我们同样有相应的解题步骤

  • 定义dp数组来表示我们求解的结果

dp = [] ,dp[n] 表示 n 之前两数相加之和

  • 写出状态转移方程

将状态转移方程用dp数组表示

dp(N) =dp(N - 1) + dp(N - 2)

进行初始化

dp[0] = 0, dp[1] = 1

使用迭代计算出结果并返回

实现

function fib(n: number): number {
    let dp = []
    dp[0] = 0
    dp[1] = 1
    let i = 2
    while(i <= n) {
        dp[i] = (dp[i - 1] + dp[i - 2])%1000000007
        i ++
    }
    return dp[n]
};
复制代码

题目

剑指 Offer 10- II. 青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例:

输入:n = 2
输出:2
复制代码

分析

台阶问题也是动态规划的经典题目,将复杂问题转化为简单模型来进行求解

还是按照我们求解动态规划题目的套路来

  • 定义好 dp 数组

dp[n] 表示青蛙跳上 n 级台阶有几种方法

  • 用dp数组写出状态转移方程,第n阶的跳法可以由第n-1阶和第n-2阶的跳法相加得来,即
dp[n] = dp[n-1] + dp[n-2]
  • 初始化 dp 数组
dp[0] = 1;dp[1] = 1; dp[2] = 2; dp[3] = dp[1] + dp[2] = 3
  • 迭代计算结果并返回

实现

function numWays(n: number): number {
    let dp: number[] = []
    dp[0] = 1
    dp[1] = 1
    dp[2] = 2
    let i: number = 3
    while(i <= n) {
        dp[i] = (dp[i-1] + dp[i-2]) % 1000000007
        i++
    }
    return dp[n]
};
相关文章
|
4月前
|
存储 算法
深入了解动态规划算法
深入了解动态规划算法
108 1
|
5天前
|
算法 安全 调度
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
【动态规划篇】穿越算法迷雾:约瑟夫环问题的奇幻密码
|
5天前
|
机器学习/深度学习 算法 测试技术
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
【动态规划篇】01 背包的逆袭:如何用算法装满你的 “财富背包”
|
4月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
1月前
|
算法 Java C++
【潜意识Java】蓝桥杯算法有关的动态规划求解背包问题
本文介绍了经典的0/1背包问题及其动态规划解法。
53 5
|
7月前
|
算法 开发者 Python
惊呆了!Python算法设计与分析,分治法、贪心、动态规划...这些你都会了吗?不会?那还不快来学!
【7月更文挑战第10天】探索编程巅峰,算法至关重要。Python以其易读性成为学习算法的首选。分治法,如归并排序,将大问题拆解;贪心算法,如找零问题,每步求局部最优;动态规划,如斐波那契数列,利用子问题解。通过示例代码,理解并掌握这些算法,提升编程技能,面对挑战更加从容。动手实践,体验算法的神奇力量吧!
87 8
|
3月前
|
算法 Python
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果
在Python编程中,分治法、贪心算法和动态规划是三种重要的算法。分治法通过将大问题分解为小问题,递归解决后合并结果;贪心算法在每一步选择局部最优解,追求全局最优;动态规划通过保存子问题的解,避免重复计算,确保全局最优。这三种算法各具特色,适用于不同类型的问题,合理选择能显著提升编程效率。
87 2
|
4月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
177 2
动态规划算法学习三:0-1背包问题
|
4月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
105 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
4月前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
222 0
动态规划算法学习二:最长公共子序列

热门文章

最新文章