一个动态规划的简单例题

动态规划（Dynamic Programming)

它是计算机中解决最优化问题的一种方法,效率高，速度快。

一般思路:

• 1、穷举法/暴力搜索
• 2、记忆化搜索/剪枝
• 3、改写成迭代形式

思想#

1.动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题

2.但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。

3.如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。

例题

e.g#

Copy
找出最长的递增的子序列 ,nums = [1,5,2,4,3]
给了一个无序的数组，要求我们找出其中最长的递增的子序列，比如：1，2，4就是其中的一个；1，2，3是另外一个。

我们可以将问题简化：要求这个算法只返回最长序列的“长度”

利用暴力枚举/暴力搜索：从“1”出发，最长递增子序列长度：3

算法实现：

Copy
def L( nums , i ):# 我们可以定义一个函数L，这个函数会返回从数组第i个数字开始的最长子序列长度
    if i == len(nums) - 1 : # 取到最后一个数字
        return 1
	for j in range ( i + 1 ,len( nums ) ) : # 检查i后面的所有数字，将索引记为j
        									#遍历所有的j
  		if nums [ j ] > nums [ i ] : # 只要这个数比当前数大（也就是说可以构成递增序列）			
            max_len = max( max_len , L( nums , j ) + 1) # 递归的调用函数自身，去计算从j开始的最长子序列长度，然后+1得到目前这个序列的总长度
	return max_len

# 接下来只需要对数组中的每一个数i ,依次调用L函数，然后选出长度最长的那个返回即可
def length_of_LTS(nums):
     return max(
            L(nums , i )for i in range ( len( nums))
	 )
        
# 可以带入之前的数据进行测试
nums = [1,5,2,4,3]
print(length_of_LTS(nums))

算法优化：记忆化搜索#

再次观察下方的遍历树,我们遍历子序列1，2，4的时候就已经计算过"从4开始的最大子序列的长度"，后面遍历1，4的时候又计算了一次。因此算法存在大量重复的计算。

解决方案的关键是我们可以在第一次计算的时候，将结果保留下来。

Copy
def L( nums , i ):
    
     if i in memo:# 看开头是否保存过这个答案
         return memo [ i ]# 如果是，直接返回结果
    
     # 否则再去计算答案
     if i == len(nums) - 1: # 取到最后一个数字
         return 1
        
     for j in range ( i + 1 ,len( nums ) ) : 
     	if nums [ j ] > nums [ i ]:
             max_len = max( max_len , L( nums , j ) + 1) # 遍历所有的j

     memo[ i ] = max_len # 哈希表，记录下“从i开始最长的子序列长度”
     return max_len

def length_of_LTS(nums):
    return max(
            L(nums , i )for i in range ( len( nums))
)

这里用到了记忆化搜索，这也就是为什么大家常说用空间换时间

迭代/非递归的实现#

从最后的式子可以推至开头的式子，是不是很像数学归纳法?

Copy
def length_of_LTS(nums);
     n = len( nums )  # 5
     L = [1 ] * n # initial value: [1,1,1,1,1] 
# 通过两个循环，外面的循环代表从下往上的依次计算；里面的循环用于遍历括号中的这些数值，运算的结果可以存放到一个数组中,直接叫L
     for i in reversed(range(n)): # i -> 4,3,2,1,0
      	for j in range(i + 1 , n):
          	if nums [ j ] > nums [ i ] :
                L[ i ] = max(L[ i ],L [ j ] + 1)                
	return max(L)

10分钟彻底搞懂“动态规划”算法_哔哩哔哩_bilibili

配套视频的链接哦