动态规划简单例题_动态规划经典题目python?

一.什么是动态规划

动态规划是一种解决复杂问题的方法，它将复杂问题分解为一系列更简单的子问题，每个子问题只解决一次，并存储它们的解。

二.动态规划组成部分

1.确定状态

简单的说，解动态规划的时候需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么。确定状态需要最后一步以及子问题两个基础。

2.转移方程

一般为列表元素的等式

3.初始条件和边界情况

需要具体考虑问题中的限制因素

4.计算顺序

利用循环、双循环计算

三.动态规划案例问题1

1.问题描述

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

2.思路分析

以列表f[i]代表青蛙走到第i+1阶台阶(列表第一个元素检索为0)有几种跳法；那么青蛙跳上第n阶台阶的最后一步一定跳了1级或者2级，那么总跳法f[i]=f[i-2]+f[i-1]，初始条件f[0]=1，利用for循环求解计算。

3.代码实现

n=int(input())
f=[]
for i in range(n):
    f.append(0)
f[0]=1
f[1]=2

if n==1:
    print(1)
elif n==2:
    print(2)
else:
    for i in range(2,n):
        f[i]=f[i-2]+f[i-1]
    print(f[n-1])

后续我将由浅入深地继续更新Python动态规划案例问题。

四.结语

作为小白一枚，记录自己的成长，分享出来，欢迎大佬指正。