动态规划

Posted on | | Visitors: ℃
Words count in article: 2.6k

动态规划

动态规划：结合了分治思想和回溯思想的一种动态解决子问题的方法，本质是一个问题由多个子问题组合

WHY：相对于朴素解法，由于可以利用子问题的结果来简化下一子问题的计算，计算复杂度的提升巨大，同时采用了类似回溯的方法来剪枝

HOW：使用DP 需要有一个状态转移的概念，不一定要非常格式化的按照DP的状态转移方程来思考，但是得有状态转移的一个列表

300. 最长上升子序列

本题相对最长连续子序列减少了连续的条件，由于有多种组合导致回溯的情况问题的时间复杂度预计应该是在O（NlogN）， 是典型的数组问题，使用指针的思维实现

如果存在一个最优子序列，那么包含该seq的所有seq（不超过原序列）的最优解都是这个seq的长度

### 单步

思考一个单步过程，对每一个数字，都查找以后的是否有比这个数字大的，如果有说明存在以这个数字开头的上升序列，更新子序列最大的数字，但是这个最大数字并非是最优的，可能存在一个比这个最大数字小，但是比上一个的数字大的，例如【2，5，4，3，。。】此时子序列的最大数字应该是3而不是5

遍历完可以找到一个子序列，计算长度就可以了。这个算法的计算复杂度是N^2

可以简单的写一个伪代码，了解题目意思;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def lengthOfLIS(self, nums) -> int:
    max_len = 0
    if not nums:
            return max_len
    for i in range(len(nums)):
        tmp_max_num = nums[i]
        tmp_max_num2 = nums[i]
        res = []
        res.append(tmp_max_num)
        for j in range(i+1, len(nums), 1):
            if nums[j] > tmp_max_num:
                tmp_max_num2 = tmp_max_num
                tmp_max_num = nums[j]
                res.append(nums[j])
                elif nums[j] > tmp_max_num2:
                    res.remove(tmp_max_num)
                    res.append(nums[j])
                    tmp_max_num = nums[j]
		max_len = max(max_len, len(res))
	return max_len

这个算法N2 的复杂度，时间是1044ms

思考一个更优化的的动态规划算法单步执行，对于数字的分治方法，都是将一个长的数组转化为多个小数组（子序列），并将子问题的答案存在一个dp[]中，然后对这个dp数组处理得到result

再优化一下，由于原数组很长，但是维护的res数组很短，而且反复申请空间消耗的时间很长，干脆每一次遍历的时候都找一下有序数组res里面有没有比这个数字更大的数字，如果没有就说明这个是子序列的最大值，有就替换一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def lengthOfLIS(self, nums) -> int:
	if not nums or not len(nums):
           return 0
       records = []
       records.append(nums[0])
       for i in range(1, len(nums)):
           if nums[i]>records[-1]:
               records.append(nums[i])
           else:
               j = len(records)-1
               while j>=0:
                   if records[j]>=nums[i]:
                       j-=1
                   else:
                       break
               records[j+1]=nums[i]
       return len(records)

时间50ms

674. 最长连续递增序列

这个问题相对上一个更加简单，遍历就完事了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        max_len = 0
        if nums is None : return max_len
        if len(nums) > 1 :
            max_len += 1
        elif len(nums) == 0:
            return 0
        else:
            return 1
        max_all = 0
        for i in range(1, len(nums)):
            if nums[i] > nums[i-1]:
                max_len += 1
            else:
                max_len = 1
            max_all = max(max_all, max_len)
        return max_all

用上动态规划，就是把每一回找到的连续数组的长度用一个dp【】来保存，此时对于每一个子序列都求一个最大长度，求解每一个，但是这个小问题有点浪费内存

5. 最长回文子串

DP经典问题，题目还是子序列的求最优化的问题，一般都有多项式级别的暴力解，子序列不同的序列头和序列尾可以生成n(n-1)/2个子序列，只要对每个子序列判断一次是否回文即可

分析一个序列判断回文的单步：

1， 分析是否头尾相同

2， 然后while 逐步分析两段是否相同

3，直到两个指针指向同一个或者只相差1个位置结束

暴力算法的复杂度是N^3，考虑使用动态规划来简化

可以定义一个dp[i][j]为一个从位置i到位置j的一个子序列是否是回文。

这个看起来是很简单的过程，但是问题其实可以思考到每一个子序列存在相关性，字串不是回文，那么父亲序列绝对不是回文，但是一个子序列若是回文，那它的下一位父亲序列s[i-1]到[j+1]还要判断多出来的s[i-1] == [j+1]就知道是不是回文了，这就是一个递推的一个状态过程

不断的找序列然后找到j-i 最大的那个存在回文的序列即是最长的回文子串

分析一个单步过程：

对于每一个子串i， j=i+n, (n)表示长度为n， n必须满足小于总长len-i-1

  1. 如果n==0 表示只有字串一位肯定是满足的，n==1, 判断是否s[i]==s[j]相等就是aa这种情况，也是满足的
  2. 如果都不满足说明，长度超过1了，那么需要判断它的字串的状态dp[i+1][j-1]和s[i]==s[j] 两者同时成立才可以。
  3. 如果上一条的情况都成立，说明新父亲串是一个回文，此时判断长度是否大于当前最大的回文串是否要更新就行

最后返回最长串的回文字符串

运行时间：4644ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def longestPalindrome(self, s: str) -> str:
        len_s = len(s)
        res = ''
        max_len = 0
        dp = [[False] * len_s for _ in range(len_s)]
        for i in range(len_s-1, -1, -1):
            for n in range(len_s - i):
                j = i+n
                if n == 0:
                    dp[i][j] = True
                elif n == 1:
                    dp[i][j] = True if s[i] == s[j] else False
                else:
                    dp[i][j] = (dp[i+1][j-1] and s[i] == s[j])
                if dp[i][j] and n+1 > max_len:
                    max_len = n+1
                    res = s[i:j+1]
        return res

速度很慢，主要字符串的长度太长，可以采用Manacher 优化到o(N) 有空自再思考

516. 最长回文子序列

相比于上题，减少了连续的条件，此时生成的回文可以不用连续，子序列的数量没有增加，但是要判断的内容变化了， 之前是一次两步长的判断，现在是一次左右可以多步

使用DP的方法，矩阵的数量可以不用改变，但是状态转换的递归条件发生了变化

之前是只判断子序列是否为回文，由于序列的最大回文存在，数量肯定是在最长的序列

​ 此时DP矩阵中存储的是数值， 表示此时子序列（问题）的最大回文长度

状态转移过程：如果满足s[i]==s[j]（‘abba’） 此时的序列相对于dp[i+1][j-1]对应的序列（‘bb’）多两个长度，

​ 如果不满足条件（‘abbc’）此时的序列就是比较子序列dp[i][j-1]（‘abb’）和dp[i+1][j]（‘bbc’）两个谁更大，如果都一样，说明增加的没有区别，不一样说明长度增加了，需要注意要从右下角开始往上遍历，因为每次都需要利用的子序列位于矩阵的左下脚dp[i + 1][j - 1]，左边dp[i][j - 1]，下边dp[i+1][j]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        len_s = len(s)
        dp = [[0] * len_s for _ in range(len_s)]
        for i in range(len_s):
            dp[i][i] = 1
        for i in range(len_s, -1, -1):
            for j in range(i + 1, len_s):
                # print(s[i:j+1])
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
        return dp[0][-1]

运行时间1512 ms

72. 编辑距离

DP中较难的题，编辑距离又叫levenshtein长度，在字符串匹配库，搜索引擎elastic search内都有应用，复杂度最低应该O（mn），表示至少每个字符都对比一下，一般使用C实现库再调用

存在三种方法编辑，编辑距离为1的情况是len*(2+26)， 能编辑的字符串数量是指数增长的，暴力法就不太可能实现了

一个初步的思考是编辑距离为2的序列中间过程应该是由距离为1的再来了一次距离为1的过程，这应该要用递归来做

思考word1 和word2 可能有子问题

1
2
3
4
ho -> ro	ho -> ros 	ho -> rose
			hor -> ros	hor -> rose	
						hors -> rose
						horse -> rose

但是这个开头都是固定的，但是很明显开头和结尾都不是固定的，像or-> ro这样的子问题也可能出现

可以设置dp[i][j]表示字符长度为i的字符串和长度为j的字符串的最短编辑距离，那对于一个单步过程，如果dp[i][i]是0时，说明第i个前面都是一样的

  1. 判断s1[i+1]和s2[j+1]是否相等，如果相等说明两个指针各进一步不影响结果
  2. 如果不等就需要判断这一次的状态改变是如何导致dp[i+1][j+1]变化
  3. 判断插入操作，当我们在word1中插入一个和word2一样的字符，那么word2就被匹配了，所以可以直接表示为dp[i][j-1]+1 对于删除操作，直接表示为dp[i-1][j]+1 对于替换操作，直接表示为dp[i-1][j-1]+1 所以下一个状态就是min（三者）

最后输出结果就是dp[m][n]的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minDistance(self, word1, word2):
        m=len(word1) 
        n=len(word2)
        dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
        #空字符串的初始化
        for i in range(n+1):
            dp[0][i]=i 
        for j in range(m+1):
            dp[j][0]=j 
        # 每一次一个指针走一步    
        for i in range(1,m+1): 
            for j in range(1,n+1):
                if word1[i-1]==word2[j-1]: 
                    dp[i][j]=dp[i-1][j-1]
                else:
                    #不同情况递归求下一个状态，分治思想
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 
        return dp[-1][-1]

运行时间200 ms

-------------本文结束感谢您的阅读 :D -------------
Show comments from Gitment