导读：今天首席CTO笔记来给各位分享关于python多少种上台阶的方式的相关内容，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
python动态规划及编辑距离计算实例
动态规划的三要素:最优子结构,边界和状态转移函数,最优子结构是指每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到(子问题的最优解能够决定这个问题的最优解),边界指的是问题最小子集的解(初始范围),状态转移函数是指从一个阶段向另一个阶段过度的具体形式,描述的是两个相邻子问题之间的关系(递推式)
重叠子问题,对每个子问题只计算一次,然后将其计算的结果保存到一个表格中,每一次需要上一个子问题解时,进行调用,只要o(1)时间复杂度,准确的说,动态规划是利用空间去换取时间的算法.
判断是否可以利用动态规划求解,第一个是判断是否存在重叠子问题。
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
分析:
假定n=10,首先考虑最后一步的情况,要么从第九级台阶再走一级到第十级,要么从第八级台阶走两级到第十级,因而,要想到达第十级台阶,最后一步一定是从第八级或者第九级台阶开始.也就是说已知从地面到第八级台阶一共有X种走法,从地面到第九级台阶一共有Y种走法,那么从地面到第十级台阶一共有X+Y种走法.
即F(10)=F(9)+F(8)
分析到这里,动态规划的三要素出来了.
边界:F(1)=1,F(2)=2
最优子结构:F(10)的最优子结构即F(9)和F(8)
状态转移函数:F(n)=F(n-1)+F(n-2)
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n=2:
return n
a=1#边界
b=2#边界
temp=0
for i in range(3,n+1):
temp=a+b#状态转移
a=b#最优子结构
b=temp#最优子结构
return temp
利用动态规划的思想计算编辑距离。
编辑距离是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。通常来说，编辑距离越小，两个文本的相似性越大。这里的编辑操作主要包括三种：
插入：将一个字符插入某个字符串；
删除：将字符串中的某个字符删除；
替换：将字符串中的某个字符替换为另外一个字符。
那么，如何用Python计算编辑距离呢？我们可以从较为简单的情况进行分析。
当两个字符串都为空串，那么编辑距离为0；
当其中一个字符串为空串时，那么编辑距离为另一个非空字符串的长度；
当两个字符串均为非空时(长度分别为 i 和 j )，取以下三种情况最小值即可：
1、长度分别为 i-1 和 j 的字符串的编辑距离已知，那么加1即可；
2、长度分别为 i 和 j-1 的字符串的编辑距离已知，那么加1即可；
3、长度分别为 i-1 和 j-1 的字符串的编辑距离已知，此时考虑两种情况，若第i个字符和第j个字符不同，那么加1即可；如果相同，那么不需要加1。
很明显，上述算法的思想即为 动态规划 。
求长度为m和n的字符串的编辑距离，首先定义函数——edit(i, j)，它表示第一个长度为i的字符串与第二个长度为j的字符串之间的编辑距离。动态规划表达式可以写为：
if i == 0 且 j == 0，edit(i, j) = 0
if （i == 0 且 j 0 ）或者 （i 0 且j == 0），edit(i, j) = i + j
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + d(i, j) }，当第一个字符串的第i个字符不等于第二个字符串的第j个字符时，d(i, j) = 1；否则，d(i, j) = 0。
def edit_distance(word1, word2):
len1 = len(word1)
len2 = len(word2)
dp = np.zeros((len1 + 1,len2 + 1))
for i in range(len1 + 1):
dp[i][0] = i
for j in range(len2 + 1):
dp[0][j] = j
for i in range(1, len1 + 1):
for j in range(1, len2 + 1):
delta = 0 if word1[i-1] == word2[j-1] else 1
dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))
return dp[len1][len2]
edit_distance('牛奶','华西奶')
结果：2
楼梯有15级台阶，可以一次走一级，两级或三级，一共有多少种不同的走法
设到第n级台阶有f(n)种走法，则
f(1)=1,f(2)=2,f(3)=4,n=4时
f(n)=f(n-1)+f(n-2)+f(n-3),
您可以编程，求f(15).繁！
楼梯有n阶,可以一步上一阶,两阶,问有多少种不同的走法python语言
def fib_recur(n):
assert n = 0, "n 0"
if n = 1:
return n
return fib_recur(n-1) + fib_recur(n-2)
for i in range(1, 20):
print(fib_recur(i), end=' ')
python3.x编程
def f(n,m):
if (n!=0):
c = 0
if (nm):
for i in range(n-m,n):
c = c + f(i,m)
return c;
else:
for i in range(n):
c = c+f(i,n)
return c;
else:
return 1;
第7行的缩进调了一下
一个楼梯有10阶台阶，每次只能上1级或者2级，走完这10级台阶共有多少种走法？
89种。
递推：
登上第1级：1种
登上第2级：2种
登上第3级：1+2=3种（前一步要么从第1级迈上来，要么从第2级迈上来）
登上第4级：2+3=5种（前一步要么从第2级迈上来，要么从第3级迈上来）
登上第5级：3+5=8种
登上第6级：5+8=13种
登上第7级：8+13=21种
登上第8级：13+21=34种
登上第9级：21+34=55种
登上第9级：55+34=89种
答：一共可以有89种不同的走法。
应用题是用语言或文字叙述有关事实，反映某种数学关系（譬如：数量关系、位置关系等），并求解未知数量的题目。每个应用题都包括已知条件和所求问题。
以往，中国的应用题通常要求叙述满足三个要求：无矛盾性，即条件之间、条件与问题之间不能相互矛盾；完备性，即条件必须充分，足以保证从条件求出未知量的数值；独立性， 即已知的几个条件不能相互推出。
小学数学应用题通常分为两类：只用加、减、乘、除一步运算进行解答的称简单应用题；需用两步或两步以上运算进行解答的称复合应用题。
python爬楼梯求至少多少阶梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。1 阶 + 1 阶 和 2 阶
解题思路：
实现了两种方法，但是第一种超出时间限制(｡ì _ í｡)，因为递归的时候方法实际计算了两次。两种方法都使用了动态规划思想，比如对于爬10阶楼梯，我们最后一步爬上第10阶只会有两种情况，一种是从9阶楼梯爬1个台阶，一种是从8阶台阶爬2两个台阶上来。所以10阶台阶问题可以划分为爬9阶和8阶两个子问题，一直递归划分到只剩2阶(2种方法)和1阶(一种方法)。
超出时间限制的代码：
class Solution:
def climbStairs(self, n: int) - int:
if n=2:
if n==2:
结语：以上就是首席CTO笔记为大家整理的关于python多少种上台阶的方式的全部内容了，感谢您花时间阅读本站内容，希望对您有所帮助，更多关于python多少种上台阶的方式的相关内容别忘了在本站进行查找喔。