简介

Kevin2li大约 6 分钟

简介

动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。

使用条件：

最优子结构：原问题的解可以由子问题的最优解得到
重叠子问题：存在子问题会被重复计算
无后效性

方法论：

定义状态(决定数据规模)
根据当前状态推导出可行子问题（有限次操作，n-1次操作）
计算每个子问题的解并记忆
根据具体任务的逻辑从子问题的解中得到当前问题的解

最终答案可能在某一状态中(如最后一个状态)，也可能是所有状态计算得到(如最大/小值)

类型

按变量数量分

一个变量：

最长递增子序列最大子数组和

两个变量：

编辑距离(leetcode)open in new window

问题描述： s1->s2的最小修改次数，允许的操作有删除、添加、修改3种

状态定义： $dp[i][j]$ 表示s1[...i]转变为s2[...j]的最小修改次数
状态转移： $dp[i][j]= dp[i-1][j-1], s_1[i]==s_2[j]$ $d p [i] [j] = d p [i - 1] [j - 1], s_{1} [i] == s_{2} [j]$ # 最后一个字符相同 $dp[i][j]= dp[i][j-1], s_1[i]!=s_2[j]$ $d p [i] [j] = d p [i] [j - 1], s_{1} [i]! = s_{2} [j]$ # 增 $dp[i][j]= dp[i-1][j], s_1[i]!=s_2[j]$ $d p [i] [j] = d p [i - 1] [j], s_{1} [i]! = s_{2} [j]$ # 删 $dp[i][j]= dp[i-1][j-1], s_1[i]!=s_2[j]$ $d p [i] [j] = d p [i - 1] [j - 1], s_{1} [i]! = s_{2} [j]$ # 改
- 边界条件: dp[0][j]=j, dp[i][0] = i
- 最终答案： $dp[n][m]$

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n, m = len(word1), len(word2)

        dp = [[0 for i in range(m+1)] for j in range(n+1)]
        for i in range(n+1):
            dp[i][0] = i
        for i in range(m+1):
            dp[0][i] = i

        for i in range(1, n+1):
            for j in range(1, m+1):
                if word1[i-1] == word2[j-1]: # 最后字符相同
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1 # 分别为增、删、改
        return dp[n][m]

最长公共子序列(leetcode)open in new window

问题描述：arr1, arr2的最长公共子序列

- 状态定义：
- 状态转移：
- 边界条件:
- 最终答案：

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

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

最长回文子串(leetcode)open in new window
- 状态定义： dp[i][j]: 以s[i]开头、s[j]结尾的子串是否为回文串
- 状态转移： $dp[i][j]= dp[i+1][j-1]\ \&\ s[i]==s[j]$
- 边界条件：dp[i][i+1]=True, dp[i][i+2]=s[i]==s[i+2]
- 最终答案：所有dp[i][j]为true中的最长字串

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False for i in range(n+1)] for j in range(n+1)]
        max_len = 1
        ans_i, ans_j = 1, 1
        for L in range(1, n+1):
            for i in range(1, n+1):
                j = i + L - 1
                if j < n+1:
                    if L == 1:
                        dp[i][j] = True
                    elif L == 2:
                        dp[i][j] = s[i-1] == s[j-1]
                    else:
                        dp[i][j] = False if s[i-1]!=s[j-1] else dp[i+1][j-1]
                    if dp[i][j] and j-i+1 > max_len:
                        max_len = j-i+1
                        ans_i, ans_j = i, j
        return s[ans_i-1:ans_j]

最小路径和(leetcode)open in new window
- 状态定义：
- 状态转移：
- 边界条件:
- 最终答案：

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0 for i in range(n+1)] for j in range(m+1)]
        for i in range(1, m+1):
            for j in range(1, n+1):
                if i == 1:
                    dp[i][j] = dp[i][j-1] + grid[i-1][j-1]
                elif j == 1:
                    dp[i][j] = dp[i-1][j] + grid[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1]
        return dp[m][n]

最大子数组和(leetcode)open in new window
- 状态定义：
- 状态转移：
- 边界条件:
- 最终答案：

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [0 for i in range(n+1)]
        ans = nums[0]
        for i in range(1, n+1):
            dp[i] = max(dp[i-1]+nums[i-1], nums[i-1])
            if dp[i] > ans:
                ans = dp[i]
        return ans

跳跃游戏(leetcode)open in new window dp[i]表示位置i能跳到的最远距离

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        dp = [0 for i in range(n+1)]
        dp[0]=1
        for i in range(1, n+1):
            if dp[i-1]>0:
                dp[i] = max(dp[i-1]-1, nums[i-1])
            else:
                dp[i] = 0
        return dp[n-1]>0

按dp次数分

一次

大部分属于这类

两次

152. 乘积最大子数组open in new window

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        dp_max = [0] * (n+1)
        dp_min = [0] * (n+1)
        dp_min[1] = dp_max[1] = nums[0]
        ans = nums[0]
        for i in range(2, n+1):
            dp_max[i] = max(nums[i-1], dp_max[i-1]*nums[i-1], dp_min[i-1]*nums[i-1])
            dp_min[i] = min(nums[i-1], dp_max[i-1]*nums[i-1], dp_min[i-1]*nums[i-1])
            ans = max(ans, dp_max[i])
        return ans

题型

背包问题

输入：物品数组，每件物品含有体积、价值、数量等属性限制：背包容量目标：

背包恰好装满，且物品数量最少(凑零钱问题)
背包尽量装，总价值越大越好
- 每件物品只有1个，只能取或不取，不允许去0.5个： 0-1背包
- xx
xx

0-1背包

完全背包

零钱兑换(leetcode)open in new window

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        m = len(coins)
        dp = [-1 for i in range(amount+1)]
        dp[0] = 0
        for i in range(1, amount+1):
            t = 10001
            for coin in coins:
                if i >= coin:
                    if dp[i-coin] != -1:
                        t = min(t, dp[i-coin] + 1)
            if t!=10001:
                dp[i] = t 
        return dp[amount]

同类题目：完全平方数open in new window

多重背包

混合背包

分组背包

二维背包

依赖背包

区间dp

戳气球(leetcode)open in new window dp[i][j]为开区间最值

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums.insert(0, 1)
        nums.append(1)
        n = len(nums)
        dp = [[0 for i in range(n+1)] for j in range(n+1)]
        for L in range(1, n+1):
            for i in range(1, n+1):
                j = i + L - 1
                if j < n+1:
                    if L == 1 or L == 2:
                        dp[i][j] = 0
                    elif L == 3:
                        dp[i][j] = nums[i-1]*nums[i]*nums[i+1]
                    else:
                        t = 0
                        for k in range(i+1, j):
                            t = max(t, dp[i][k] + dp[k][j] + nums[i-1]*nums[k-1]*nums[j-1])
                        dp[i][j] = t
        return dp[1][n]

数位dp

状压dp

树状dp

参考：https://oi-wiki.org/dp/tree/open in new window 337. 打家劫舍 IIIopen in new window

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        def dfs(root):
            # dp[0]表示不选，dp[1]表示选，要后序遍历才能自底向上计算
            if root is None:
                return [0, 0]
            l = dfs(root.left)
            r = dfs(root.right)
            return [max(l)+max(r), root.val+l[0]+r[0]]
        return max(dfs(root))

与其他算法结合

接雨水(leetcode)open in new window 单调栈、前缀和
状态定义： $dp[i]$ 表示前i个柱子能容纳的水容量

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        stack = []
        dp = [0 for i in range(n+1)]
        
        # 前缀和
        pre_sum = [0 for i in range(n+1)]
        for i in range(1, n+1):
            pre_sum[i] = pre_sum[i-1] + height[i-1]
        
        for i in range(1, n+1):
            if not stack or height[i-1] <= height[stack[-1]]:
                stack.append(i-1)
                dp[i] = dp[i-1]
            else:
                while stack and height[stack[-1]] <= height[i-1]:
                    l = stack.pop()
                if not stack:
                    h = min(height[l], height[i-1])
                else:
                    h = height[i-1]
                    l = stack[-1]
                dp[i] = dp[l+1]+max(0, h*(i-1-l-1)-(pre_sum[i-1]-pre_sum[l+1]))
                stack.append(i-1)
        return dp[n]

简介

# 简介

# 类型

# 按变量数量分

# 一个变量：

# 两个变量：

# 按dp次数分

# 一次

# 两次

# 题型

# 背包问题

# 0-1背包

# 完全背包

# 多重背包

# 混合背包

# 分组背包

# 二维背包

# 依赖背包

# 区间dp

# 数位dp

# 状压dp

# 树状dp

# 与其他算法结合

简介

类型