多维动态规划

编辑距离

2023-12-17T07:37:59.png
主要是找到通项公式:使用dp[i][j]表示word1[:i]word2[:j]需要使用的最少操作数,那么对应的通项公式如下:

$$ dp[i][j] = \left\{\begin{matrix} dp[i-1][j-1] & if\,\,\,\,word1[i] = word2[j]\\ min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) & if\,\,\,\,word1[i] != word2[j] \end{matrix}\right. $$

其次是初始化,对于dp[0][j]表示word1[:0]word2[:j]需要使用的最少操作数,即dp[0][j]=jdp[i][0]同理
使用python实现:

def minDistance(word1,word2):
    m = len(word1)
    n = len(word2)
    # 初始化
    dp = []
    for i in range(m+1):
        dp.append([0]*(n+1))
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    for i in range(m):
        for j in range(n):
            if word1[i] == word2[j]:
                dp[i+1][j+1] = dp[i][j]
            else:
                dp[i+1][j+1] = min(dp[i+1][j],dp[i][j+1],dp[i][j]) + 1
    return dp[m][n]

交错字符串

2024-05-13T08:37:02.png
判断两个字符串是否可以交叉组合成另外一个字符串,最开始想到的是递归的方法,但是递归会重复导致超时,后面看了一下题解,使用动态规划解决
递归的思路就是s3的第1个字符要么由s1的第1个字符串组成,要么由s2的第1个字符串组成,如果s3的第一个字符由s1的第一个字符组成,那么将s3的第一个字符和s1的第一个字符去掉,则又变成了上面的子问题,递归的思路如下:

def isInterleave2(self, s1: str, s2: str, s3: str) -> bool:
    if len(s1) == 0 and len(s2) == 0 and len(s3) == 0:
        return True
    if len(s3) == 0:
        return False
    flag = False
    if len(s1)>0 and s1[0] == s3[0]:
        flag = self.isInterleave(s1[1:],s2,s3[1:])
    if len(s2)>0 and s2[0] == s3[0]:
        flag = flag or self.isInterleave(s1,s2[1:],s3[1:])
    return flag

dp的思路也很简答,主要是找到通项公式,用dpi表示s1的前i个字符和s2的前j个字符是否能够组成s3的前i+j个字符,需要判断一些边界条件:

def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
    if len(s1) + len(s2) != len(s3): return False
    if len(s1) == 0 or len(s2) == 0:
        return (s1 == s3) or (s2 == s3)
    n = len(s1)
    m = len(s2)
    # 初始化
    dp = [[True for i in range(m+1)] for j in range(n+1)]
    for i in range(n):
        dp[i+1][0] = dp[i][0] and s3[i] == s1[i]
    for j in range(m):
        dp[0][j+1] = dp[0][j] and s3[j] == s2[j]
    # 执行通项公式
    for i in range(1,n+1):
        for j in range(1,m+1):
            dp[i][j] = (dp[i-1][j] and s3[i+j-1]==s1[i-1]) or (dp[i][j-1] and s3[i+j-1]==s2[j-1])
    return dp[n][m]

最长回文子串

2024-05-13T11:21:49.png
这道题有简单的做法,比如遍历每个元素,以这个元素为中心或者以这个元素和相邻的元素为中心,判断其延伸的最大字符串,再从这些最大字符串中选择最大的,就是满足题目要求的;还有更加快的解法(不太好描述,见leetcode题解中最快的代码),此次用dp的方式解决,虽然耗时很长,但目的是为了应用dp
dp[i][k]表示以第i个位置的元素为结尾,长度为k的字符串是否是回文串,是则为1,否则为0,由此便可以解决该题:

def longestPalindrome(self, s: str) -> str:
    if len(s) == 0:return ""
    max_p = s[0]
    n = len(s)+1
    # 初始化
    dp = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        dp[i][0] = 1
        dp[i][4] = 1
    # 执行通项公式 dp[i+1][k] = for...(dp[])
    for i in range(n-1):
        for j in range(i):
            if s[j] == s[i]:
                dp[i+1][i-j+1] = 1 if dp[i][i-j-1]>0 else 0
                if dp[i+1][i-j+1] and len(max_p) < i-j+1:
                    max_p = s[j:i+1]
    return max_p

三角形最小路径和

2024-05-13T12:10:27.png
最开始我用递归的方式解,超时了,因为感觉dp好像没法用,dp[i] 和 dp[i-1]没啥关系,好像和dp[i+1]有关系,就没有往dp想,看了一下题解,思路非常好,将置顶向下改为置底向上,一下子思路就开阔了,用dp[i][j]表示从第(i,j)开始到底部最小值,那么dp[0,0]就是我们要的答案,通项公式如下:

$$ dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + tri[i][j] $$

代码如下:

# dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + tri[i][j]
def minimumTotal(self, triangle: List[List[int]]) -> int:
    # 初始化
    dp = [[triangle[i][j] if i == len(triangle)-1 else 0  for j in range(len(triangle[i]))] for i in range(len(triangle))]
    # 执行dp
    i = len(triangle)-2
    while i >=0:
        for j in range(len(triangle[i])):
            dp[i][j] = min(dp[i+1][j],dp[i+1][j+1]) + triangle[i][j]
        i -= 1
    #
    return dp[0][0]

最大正方形

2023-12-17T08:52:16.png
因为是正方形,题目变得简单,使用dp[i][j]表示以[i,j]为正方形的右下脚元素对应的最大正方形,如果右下角值为1,则最大的正方形等于左边dp[i][j-1]、上面dp[i-1][j]、中间dp[i-1][j-1]对应的最小值,即

$$ dp[i][j] = \left\{\begin{matrix} 0 & if\,\,\,\,matrix[i][j] = 0\\ min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1 & if\,\,\,\,matrix[i][j] = 1 \end{matrix}\right. $$

上面那个通项公式绘制一个图就比较好理解了,借用leetcode上的解题图
2023-12-17T09:01:43.png
黄色部分是最大的正方形,图1所示,左边的最大正方形是4,中间的是3,上边的是4,则最大的是三者最小值3+1,图2所示,左边的是3,中间的是4,上边的是2,则最大的是三者最小值2+1
python代码实现如下所示:

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        max_value = 0
        dp = [ [ 0 for j in range(len(matrix[i]))] for i in range(len(matrix))]
        # 初始条件
        for i in range(len(matrix)):
            if matrix[i][0] == '1':
                dp[i][0] = 1
                max_value = 1
        for i in range(len(matrix[0])):
            if matrix[0][i] == '1':
                dp[0][i] = 1
                max_value = 1
        # 执行dp通项公式
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[i])):
                if matrix[i][j] == '1':
                    dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1
                    if dp[i][j]*dp[i][j] > max_value:
                        max_value = dp[i][j]*dp[i][j]
        #
        return max_value

最小路径和

2023-12-17T09:31:12.png
这种类型的题目很简单,因为通项公式很明显,用dp[i][j]表示从左上角到位置[i,j]路径值最短,则通项公式为:

$$ dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j] $$

主要需要注意的是dp的初始化,[0,0]处的值是确定的,[0,j],[i,0]位置的值是确定的
使用python实现:

def minPathSum(self, grid: List[List[int]]) -> int:
    dp = []
    for i in range(len(grid)):
        dp.append([0]*len(grid[0]))
    dp[0][0] = grid[0][0]
    for i in range(1,len(grid)):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    for j in range(1,len(grid[0])):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    for i in range(1,len(grid)):
        for j in range(1,len(grid[i])):
            dp[i][j] = min(dp[i][j-1],dp[i-1][j]) + grid[i][j]
    return dp[-1][-1]

一维动态规划

最长递增子序列

2023-12-17T10:04:45.png
dp[i]表示以第i个位置为终点对应的最长递增子序列,则该值等于前面所有满足条件的最大dp值,即通项公式为:

$$ dp[i] = (\max_{j,nums[j]<nums[i]}^idp[j]) + 1 $$

最后还需要转换一下,因为dp[i]表示的是以第i个位置为终点对应的最长递增子序列,题目是需要的是任意一个子序列,并不是非得包括最后一个元素,用python实现如下:

def lengthOfLIS(self, nums: List[int]) -> int:
    ret = 0
    dp = [0]*len(nums)
    for i in range(len(nums)):
        max_value = 1
        for j in range(i):
            if nums[j]<nums[i]:
                max_value = max(max_value,dp[j]+1)
        dp[i] = max_value
        ret = max(ret,max_value)
    return ret

零钱兑换

2023-12-17T14:05:11.png
常规dp解法,dp[i]表示总金额为i时需要的最少硬币数,等于前面满足条件的最小dp值,即通项公式为:

$$ dp[i] = (\min_{c_k}^{coins}dp[i-c_k]) + 1 $$

注意无法组合的处理,使用python实现如下:

def coinChange(self, coins: List[int], amount: int) -> int:
    dp = [0]*(amount+1)
    for i in range(1,amount+1):
        cur_num = amount+1
        for k in coins:
            if i-k>=0:
                cur_num = min(cur_num,dp[i-k]+1)
        dp[i] = cur_num
    return dp[amount] if dp[amount]<=amount else -1

单词拆分

2023-12-17T14:13:29.png
定义dp[i]s[:i]是否可以由wordDDict组成,则需遍历满足条件(这个条件就是s[:i]的尾部可以由wordDDict中的某个词等价)的子串是否可以由wordDDict组成,用python实现如下:

def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    dp = [False]*(len(s)+1)
    dp[0] = True
    for i in range(len(s)):
        states = False
        for w in wordDict:
            w_length = len(w)
            if i+1-w_length>=0 and s[i+1-w_length:i+1] == w:
                states = states or dp[i+1-w_length]
        dp[i+1] = states
    return dp[-1]

打家劫舍

2023-12-17T14:20:11.png
这个题稍微有点不同,需要用到两个一维数组,比如如果用dp[i]表示当前位置能偷到的最大值,由于题目中提到不能连着偷,dp数组中没法知道i-1个位置是否偷过,因此一个位置应该有两个状态,该位置被偷的情况下能偷的最大值,该位置不被偷的情况下能偷的最大值,最后取这两个的最大值,对应的通项公式如下:

$$ dp[0][i] = max(dp[1][i-1],dp[0][i-1]) \\ dp[1][i] = dp[0][i-1] + nums[i] $$

用python实现:

def rob(self, nums: List[int]) -> int:
    dp = [[0]*len(nums),[0]*len(nums)]
    dp[0][0] = 0
    dp[1][0] = nums[0]
    for i in range(1,len(nums)):
        dp[0][i] = max(dp[1][i-1],dp[0][i-1])
        dp[1][i] = dp[0][i-1] + nums[i]
    return max(dp[0][-1],dp[1][-1])