python跳台阶问题(python爬楼梯问题)
n级台阶，一次了以上123级中一种，枚举所有上楼梯可能性，python实现
可以用枚举法和归纳法来解答。
一、枚举法
11级台阶，如果每次跨2级，最多可跨5次。所以，可以分六种情况来考虑：
1、每次都只跨一级台阶，这样的走法只有1种。
2、有一次跨二级台阶，其余每次都跨一级台阶，这样的走法有10=种。
3、有两次跨二级台阶，其余每次都跨一级台阶，这样的走法有8+7+6+5+4+3+2+1=36种。
4、有三次跨二级台阶，其余每次都跨一级台阶，这样的走法有（6+5++4+3+2+1）+（5+4++3+2+1）+（4+3+2+1）+（3+2+1）+（2+1）+1=56种。
5、有四次跨二级台阶，其余每次都跨一级台阶，这样的走法有36种。（算式略）
6、有五次跨二级台阶，其余每次都跨一级台阶，这样的走法有6种。
所以，一共有1+10+36+56+35+6=144=
Python 独立跳棋问题的算法思路是什么？
这么好玩的算法。为什么不自己先试试呢。
你的问题里没有描述规则，所以我猜想，它应该是按跳棋的规则去跳，然后达到另外一个规则标准就会消除。
正常的做法，比较费时的做法是尝试每一种可能路径，通常是有深度的。比如尝试10步，或者是100步。然后评估结果。
不过可以通过自己的经验，让路径的选择变得简单。 减少规则推演的次数与深度。
这些都是最简单的逻辑。不过运畴学，还有一个什么什么科学是专门用来做这种棋路推演的。 你可以找教材书看一下。
或者是最简单的办法，找师兄师姐的论文看看。
如果是我自己做这种题目，我会采用“双向”推演，加上排除法，还有透视逻辑做。
另外为了提高效率，我会事先生成一个所有棋 路的最小生成树。这样可以减化“搬”动棋子的时间。
11届国赛python试题 J: 蓝跳跳
【问题描述】
小蓝制作了一个机器人，取名为蓝跳跳，因为这个机器人走路的时候基本靠跳跃。
蓝跳跳可以跳着走，也可以掉头。蓝跳跳每步跳的距离都必须是整数，每步可以跳不超过 k 的长度。由于蓝跳跳的平衡性设计得不太好，如果连续两次都是跳跃，而且两次跳跃的距离都至少是 p，则蓝跳跳会摔倒，这是小蓝不愿意看到的。
小蓝接到一个特别的任务，要在一个长为 L 舞台上展示蓝跳跳。小蓝要控制蓝跳跳从舞台的左边走到右边，然后掉头，然后从右边走到左边，然后掉头，然后再从左边走到右边，然后掉头，再从右边走到左边，然后掉头，如此往复。为了让观者不至于太无趣，小蓝决定让蓝跳跳每次用不同的方式来走。小蓝将蓝跳跳每一步跳的距离记录下来，按顺序排成一列，显然这一列数每个都不超过 k 且和是 L。这样走一趟就会出来一列数。如果两列数的长度不同，或者两列数中存在一个位置数值不同，就认为是不同的方案。
请问蓝跳跳在不摔倒的前提下，有多少种不同的方案从舞台一边走到另一边。
【输入格式】
输入一行包含三个整数 k, p, L。
【输出格式】
输出一个整数，表示答案。答案可能很大，请输出答案除以 20201114 的余数。
【样例输入】
3 2 5
【样例输出】
9
【样例说明】
蓝跳跳有以下 9 种跳法：
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
2+1+1+1
2+1+2
1+1+3
1+3+1
3+1+1
【样例输入】
5 3 10
【样例输出】
397
这种题可以用递归的DFS解也可以用动态规划，相比较经典的递归走台阶问题，由于题目没有限定第一步跳的种类，所有导致有多种方法。递归之后也是无法求解;递归无法求解的题目。因为重复计算。计算规模o(L的k次方)，所以采用了动态规划+递推做的此题，我们可以建立一个2维数组dp[i][j] 。
i 表示舞台距离，j表示第一次跳j格时。 dp[i][j]表示我当前步数用j步走 可以多少种方法走到i。
p意思就是连续跳大于等于p时就会摔倒。
d[i][j]i跳数的取值范围0-K
j的取值范围是0-L
规律描述：当舞台长度为1时，我第一步为1时dp[1][1]=1 种方法 当第一步为2时 d[1][2]=0种。当第一步为3时dp[1][3]=0种。
当舞台长度为2时，我第一步为1时dp[2][1]=1种方法 当第一步为2时dp[2][2]=1种。当第一步为3时dp[2][3]=0种.
当我们得到长度为2 第一步为1时， 我当前的长度减1 剩余舞台长度为1，我们可以看到舞台为1的时候一共只有1种方法那么当长度为dp[1][1]+dp[1][2]+dp[1][3]=dp[2][1]=1 第一步为1时就是一种方法。因为当跳的步数和长度相等的时候只有一种方法 dp[2][2]=1。
如果连续两次都是跳跃，而且两次跳跃的距离都至少是 p，我们知道j是第一种跳法，k就是第2个选择的跳法所以 j=b 分为二种转移方程，
当j=b , 说明我们第一次跳了大于p的距离如果我们第二次在大于p那么蓝跳跳将会摔倒所以我们dp[4][2]+=dp[2][1] 不可以选择dp[2][2]和dp[2][3]
那么转移方程得：dp[i][j]+=dp[i-j][k]
当第一次小于p的长度，我们第二次就把所有可能选择上dp[4][1]=dp[3][1]+dp[3][2]+dp[3][3]
那么转移方程得：dp[i][j]+=sum(dp[i-j])。
但是这种不是最优解最多跑80%的数据。
创建一个双层的循环数组，0层存jb的方式个数，1层存bp+1方式个数。和上面方法差不多只不过是以双层的格式存储，这样可以少很多的计算量。
我们先把已知的数据写入二维数据中dp[1][0]=1，然后遍历2,s+1和1,p+1,因为当s=0时 方法只有一种。把dp[0][1]=1 或者dp[0][0]=1 我只是把这个当上面方法dp[i][j]+=1用了。
这个转移方程也是2个，一个 (1,b) 和(b,p+1) 把jb 存在dp[i][0] bp+1存在dp[i][1]。
转移方程分别为 dp[i][0]+=dp[i-j][1]+dp[i-j][0]， dp[i][1]+=dp[i-j][0]。
这种就可以把数据跑完了计算量把上个方法少了很多。
用python编程，一球从100米高度自由落下，每次落地后反跳回原高度的一半再落下。
high?=?100
n?=?10
high_all?=?0?#第n次落地时走过的长度
high_each?=?0?#每次落地的高度
def?ball_lands(n):
????global?high_all,?high_each,?high
????#小球第一次落地时
????if?n?==?0:
????????high_each?=?high
????????high_all?+=?high_each
????????#print('1',?high_each,?high_all)
????????return?high_each
????#从小球第n次落地往前推
????high_each?=?high?*?(1?/?2)?**?n
????print(u'第%d次小球弹起的高度为：%.2f'?%(n,?high_each))
????high_all?+=?high_each?*?2
????#print('2',?high_each,?high_all)
????ball_lands(n?-?1)
ball_lands(n)
print(u'小球落地%d次，共经过%.2f米。'?%?(n,high_all))
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
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: