动态规划问题

给一个无序的数组 [1, 5, 2, 4, 3] ，找出最长的递增子序列
比如1,2,4 还有1,2,3
或者把问题简化一下，求最长递增子序列长度

暴力枚举(暴力搜索)

思路

从1出发，取比他大的数，然后第二个数再取比他大的数
算法一直循环往复的下去，直到把每个子序列都找遍
image.png

代码实现

写一个函数，传入参数为数组，和出发寻找子序列的下标，最终返回子序列长度
使用递归计算子序列长度

  1. def L(nums, i):
  2.     max_len = 1
  3.     # 检查i下标后所有数字
  4.     for j in range(i + 1, len(nums)):
  5.         if nums[j] > nums[i]:
  6.             # 计算从j开始的最长子序列长度
  7.             # 因为从最开始计算子序列长度 所以要+1
  8.             max_len = max(max_len, L(nums, j) + 1)
  9.     return max_len

但是此写法时间复杂度太高，数组数量大时效率极低

优化方案 记忆化搜索

用空间换时间，避免重复计算，在第一次计算的时候将结果保存
比如上面出现的4，在子序列中出现了两次，可以在第一次出现的时候将结果保存下来
因为4后面没有比他更大的所以 L(4) = 1
image.png

  1. # 存储计算结果
  2. memo = {}
  4. def L(nums, i):
  5.     # 判断是否保存过
  6.     if i in memo:
  7.         return memo[i]
  8.     max_len = 1
  9.     # 计算后续的节点开始最长的子序列
  10.     for j in range(i + 1, len(nums)):
  11.         if nums[j] > nums[i]:
  12.             # 计算从j开始的最长子序列长度
  13.             # 因为从最开始计算子序列长度 所以要+1
  14.             max_len = max(max_len, L(nums, j) + 1)
  15.     # 保存子序列长度
  16.     memo[i] = max_len
  17.     return max_len

迭代/非递归实现

避免递归时函数调用的开销