动态规划常见面试题

子序列类型
编辑距离

# 编辑距离
def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0] * (n2+1) for _ in range(n1 + 1)]

        for i in range(1,n1 + 1):
            dp[i][0] = dp[i-1][0] + 1
        for j in range(1,n2 + 1):
            dp[0][j] = dp[0][j-1]  + 1

        for i in range(1,n1 + 1):
            for j in range(1,n2 + 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]

最长递增子序列

# 最长递增子序列
def lengthOfLIS(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i] ,dp[j] + 1)
    res = 0
    for i in range(len(dp)):
        res = max(res,dp[i])
    return res 

最大子数组

# 最大连续子数组和
def maxSubArray(self, nums: List[int]) -> int:
        # n = len(nums)
        # dp = [0] * n 
        # dp[0] = nums[0]

        # for i in range(1,n):
        #     if dp[i-1] >= 0:
        #         dp[i] = dp[i-1] + nums[i]
        #     else:
        #         dp[i] = nums[i]
        # return max(dp)

        sum_v = nums[0]
        max_v = nums[0]
        for i in range(1,len(nums)):
            if sum_v > 0:
                sum_v = sum_v + nums[i]
            else:
                sum_v = nums[i]
            max_v = max(max_v,sum_v)
        return max_v

最长公共子序列

def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m,n = len(text1),len(text2)
        dp = [[0] * ( n+ 1) for _ in range(m + 1)]

        for i in range(1,m+1):
            for j in range(1,n+1):
                if text1[i-1] == text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[-1][-1]

背包问题
0-1背包问题

def knapsack(w,n,wt,val):
    dp = [[0] * (w + 1) for _ in range(n+1)]
    for i in range(1,n+1):
        for j in range(1,w+1):
            if w - wt[i-1] < 0:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = max(dp[i-1][j],dp[i-1][wt[i-1]] + val[i-1])
    return dp[n][w]

子集背包问题

def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 2 : return False
        sum_v = sum(nums)
        if sum_v % 2 != 0:
            return False
        target = sum_v // 2
        dp = [[False] * (target+1) for _ in range(n+1)]
        for i in range(n+1):
            dp[i][0] = True
        for i in range(1,n+1):
            for j in range(1,target+1):
                if j - nums[i-1] < 0:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i-1]]
        return dp[n][target]

完全背包问题

游戏问题
最小路径和

加权最短路径

打家劫舍

股票买卖

KMP

贪心问题
区间调度

安排会议室

跳跃游戏