动态规划

发表于 | 分类于
字数统计: 4.6k | 阅读时长 ≈ 21

五问动态规划

问：动态规划是什么？

答：动态规划是一种通过“大而化小”的思路解决问题的算法。区别于一些固定形式的算法，如二分法，宽度优先搜索法，动态规划没有实际的步骤来规定第一步做什么第二步做什么。所以更加确切的说，动态规划是一种解决问题的思想。这种思想的本质是，一个规模比较大的问题（假如用2-3个参数可以表示），是通过规模比较小的若干问题的结果来得到的（通过取最大，取最小，或者加起来之类的运算）所以我们经常看到的动态规划的核心——状态转移方程都长成这样：

问：动态规划什么时候可以用？

答：动态规划解决的一定是最优化问题。一个问题必须有重叠的子问题和最优子结构，才能使用动态规划取解决问题。

问：动态规划的常见类型有哪些？

  • 矩阵型
  • 序列型
  • 双序列型
  • 划分型
  • 区间型
  • 背包型

问：什么样的问题适合使用动态规划？

答：可以使用动态规划的问题一般都有一些特点可以遵循。如题目的问法一般是三种方式：

  1. 求最大值/最小值
  2. 求可不可行
  3. 求方案总数

如果你碰到一个问题，是问你这三个问题之一的，那么有90%的概率是使用动态规划来求解。要重点说明的是，如果一个问题让你求出“所有的”方案和结果，则肯定不是使用动态规划。

解决一个动态规划问题的步骤是什么？

答：首先判断是否是动态规划的问题，如果是，则尝试将其进行分类常见类型，找到对应的类别和相似的问题。接着从下面的4个要素去逐步剖析解决这道题：

  1. 状态是什么
  2. 状态转移方程是什么
  3. 状态的初始值是什么
  4. 问题要求的最后答案是什么

每个步骤分析完成之后，就基本上解决了整道动态规划的问题。

动态规划相关题

交叉字符串

题目：给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。

样例

比如 s1 = “aabcc” s2 = “dbbca”

  • 当 s3 = “aadbbcbcac”，返回 true.
  • 当 s3 = “aadbbbaccc”， 返回 false.

思路：

1.这题我们利用动态规划加记忆化搜索。如果能够进行交叉组成，利用动态规划，建立 $boolean dp[i][j]$， 意思是s1的第i为 和s2的第j为是否能够够成s3的i + j 长度的交叉字符串。不一定要每个字符交替插入，s1 = aa, s2 = d 也可以组成s3 = aad。记忆矩阵这里要清楚定义，一个维度是s1的长度，一个维度是s2的长度。

2.因此状态转移方程就可以写成:

3.初始条件要注意，我们这里是把记忆矩阵建立为$test$，因此第一行就是没有s1的情况下看看s2能不能与s3配对，第一列就是在没有s2的情况下能不能与s3配对。
4.最后就是看最右下角的dp。时间复杂度是o(n*m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    """
    @params s1, s2, s3: Three strings as description.
    @return: return True if s3 is formed by the interleaving of
             s1 and s2 or False if not.
    @hint: you can use [[True] * m for i in range (n)] to allocate a n*m matrix.
    """
    def isInterleave(self, s1, s2, s3):
        # write your code here
        if s1 is None or s2 is None or s3 is None:
            return False
        if len(s1) + len(s2) != len(s3):
            return False
        # 初始边界s1行s2列的false
        interleave = [[False] * (len(s2) + 1) for i in range(len(s1) + 1)]
        interleave[0][0] = True
        for i in range(len(s1)):
            interleave[i + 1][0] = s1[:i + 1] == s3[:i + 1]
        for i in range(len(s2)):
            interleave[0][i + 1] = s2[:i + 1] == s3[:i + 1]

        for i in range(len(s1)):
            for j in range(len(s2)):
                interleave[i + 1][j + 1] = False
                if s1[i] == s3[i + j + 1]:
                    interleave[i + 1][j + 1] = interleave[i][j + 1]
                if s2[j] == s3[i + j + 1]:
                    interleave[i + 1][j + 1] |= interleave[i + 1][j]
        return interleave[len(s1)][len(s2)]

最长上升子序列

描述：给定一个整数序列，找到最长上升子序列（LIS，不要求一定连续），返回LIS的长度。例如现在有序列A=\{1,2,3,-1,-2,7,9\}，它的最长上升子序列为\{1,2,3,7,9\}，长度为5.

思路：dp[i] 表示走到第i个元素时的当前最大连续子序列的长度 ，这样对A[i]有两种可能：

1、如果A[i]之前的元素A[j]，其中$jdp[i]$，那么可以把A[i]拼接到A[j]的后面

2、如果之前的元素都比A[i]大，则A[i]自己成为最大的上升自序，长度为1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    """
    @param nums: The integer array
    @return: The length of LIS (longest increasing subsequence)
    """
    def longestIncreasingSubsequence(self, nums):
        # write your code here
        if nums is None or not nums:
            return 0
        dp = [1] * len(nums) # 边界初始条件
        for curr, val in enumerate(nums):
            for prev in xrange(curr):
                if nums[prev] < val:  # 如果之前的元素大于等于curr，则dp[curr]为初始的1
                    dp[curr] = max(dp[curr], dp[prev] + 1) #状态转移方程
        return max(dp)

单词拆分 ++

描述：给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。

样例：给出s = “lintcode”，dict = [“lint”,”code”]返回 true 因为“lintcode”可以被空格切分成“lint code”

思路：如果最大字典长度为k，f[i]的状态由前面i-k到i-1之间决定，这中间任何一段属于dict则f[I]为True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    # @param s: A string s
    # @param dict: A dictionary of words dict
    def wordBreak(self, s, dict):
        if len(dict) == 0:
            return len(s) == 0
            
        n = len(s)
        f = [False] * (n + 1)
        f[0] = True  # 初始边界
        
        maxLength = max([len(w) for w in dict]) #先计算字典中最大长度，减少复杂度
        for i in xrange(1, n + 1):
            for j in range(1, min(i, maxLength) + 1): #不必遍历i之前的所有j
                if not f[i - j]:
                    continue
                if s[i - j:i] in dict:
                    f[i] = True
                    break # 有一个满足即可判断下一个f[i+1]
        return f[n]

数字三角形

描述：给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上

样例：比如，给出下列数字三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

思路：自底向上的动态规划, 当前位置由左下或者右下最小值决定，时间复杂度O(n), python3 实现 ， triangle数组代表第i行第j个数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    """
    @param triangle: a list of lists of integers
    @return: An integer, minimum path sum
    """
    def minimumTotal(self, triangle):
        rows = len(triangle)
        dp = [[0] * len(triangle[row]) for row in range(rows)] 
        for i in range(len(triangle[rows - 1])):
            dp[rows - 1][i] = triangle[rows - 1][i] #初始边界
        for i in range(rows - 2, -1, -1):
            for j in range(i + 1):
                dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j] #状态转移方程
        return dp[0][0]

最小路径和

描述：给定一个只含非负整数的m×n网格，找到一条从左上角到右下角的可以使数字和最小的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    """
    @param grid: a list of lists of integers.
    @return: An integer, minimizes the sum of all numbers along its path
    """
    def minPathSum(self, grid):
        for i in range(len(grid)): 
            for j in range(len(grid[0])):
                if i == 0 and j > 0:
                    grid[i][j] += grid[i][j-1] # 第一行，只在左边
                elif j == 0 and i > 0:
                    grid[i][j] += grid[i-1][j] # 第一列，只在右边
                elif i > 0 and j > 0:
                    grid[i][j] += min(grid[i-1][j], grid[i][j-1])  # 由上面和左面的最小路径决定
        return grid[len(grid) - 1][len(grid[0]) - 1]

爬楼梯 ++

描述：假设你正在爬楼梯，需要n步你才能到达顶部。但每次你只能爬一步或者两步，你能有多少种不同的方法？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    """
    @param n: An integer
    @return: An integer
    """
    def climbStairs(self, n):
        # write your code here
        if n == 0:
            return 1
        if n <= 2:
            return n
        result=[1,2]
        for i in range(n-2):
            result.append(result[-2]+result[-1])
        return result[-1]

不同的路径

描述：有一个机器人的位于一个 m × n 个网格左上角。机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。问有多少条不同的路径？

思路：有左边一格的路径数和上面一格的路径数决定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:

    def uniquePaths(self, m, n):
        paths = [[0] * n for i in range(m)] #初始边界
        # initial rows
        paths[0][0] = 1
        for x in range(1, m):
            paths[x][0] = paths[x - 1][0] #边界
        # initail columns
        for y in range(1, n):
            paths[0][y] = paths[0][y - 1] #边界

        for x in range(1, m):
            for y in range(1, n):
                paths[x][y] = paths[x -1][y] + paths[x][y - 1]
        return paths[m - 1][n - 1]

编辑距离 +

题目：给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。你总共三种操作方法：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

样例：给出 work1=”mart” 和 work2=”karma”，返回 3。（先进行2个替换，后面进行1个插入）

思路：f[i][j代表第一个字符串以i结尾匹配上（编辑成）第二个字符串以j结尾的字符串，最少需要多少次编辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    """
    @param word1: A string
    @param word2: A string
    @return: The minimum number of steps.
    """
    def minDistance(self, word1, word2):
        n, m = len(word1), len(word2)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        
        for i in range(n + 1):
            f[i][0] = i # 边界
        for j in range(m + 1):
            f[0][j] = j # 边界

        for i in range(1, n + 1):
            for j in range(1, m + 1):
                if word1[i - 1] == word2[j - 1]:
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j] + 1, f[i][j - 1] + 1)
                    # equivalent to f[i][j] = f[i - 1][j - 1]
                else: #分别代表替换，插入，删除
                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
                        
        return f[n][m]

正则表达式匹配 ++

描述：实现支持‘.’和‘*‘的正则表达式匹配。’.’匹配任意一个字母。’*’匹配零个或者多个前面的元素。匹配应该覆盖整个输入字符串，而不仅仅是一部分。返回true 和 false

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
isMatch("aa","a") → false

isMatch("aa","aa") → true

isMatch("aaa","aa") → false

isMatch("aa", "a*") → true

isMatch("aa", ".*") → true

isMatch("ab", ".*") → true

isMatch("aab", "c*a*b") → true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    # DP
    def isMatch(self, s, p):
        dp = [[False for i in range(0,len(p) + 1)] for j in range(0, len(s) + 1)]
        dp[0][0] = True
        for i in range(1, len(p) + 1):
            if (p[i - 1] == '*'):
                dp[0][i] = dp[0][i - 2]
        for i in range(1, len(s) + 1):
            for j in range(1, len(p) + 1):
                if p[j - 1] == '*':
                    dp[i][j] = dp[i][j - 2]
                    if s[i - 1] == p[j - 2] or p[j - 2] == '.':
                        dp[i][j] |= dp[i-1][j]
                else:
                    if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                        dp[i][j] = dp[i - 1][j - 1]
    
        return dp[len(s)][len(p)]

    # 懒癌版
    def isMatch(self, s, p):
        # '$'字符规则代表匹配字符串的末尾，匹配返回一个Match 对象，否则返回None
        return re.match(p + '$', s) != None

不同的二叉查找树 II

描述：给出n，生成所有由1…n为节点组成的不同的二叉查找树

样例：给出n = 3，生成所有5种不同形态的二叉查找树：

1
2
3
4
5
6
1         3     3       2    1
 \       /     /       / \    \
  3     2     1       1   3    2
 /     /       \                \
2     1         2                3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        this.val = val
        this.left, this.right = None, None
"""
class Solution:
    # @paramn n: An integer
    # @return: A list of root
    def generateTrees(self, n):
        # write your code here
        return self.dfs(1, n)
        
    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):
            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:
                for j in RightTree:
                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res

乘积最大子序列 +

描述：找出一个序列中乘积最大的连续子序列（至少包含一个数）

样例：比如, 序列 [2,3,-2,4] 中乘积最大的子序列为 [2,3] ，其乘积为6。

思路：这道题和maximal subarray思路一样，不同的是对于加法加上负数会变小，加上正数会变大；而对于乘法，乘以正数有可能变大也有可能变小（原数是负数的情况下），乘以负数也有可能变大或者变小

所以需要两个变量：
min_p表示行进到当前subarray能得到的最小的积
max_p表示行进到当前subarray能得到的最大的积

对于某一个subarray来说，它最大的积，有可能来自之前的最大积乘以一个正数，或者之前的最小积乘以一个负数，或者nums[i]就是最大的
因此 $max_p = max(nums[i], max_p × nums[i], min_p × nums[i])$
最小积同理

最后用res变量跟踪一下全局最大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    """
    @param nums: An array of integers
    @return: An integer
    """
    def maxProduct(self, nums):
        if not nums:
            return None
            
        global_max = prev_max = prev_min = nums[0]
        for num in nums[1:]:
            if num > 0:
                curt_max = max(num, prev_max * num)
                curt_min = min(num, prev_min * num)
            else:
                curt_max = max(num, prev_min * num)
                curt_min = min(num, prev_max * num)
            
            global_max = max(global_max, curt_max)
            prev_max, prev_min = curt_max, curt_min
            
        return global_max

通配符匹配

描述：判断两个可能包含通配符“？”和“*”的字符串是否匹配。匹配规则如下：

1
2
3
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个串完全匹配才算匹配成功。

样例：

1
2
3
4
5
6
7
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    """
    @param s: A string
    @param p: A string includes "?" and "*"
    @return: A boolean
    """
    def isMatch(self, s, p):
        # write your code here
        n = len(s)
        m = len(p)
        f = [[False] * (m + 1) for i in range(n + 1)]
        f[0][0] = True

        if n == 0 and p.count('*') == m:
            return True

        for i in range(0, n + 1):
            for j in range(0, m + 1):
                if i > 0 and j > 0:
                    f[i][j] |= f[i-1][j-1] and (s[i-1] == p[j-1] or p[j - 1] in ['?', '*'])

                if i > 0 and j > 0:
                    f[i][j] |= f[i - 1][j] and p[j - 1] == '*'

                if j > 0:
                    f[i][j] |= f[i][j - 1] and p[j - 1] == '*'
        return f[n][m]

打劫房屋 ++

描述：假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且 当相邻的两个房子同一天被打劫时，该系统会自动报警。给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。

样例：给定 [3, 8, 4], 返回 8.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    """
    @param A: An array of non-negative integers
    @return: The maximum amount of money you can rob tonight
    """
    def houseRobber(self, A):
        if not A:
            return 0
        if len(A) <= 2:
            return max(A)
            
        f = [0] * len(A)
        f[0], f[1] = A[0], max(A[0], A[1])
        
        for i in range(2, len(A)):
            f[i] = max(f[i - 1], f[i - 2] + A[i])
        return f[len(A) - 1]
        
# 使用滚动数组版本
class Solution:
    """
    @param A: An array of non-negative integers
    @return: The maximum amount of money you can rob tonight
    """
    def houseRobber(self, A):
        if not A:
            return 0
        if len(A) <= 2:
            return max(A)
            
        f = [0] * 3
        f[0], f[1] = A[0], max(A[0], A[1])
        
        for i in range(2, len(A)):
            f[i % 3] = max(f[(i - 1) % 3], f[(i - 2) % 3] + A[i])
            
        return f[(len(A) - 1) % 3]

买卖股票的最佳时机

描述：假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成 k 笔交易。你不可以同时参与多笔交易(你必须在再次购买前出售掉之前的股票)

样例：给定价格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.（1买4卖，2买5卖）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    """
    @param k: an integer
    @param prices: an integer array
    @return: an integer which is maximum profit
    """
    def maxProfit(self, k, prices):
        # write your code here
        size = len(prices)
        if k >= size / 2:
            return self.quickSolve(size, prices)
        dp = [None] * (2 * k + 1)
        dp[0] = 0
        for i in range(size):
            for j in range(min(2 * k, i + 1) , 0 , -1):
                dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])
        return max(dp)

    def quickSolve(self, size, prices):
        sum = 0
        for x in range(size - 1):
            if prices[x + 1] > prices[x]:
                sum += prices[x + 1] - prices[x]
        return sum

解码方法+

描述：有一个消息包含A-Z通过以下规则编码，现在给你一个加密过后的消息，问有几种解码的方式

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

样例：给你的消息为12，有两种方式解码 AB(12) 或者 L(12). 所以返回 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    # @param {string} s a string,  encoded message
    # @return {int} an integer, the number of ways decoding
    def numDecodings(self, s):
        # Write your code here
        if s == "" or s[0] == '0':
            return 0

        dp=[1,1]
        for i in range(2,len(s) + 1):
            if 10 <= int(s[i - 2 : i]) <=26 and s[i - 1] != '0':
                dp.append(dp[i - 1] + dp[i - 2])
            elif int(s[i-2 : i]) == 10 or int(s[i - 2 : i]) == 20:
                dp.append(dp[i - 2])
            elif s[i-1] != '0':
                dp.append(dp[i-1])
            else:
                return 0

        return dp[len(s)]

完美平方

描述：给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, … )使得他们的和等于 n。你需要让平方数的个数最少。

样例：

给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。
给出 n = 13, 返回 2 因为 13 = 4 + 9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def numSquares(self, n):
        # write your code here
        dp = []
        import sys
        for i in range(n+1):
            dp.append(sys.maxint)
        i = 0
        while i * i <= n:
            dp[i*i] = 1
            i += 1

        
        for i in range(n+1):
            j = 1
            while j * j <= i:
                dp[i] = min(dp[i], dp[i-j*j] + 1)
                j += 1
        return dp[n]
-------------Thanks for Reading!-------------