概述
动态规划三要素：1.最优子结构：每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到。
2.边界：问题最小子集的解
3.状态转移函数：递推式（一个阶段向另一个阶段过渡）
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
示例1
输入：
2
返回值：
2
复制
说明：
青蛙要跳上两级台阶有两种跳法，分别是：先跳一级，再跳一级或者直接跳两级。因此答案为2
示例2
输入：
7
返回值：
21
分析：边界：f(1)=1,f(2)=2
最优子结构：f(10)的最优子结构是f(9)和f(8)
状态转移函数：f(n)=f(n-1)+f(n-2)
class Solution:
def jumpFloor(self , n: int) -> int:
# write code here
if n<=2:
return n
a=1 #边界
b=2 #边界
tmp=0
for i in range(3,n+1):
tmp=a+b
#状态转移
a=b
#最优子结构
b=tmp #最优子结构
return tmp
最后
以上就是激昂心锁为你收集整理的动态规划：BM63跳台阶的全部内容，希望文章能够帮你解决动态规划：BM63跳台阶所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复