动态规划解题方式

  1. 动态规划的解题方式通常分为两种：

通过定义递归方程解决，这是一种自顶向下的求解方式，通常这种方式会有很多重复计算过程，因此可以通过建立备忘录记录中间过程来进行优化；
通过定义DP(Dynamic Programming)数组来求解，这是一种自底向上的求解方式。

  1. 下面以常见的斐波拉契数列为例来说明一下上述两种求解方式。
  2. 斐波那契数列（Fibonacci sequence）是指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……。
  3. 即后一个数为前两个数之和。
  4. 在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）
  6. # 暴力递归
  7. def fib(n):
  8.     if n <= 2:
  9.         return 1
  10.     return fib(n-1) + fib(n-2)
  12. # 斐波那契数列
  13. def fib(n):
  14.     def helper(n):
  15.         if n <= 2:
  16.             return 1
  17.         # 如果n的值已经计算过了，则直接返回值memo[n]
  18.         if n in memo:
  19.             return memo[n]
  20.         memo[n] = fib(n - 1) + fib(n - 2)
  21.         return memo[n]
  22.     # 记录已经计算的值，防止重复计算
  23.     memo = {}
  24.     return helper(n)
  27. print(fib(6))

leetcode题目：爬楼梯

每次最多只能爬1阶或者2阶，求爬到n阶有多少种方法？
题解：爬到n阶只需要知道第n-1阶和第n-2阶有多少种办法，所以只需要记录n-1阶 和 n-2阶的办法数即可

  1. class Solution:
  2.     def climbStairs(self, n: int) -> int:
  3.         # 当 楼梯只有1阶或者2阶
  4.         if  n <= 2:
  5.             return n
  6.         a = 1   # 初始化1阶楼梯有一种办法
  7.         b = 2   # 初始化2阶楼梯有2种办法
  8.         for i in range(3, n+1):
  9.             # 空间压缩，只记录n-1阶 和 n-2阶的办法数
  10.             a, b = b, a+b
  11.         return b
  13. # 时间复杂度O(n),空间复杂度O(1)

leetcode题目：买股票的最佳时间

求卖出股票的最大利益是多少？
题解：卖出减去买入，利益要求最大化，且卖出必须是在买入之后

  1. # 暴力法
  2. class Solution:
  3.     def maxProfit(self, prices: List[int]) -> int:
  4.         ans = 0 # 初始化交易后股票的利益为0
  5.         # 遍历可能买入的时间
  6.         for i in range(len(prices)):
  7.             # 遍历可能卖出的时间，看哪个时间卖出的利润最大
  8.             for j in range(i + 1, len(prices)):
  9.                 # 卖出价格减去买入价格的利润，如果利润为负，则取0,===没有交易
  10.                 ans = max(ans, prices[j] - prices[i])
  12.         # 交易后的利润
  13.         return ans
  15. # 空间复杂度O(1),时间复杂度O(n*n)
  2. class Solution:
  3.     def maxProfit(self, prices: List[int]) -> int:
  4.         minprice = float('inf') # 初始化设置最小买入价格为正无穷大
  5.         maxprofit = 0   # 设置初始化最大利润为0
  6.         for price in prices:
  7.             # 遍历记录历史的最低价格
  8.             minprice = min(minprice, price)
  9.             # 判断当前卖出的最大利润，获取遍历完的最大利润
  10.             maxprofit = max(maxprofit, price - minprice)
  11.         return maxprofit
  13. # 空间复杂度O(1),时间复杂度O(n)
  1. class Solution:
  2.     def maxProfit(self, prices:List[int]) ->int:
  3.         minprice = prices[0]    # 初始化最小价格
  4.         maxprofit = 0    # 初始化最大利润
  5.         for price in prices:
  6.             # 如果当前价格小于最低价，则替换当前价格为最低价
  7.             if price < minprice:
  8.                 minprice = price
  9.             # 如果当前利润小于当前价格减去“当前认为的最低价”，则当前利润才是最大利润
  10.             if maxprofit < price - minprice:
  11.                 maxprofit = price - minprice
  12.         return maxprofit
  15.  # 空间复杂度O(1),时间复杂度O(n)