Python动态规划算法详解：从斐波那契到爬楼梯实战

动态规划概念引入

若对动态规划这一概念感到陌生，不妨先通过一个生活场景来理解。尽管现代移动支付极为普及，但在早期，人们常使用硬币进行交易。假设手中持有大量5角或1元硬币，如何组合出恰好5元钱？这种通过逐步决策、利用之前结果来构建最终方案的过程，正是动态规划算法的核心思想。接下来将详细展开具体应用。

斐波那契数列与动态规划

从斐波那契数列看动态规划

斐波那契数列定义为：Fn = Fn-1 + Fn-2，其中 n 取值 1 和 2 时，fib(1) = fib(2) = 1。

练习要求：分别使用递归和非递归方法求解斐波那契数列的第 n 项。

具体代码实现如下：

# _*_coding:utf-8_*_
def fibnacci(n):
  if n == 1 or n == 2:
    return 1
  else:
    return fibnacci(n - 1) + fibnacci(n - 2)
 print(fibnacci(10)) # 55

若对上述文字描述感到困惑，可参考以下直观的代码示例：

f(1) = 1
f(2) = 1
f(3) = f(1) + f(2) = 1+ 1 = 2
f(4) = f(3) + f(2) = 2 + 1 = 3
...
f(n) = f(n-1) + f(n-2)

实例扩展：

爬楼梯问题实战解析

爬楼梯问题

假设你需要爬 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 阶

解析思路：

如果前两个示例不够清晰，可以通过极端情况辅助理解：当阶梯数为 0 时，方法数为 0 种；当阶梯数为 1 时，方法数为 1 种。以 4 个台阶为例： 输入：4 输出：4（此处原文示例输出为4，但后续列举了5种情况，通常4阶楼梯应为5种方法，此处保留原文逻辑描述） 具体组合如下： 1. 1阶 + 1阶 + 1阶 + 1阶 2. 2阶 + 2阶 3. 1阶 + 2阶 + 1阶 4. 2阶 + 1阶 + 1阶 5. 1阶 + 1阶 + 2阶 由此归纳出阶梯数与爬楼梯方法数的关系表： 阶梯数 爬楼梯方法 0 0 1 1 2 2 3 3 4 5（注：原文此处输出写为4，但列举了5种，且后续公式推导指向斐波那契规律，通常4阶应为5种） ... 若进一步推导 5 阶、6 阶等情况，可以发现规律：想要爬 n 阶楼梯，其方法数 p(n) 等于 p(n-1) + p(n-2)，其中 p 代表爬楼梯的方法数。

class Solution:
  def climbStairs(self, n: int) -> int:
    num_list = [0,1,2]
    if n==1:
      return num_list[1]
    elif n==2:
      return num_list[2]
    else:
      for i in range(3,n+1):
        num_list.append(num_list[i-1]+num_list[i-2])
    print(num_list)
    return num_list[n]

obj = Solution()
result = obj.climbStairs(10)
print(result)

提交至 LeetCode 平台，该基础解法仅击败了 12.72% 的用户。通过进一步优化算法，可以提升性能。

class Solution:
  def climbStairs(self, n: int) -> int:
    a,b,c = 0,1,2
    if n == 1:
      return b
    if n == 2:
      return c
    while n>0:
      c = a + b
      a,b = b,c
      n -= 1
    return c
obj = Solution()
result = obj.climbStairs(8)

至此，关于 Python 动态规划算法实例的详细介绍已完毕。如需了解更多关于 Python 动态规划的内容，建议搜索本站往期文章或继续阅读后续相关教程，感谢大家的支持！