最最最牛逼的算法：动态规划

1.寻找不相邻元素的最大和

<递归版本>

 1 def recv_opt(array, i):
 2     """
 3     这里面的递归出口是0/1
 4     递归关系是
 5     max(recv_dp(array, i - 2) + array[i],
 6         recv_dp(array, i - 1))
 7     :param array: 数组
 8     :param i: 里面长度
 9     :return: 最大值
10     """
11     if i == 0:
12         return array[0]
13     elif i == 1:
14         return max(array[0], array[1])
15     else:
16         A = recv_opt(array, i - 2) + array[i]
17         B = recv_opt(array, i - 1)
18         return max(A, B)
19 
20 
21 array = [1, 2, 4, 1, 7, 8, 3]
22 print(recv_opt(array, len(array) - 1))

View Code

<动态规划版本>

 1 import numpy as np
 2 arr = [1,2,4,1,7,8,3]
 3 # arr = [4,1,1,9,1]
 4 def dp(arr):
 5     opt = np.zeros(len(arr))
 6     opt[0]=arr[0]
 7     opt[1]=max(arr[0],arr[1])
 8     for i in range(2,len(arr)):
 9         A = opt[i-2]+arr[i]
10         B = opt[i-1]
11         opt[i] = max(A,B)
12     return opt[len(arr)-1]
13 print(dp(arr))
14 """
15 15.0
16 """

View Code

2.最大连续子序列和

思路：对于arr[i],要么为单独为max，要么前面开始的某一段到arr[i].

转移方程为：
    dp[i] = max{arr[i],dp[i-1]+A[i]}
出口为：
    dp[0] = arr[0]

 1 # 最大连续子序列和
 2 def max_sum(arr):
 3     dp = []
 4     dp.append(arr[0])
 5     for i in range(1, len(arr)):
 6         dp.append(max(arr[i], dp[i - 1] + arr[i]))
 7     return dp
 8 
 9 
10 arr = [-2, 11, -4, 13, -5, -2]
11 print(max_sum(arr))

View Code

3.最长公共子序列

思路：。。。

 1 import numpy as np
 2 
 3 
 4 def LCS(str1, str2):
 5     dp = np.zeros((len(str1) + 1, len(str2) + 1))
 6     for i in range(1, len(str1) + 1):
 7         for j in range(1, len(str2) + 1):
 8             if str1[i - 1] == str2[j - 1]:
 9                 dp[i][j] = dp[i - 1][j - 1] + 1
10             else:
11                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
12     return dp
13 
14 
15 print(LCS("abcbdab", "bdcaba"))
16 """
17 [[0. 0. 0. 0. 0. 0. 0.]
18  [0. 0. 0. 0. 1. 1. 1.]
19  [0. 1. 1. 1. 1. 2. 2.]
20  [0. 1. 1. 2. 2. 2. 2.]
21  [0. 1. 1. 2. 2. 3. 3.]
22  [0. 1. 2. 2. 2. 3. 3.]
23  [0. 1. 2. 2. 3. 3. 4.]
24  [0. 1. 2. 2. 3. 4. 4.]]
25 """

View Code