python动态规划算法实例详解

一、什么是动态规划？

如果大家对“动态规划”这个生僻的术语不理解的话，那就先听小刘给大家说个现实生活中的实际案例吧:

虽然现在手机是相当的便捷，还可以付款，但是最初的时候，我们经常会使用硬币，其中，我们如果遇到手中有很多五毛或者1块钱硬币，要怎么凑出来5元钱呢？凑出来5元钱的这一个过程也可以称之为动态规划算法。

二、新视角：从斐波那契数列看动态规划

斐波那契数列：

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

代码如下：

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)

三、实例扩展（爬楼梯）

1. 题目描述

假设你正在爬楼梯，需要n阶才能到达楼顶，每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

2. 示例

示例1

输入： 2

输出： 2

解释： 有以下两种方法可以爬到楼顶：

1. 1 阶 + 1 阶
2. 2 阶

示例2

输入： 3

输出： 3

解释： 有以下三种方法可以爬到楼顶：

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

3. 解析

如果给的两个示例看的不是特别清楚，你可以当阶梯为0，那么上楼梯方法0种这是必然，当阶梯只有1那么上楼梯方法只有1种：

当4个台阶：

输入：4

输出：4

1. 1阶 + 1阶 + 1阶 + 1阶
2. 2阶 + 2阶
3. 1阶 + 2阶 + 1阶
4. 2阶 + 1阶 + 1阶
5. 1阶 + 1阶 + 2阶

那么得到：

如果感觉看的不明显可以推理一下5阶，6阶…

可以得到当我们想爬n阶楼梯，我们可以得到：p ( n − 1 ) + p ( n − 2 ) p p(n-1) + p(n-2) pp(n−1)+p(n−2)p 为爬楼梯方法。

4. 代码实现

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)

四、结语

今天的算法实例详解就分享到这里了，你们知道什么是动态规划了吗？🥰