编程进阶网
杨充
2022-07-26
目录

动规算法题合集

# 爬楼梯（Climbing Stairs）

LeetCode 70 · ⭐ · 斐波那契 DP

# 01. 题目

每次爬 1 或 2 步，到第 n 阶有几种方法？n=3 → 3（1+1+1 / 1+2 / 2+1）

# 02. 分析

dp[i] = dp[i-1] + dp[i-2]（从i-1迈1步或从i-2迈2步）。空间压缩为两个变量。

# 03. 代码

Java：if(n<=2) return n; int a=1,b=2; for(int i=3;i<=n;i++){ int c=a+b; a=b; b=c; } return b; Python：a,b=1,2; [exec('a,b=b,a+b') for _ in range(3,n+1)]; return b if n>2 else n C++：int a=1,b=2; if(n==1) return a; for(int i=3;i<=n;i++){ int c=a+b; a=b;b=c; } return b;

复杂度：O(N)/O(1)。

# 04. DP 入门口诀

状态 → 转移 → 边界：三个要素缺一不可。 状态 = 到第i阶的方法数。转移 = dp[i]=dp[i-1]+dp[i-2]。边界 = dp[1]=1,dp[2]=2。

相关：172 打家劫舍

# 打家劫舍 I / II / III

LeetCode 198/213/337 · ⭐⭐

# 172 打家劫舍 I (198) 线性

dp[i]=max(dp[i-1], dp[i-2]+nums[i])。空间压缩：prev2,prev。

public int rob(int[] nums) { int prev2=0,prev=0; for(int n:nums){ int cur=Math.max(prev,prev2+n); prev2=prev; prev=cur; } return prev; }
1

Python：prev2=prev=0; [exec('cur=max(prev,prev2+n); prev2,prev=prev,cur') for n in nums]; return prev

# 173 打家劫舍 II (213) 环形

首尾相邻 → 做两次线性：max(rob(0,n-2), rob(1,n-1))。

public int rob(int[] nums) { int n=nums.length; if(n==1) return nums[0]; return Math.max(robRange(nums,0,n-2),robRange(nums,1,n-1)); }
int robRange(int[] nums,int l,int r){ int prev2=0,prev=0; for(int i=l;i<=r;i++){ int cur=Math.max(prev,prev2+nums[i]); prev2=prev;prev=cur; } return prev; }
1
2

# 174 打家劫舍 III (337) 树形

对每个节点返回 [不偷, 偷]。

public int rob(TreeNode root) { int[] r=dfs(root); return Math.max(r[0],r[1]); }
int[] dfs(TreeNode n){ if(n==null) return new int[]{0,0}; int[] L=dfs(n.left),R=dfs(n.right); return new int[]{Math.max(L[0],L[1])+Math.max(R[0],R[1]), n.val+L[0]+R[0]}; }
1
2

Python：def rob(self, root): def dfs(n): return (0,0) if not n else (max(dfs(n.left))+max(dfs(n.right)), n.val+dfs(n.left)[0]+dfs(n.right)[0]); return max(dfs(root))

复杂度：I/II O(N)/O(1)，III O(N)/O(H)。

# N003 打家劫舍 II（环形）

LeetCode 213 · ⭐⭐ · 环形DP

# 01. 题目

房屋围成环形（首尾相邻），不能偷相邻两家。[2,3,2] → 3。

# 02. 题目分析

环形 → 首尾不能同时偷。做两次线性 DP：

  • rob(0, n-2)：不偷最后一家
  • rob(1, n-1)：不偷第一家 取 max。

# 03. 代码

Java：

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
}
int robRange(int[] nums, int l, int r) {
    int prev2 = 0, prev = 0;
    for (int i = l; i <= r; i++) {
        int cur = Math.max(prev, prev2 + nums[i]);
        prev2 = prev; prev = cur;
    }
    return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

Python：

def rob(self, nums):
    def rob_range(l, r):
        prev2 = prev = 0
        for i in range(l, r + 1):
            cur = max(prev, prev2 + nums[i])
            prev2 = prev; prev = cur
        return prev
    n = len(nums)
    if n == 1: return nums[0]
    return max(rob_range(0, n-2), rob_range(1, n-1))
1
2
3
4
5
6
7
8
9
10

复杂度：O(N)/O(1)。

相关：N002 打家劫舍、N004 打家劫舍III

# N004 打家劫舍 III（树形DP）

LeetCode 337 · ⭐⭐ · 树形DP

# 01. 题目

二叉树形式排列房屋，不能偷直接相连的两家（父子关系）。

# 02. 题目分析

对每个节点返回 [不偷, 偷] 两种状态：

  • 不偷：max(L[0],L[1]) + max(R[0],R[1])
  • 偷：node.val + L[0] + R[0]

# 03. 代码

Java：

public int rob(TreeNode root) {
    int[] res = dfs(root); return Math.max(res[0], res[1]);
}
int[] dfs(TreeNode node) { // [不偷, 偷]
    if (node == null) return new int[]{0, 0};
    int[] L = dfs(node.left), R = dfs(node.right);
    int notRob = Math.max(L[0], L[1]) + Math.max(R[0], R[1]);
    int rob = node.val + L[0] + R[0];
    return new int[]{notRob, rob};
}
1
2
3
4
5
6
7
8
9
10

Python：

def rob(self, root):
    def dfs(node):
        if not node: return (0, 0)
        L, R = dfs(node.left), dfs(node.right)
        return (max(L)+max(R), node.val+L[0]+R[0])
    return max(dfs(root))
1
2
3
4
5
6

C++：

int rob(TreeNode* root) {
    auto [notRob, rob] = dfs(root);
    return max(notRob, rob);
}
pair<int,int> dfs(TreeNode* node) {
    if (!node) return {0,0};
    auto [l0,l1] = dfs(node->left), [r0,r1] = dfs(node->right);
    return {max(l0,l1)+max(r0,r1), node->val+l0+r0};
}
1
2
3
4
5
6
7
8
9

复杂度：O(N)/O(H)。

三题对比：线性 → 环形（两次线性）→ 树形（自底向上返回双状态）。同一条 DP 思路的递进。

相关：N002 打家劫舍、N003 打家劫舍II

# 不同路径 (62) / 最小路径和 (64) / 正则匹配 (10)

# 175 不同路径 (62) 网格DP

dp[j] += dp[j-1]。Python: return comb(m+n-2, n-1)。

public int uniquePaths(int m, int n) { int[] dp=new int[n]; Arrays.fill(dp,1); for(int i=1;i<m;i++) for(int j=1;j<n;j++) dp[j]+=dp[j-1]; return dp[n-1]; }
1

# 177 最小路径和 (64)

public int minPathSum(int[][] g) { int m=g.length,n=g[0].length; for(int i=1;i<m;i++) g[i][0]+=g[i-1][0]; for(int j=1;j<n;j++) g[0][j]+=g[0][j-1]; for(int i=1;i<m;i++) for(int j=1;j<n;j++) g[i][j]+=Math.min(g[i-1][j],g[i][j-1]); return g[m-1][n-1]; }
1

Python：

def minPathSum(self, g):
    m,n=len(g),len(g[0])
    for i in range(1,m): g[i][0]+=g[i-1][0]
    for j in range(1,n): g[0][j]+=g[0][j-1]
    for i in range(1,m):
        for j in range(1,n): g[i][j]+=min(g[i-1][j],g[i][j-1])
    return g[-1][-1]
1
2
3
4
5
6
7

复杂度：O(N²)/O(1)（原地修改）。

# 190 正则表达式匹配 (10)

.匹配任意，*匹配零或多个前元素。

public boolean isMatch(String s, String p) { int m=s.length(),n=p.length(); boolean[][] dp=new boolean[m+1][n+1]; dp[0][0]=true; for(int j=2;j<=n;j++) if(p.charAt(j-1)=='*') dp[0][j]=dp[0][j-2]; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(p.charAt(j-1)=='*'){ dp[i][j]=dp[i][j-2]; if(p.charAt(j-2)=='.'||p.charAt(j-2)==s.charAt(i-1)) dp[i][j]|=dp[i-1][j]; } else dp[i][j]=dp[i-1][j-1]&&(p.charAt(j-1)=='.'||p.charAt(j-1)==s.charAt(i-1)); return dp[m][n]; }
1

Python：

def isMatch(self, s, p):
    m,n=len(s),len(p); dp=[[False]*(n+1) for _ in range(m+1)]; dp[0][0]=True
    for j in range(2,n+1):
        if p[j-1]=='*': dp[0][j]=dp[0][j-2]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if p[j-1]=='*': dp[i][j]=dp[i][j-2] or ((p[j-2]=='.'or p[j-2]==s[i-1]) and dp[i-1][j])
            else: dp[i][j]=dp[i-1][j-1] and (p[j-1]=='.'or p[j-1]==s[i-1])
    return dp[m][n]
1
2
3
4
5
6
7
8
9

复杂度：O(MN)/O(MN)。

# DP 题型速查

题型 代表题 状态定义
线性 172打家劫舍 dp[i]=max(dp[i-1],dp[i-2]+v)
网格 175/177 dp[i][j]=dp[i-1][j]+dp[i][j-1]
双串 179LCS/180编辑/190正则 dp[i][j]=f(a[i],b[j])
背包 181-185 dp[j]=max(dp[j],dp[j-w]+v)
区间 187回文 dp[i][j]=dp[i+1][j-1]&&s[i]==s[j]

# N007 最小路径和

LeetCode 64 · ⭐⭐ · 网格DP

public int minPathSum(int[][] g) { int m=g.length,n=g[0].length; for(int i=1;i<m;i++) g[i][0]+=g[i-1][0]; for(int j=1;j<n;j++) g[0][j]+=g[0][j-1]; for(int i=1;i<m;i++) for(int j=1;j<n;j++) g[i][j]+=Math.min(g[i-1][j],g[i][j-1]); return g[m-1][n-1]; }
1

Python：

def minPathSum(self, g):
    m,n=len(g),len(g[0])
    for i in range(1,m): g[i][0]+=g[i-1][0]
    for j in range(1,n): g[0][j]+=g[0][j-1]
    for i in range(1,m):
        for j in range(1,n): g[i][j]+=min(g[i-1][j],g[i][j-1])
    return g[-1][-1]
1
2
3
4
5
6
7

复杂度：O(mn)/O(1)（原地修改）。相关：N005 不同路径

# 最长递增子序列 (300) / 最长公共子序列 (1143)

# 178 LIS (300)

DP O(N²): dp[i]=max(dp[i],dp[j]+1) when nums[i]>nums[j]

贪心+二分 O(NlogN): tails数组

public int lengthOfLIS(int[] nums) { int[] tails=new int[nums.length]; int len=0; for(int x:nums){ int l=0,r=len; while(l<r){ int m=l+(r-l)/2; if(tails[m]<x) l=m+1; else r=m; } tails[l]=x; if(l==len) len++; } return len; }
1

Python：

def lengthOfLIS(self, nums):
    from bisect import bisect_left
    tails=[]
    for x in nums:
        i=bisect_left(tails,x)
        if i==len(tails): tails.append(x)
        else: tails[i]=x
    return len(tails)
1
2
3
4
5
6
7
8

# 179 LCS (1143)

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1 & a[i]=b[j] \ \max(dp[i-1][j], dp[i][j-1]) & a[i]\neq b[j] \end{cases}$$

public int longestCommonSubsequence(String a, String b) { int m=a.length(),n=b.length(); int[][] dp=new int[m+1][n+1]; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j]=a.charAt(i-1)==b.charAt(j-1)?dp[i-1][j-1]+1:Math.max(dp[i-1][j],dp[i][j-1]); return dp[m][n]; }
1

Python：

def longestCommonSubsequence(self, a, b):
    m,n=len(a),len(b); dp=[[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1): dp[i][j]=dp[i-1][j-1]+1 if a[i-1]==b[j-1] else max(dp[i-1][j],dp[i][j-1])
    return dp[m][n]
1
2
3
4
5

复杂度：LIS O(NlogN)/O(N)，LCS O(MN)/O(MN)。

# N009 最长公共子序列（LCS）

LeetCode 1143 · ⭐⭐ · 双串DP

# 01. 题目

text1="abcde", text2="ace" → 3 ("ace")

# 02. 分析

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1 & a[i]=b[j] \ \max(dp[i-1][j], dp[i][j-1]) & a[i]\neq b[j] \end{cases}$$

# 03. 代码

Java：

public int longestCommonSubsequence(String a, String b) {
    int m=a.length(), n=b.length();
    int[][] dp=new int[m+1][n+1];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=dp[i-1][j-1]+1;
            else dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9

Python：

def longestCommonSubsequence(self, a, b):
    m,n=len(a),len(b)
    dp=[[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if a[i-1]==b[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[m][n]
1
2
3
4
5
6
7
8

C++：

int longestCommonSubsequence(string a, string b) {
    int m=a.size(),n=b.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1));
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            dp[i][j]=a[i-1]==b[j-1]?dp[i-1][j-1]+1:max(dp[i-1][j],dp[i][j-1]);
    return dp[m][n];
}
1
2
3
4
5
6
7
8

复杂度：O(MN)/O(MN)。

相关：N008 最长递增子序列、N010 编辑距离

# 编辑距离（Edit Distance）

LeetCode 72 · ⭐⭐⭐ · 双串DP

# 01. 题目

"horse"→"ros" 需 3 步（replace/delete/insert）。最少操作数。

# 02. 分析

$$dp[i][j] = \begin{cases} dp[i-1][j-1] & a[i]=b[j] \ 1+\min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) & a[i]\neq b[j] \end{cases}$$

三种操作：替换(dp[i-1][j-1])、删除(dp[i-1][j])、插入(dp[i][j-1])

# 03. 代码

Java：

public int minDistance(String a, String b) {
    int m=a.length(),n=b.length();
    int[][] dp=new int[m+1][n+1];
    for(int i=0;i<=m;i++) dp[i][0]=i;
    for(int j=0;j<=n;j++) dp[0][j]=j;
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
        if(a.charAt(i-1)==b.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
        else dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10

Python：

def minDistance(self, a, b):
    m,n=len(a),len(b); dp=[[0]*(n+1) for _ in range(m+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(1,m+1):
        for j in range(1,n+1): dp[i][j]=dp[i-1][j-1] if a[i-1]==b[j-1] else 1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
    return dp[m][n]
1
2
3
4
5
6
7

C++：

int minDistance(string a, string b) { int m=a.size(),n=b.size(); vector<vector<int>> dp(m+1,vector<int>(n+1)); for(int i=0;i<=m;i++) dp[i][0]=i; for(int j=0;j<=n;j++) dp[0][j]=j; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) dp[i][j]=a[i-1]==b[j-1]?dp[i-1][j-1]:1+min({dp[i-1][j-1],dp[i-1][j],dp[i][j-1]}); return dp[m][n]; }
1

复杂度：O(MN)/O(MN)。空间可压缩到 O(min(M,N))。

相关：179 最长公共子序列、190 正则

# 背包问题全家桶

# 181 零钱兑换 (322) 完全背包·最少

public int coinChange(int[] coins, int a) { int[] dp=new int[a+1]; Arrays.fill(dp,a+1); dp[0]=0; for(int c:coins) for(int i=c;i<=a;i++) dp[i]=Math.min(dp[i],dp[i-c]+1); return dp[a]>a?-1:dp[a]; }
1

# 182 零钱兑换II (518) 完全背包·组合数

public int change(int a, int[] coins) { int[] dp=new int[a+1]; dp[0]=1; for(int c:coins) for(int i=c;i<=a;i++) dp[i]+=dp[i-c]; return dp[a]; }
1

注意：外硬币内容量 = 组合数。内容量外硬币 = 排列数。

# 183 分割等和子集 (416) 0-1背包

public boolean canPartition(int[] nums) { int s=0; for(int n:nums) s+=n; if(s%2==1) return false; int t=s/2; boolean[] dp=new boolean[t+1]; dp[0]=true; for(int n:nums) for(int j=t;j>=n;j--) dp[j]|=dp[j-n]; return dp[t]; }
1

倒序遍历保证每个物品只用一次。

# 184 目标和 (494) 0-1排列

public int findTargetSumWays(int[] nums, int t) { int s=0; for(int n:nums) s+=n; if((s+t)%2==1||s+t<0) return 0; int b=(s+t)/2; int[] dp=new int[b+1]; dp[0]=1; for(int n:nums) for(int j=b;j>=n;j--) dp[j]+=dp[j-n]; return dp[b]; }
1

# 185 完全平方数 (279) 完全背包

public int numSquares(int n) { int[] dp=new int[n+1]; Arrays.fill(dp,n+1); dp[0]=0; for(int i=1;i*i<=n;i++) for(int j=i*i;j<=n;j++) dp[j]=Math.min(dp[j],dp[j-i*i]+1); return dp[n]; }
1

# 186 单词拆分 (139) 线性DP+哈希

public boolean wordBreak(String s, List<String> dict) { Set<String> set=new HashSet<>(dict); boolean[] dp=new boolean[s.length()+1]; dp[0]=true; for(int i=1;i<=s.length();i++) for(int j=0;j<i;j++) if(dp[j]&&set.contains(s.substring(j,i))){ dp[i]=true; break; } return dp[s.length()]; }
1

# 背包速查

类型 循环顺序 含义
0-1背包 倒序 j-- 每个物品一次
完全背包·最少 正序 j++ min
完全背包·组合 外硬币正序 dp[j]+=dp[j-c]

# N012 零钱兑换 II（组合数）

LeetCode 518 · ⭐⭐ · 完全背包·组合数

N011 问"最少几个"，N012 问"几种凑法"——一字之差，本质翻天。

# 01. 题目

amount = 5, coins = [1,2,5] → 4 种（5 / 2+2+1 / 2+1+1+1 / 1+1+1+1+1）

# 02. 题目分析

组合数 vs 排列数

$$dp[i] = dp[i] + dp[i - coin]$$

关键在于遍历顺序：

遍历顺序 结果 含义
外硬币内容量 组合数 硬币顺序固定，不会重复计数
内容量外硬币 排列数 同一组硬币的不同顺序计多次
为什么 外硬币内容量 内容量外硬币
[1,2] 凑 3 1+1+1, 1+2（只计2种） 1+1+1, 1+2, 2+1（计3种）

# 03. 代码

Java：

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins)                    // 外循环：硬币
        for (int i = coin; i <= amount; i++)   // 内循环：容量（正序）
            dp[i] += dp[i - coin];
    return dp[amount];
}
1
2
3
4
5
6
7
8

Python：

def change(self, amount: int, coins: List[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1
    for c in coins:
        for i in range(c, amount + 1):
            dp[i] += dp[i - c]
    return dp[amount]
1
2
3
4
5
6
7

C++：

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount + 1);
    dp[0] = 1;
    for (int c : coins)
        for (int i = c; i <= amount; i++)
            dp[i] += dp[i - c];
    return dp[amount];
}
1
2
3
4
5
6
7
8

复杂度：O(N·amount) / O(amount)。

# 04. N011 vs N012 对比

N011 最少硬币 N012 组合数
状态转移 min(dp[i], dp[i-c]+1) dp[i] += dp[i-c]
初始化 dp[0]=0，其余 ∞ dp[0]=1，其余 0
目标 最少 方案数

相关题目：N011 零钱兑换、M005 组合总和

# N013 分割等和子集（Partition Equal Subset Sum）

LeetCode 416 · ⭐⭐ · 0-1背包

最经典的 0-1背包应用题。"能否选出一些数凑成 sum/2"。

# 01. 题目

[1,5,11,5] → true（可分为 [1,5,5] 和 [11]）

# 02. 题目分析

转化为背包问题

问题：数组能否分成和相等的两个子集？
转化：能否选一些数，和为 sum/2？
     ↓
0-1背包：target = sum/2，每个物品（数）只能选一次
1
2
3
4

$$dp[j] = dp[j] ;|; dp[j - num]$$

倒序遍历 j（每个数只能用一次）。

# 03. 代码

Java：

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int n : nums) sum += n;
    if (sum % 2 == 1) return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int n : nums)
        for (int j = target; j >= n; j--)   // 倒序！
            dp[j] |= dp[j - n];
    return dp[target];
}
1
2
3
4
5
6
7
8
9
10
11
12

Python：

def canPartition(self, nums: List[int]) -> bool:
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True
    for n in nums:
        for j in range(target, n - 1, -1):  # 倒序！
            dp[j] |= dp[j - n]
    return dp[target]
1
2
3
4
5
6
7
8
9
10

C++：

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2) return false;
    int target = sum / 2;
    vector<bool> dp(target + 1);
    dp[0] = true;
    for (int n : nums)
        for (int j = target; j >= n; j--)
            dp[j] = dp[j] || dp[j - n];
    return dp[target];
}
1
2
3
4
5
6
7
8
9
10
11

复杂度：O(N·target) / O(target)。

# 04. 总结

dp[j] 表示能否凑成 j。每次倒序遍历保证每个物品只用一次——这是 0-1 背包的核心。

相关题目：N014 目标和、N011 零钱兑换

# N014 目标和（Target Sum）

LeetCode 494 · ⭐⭐ · 0-1背包变形

给每个数加正号或负号，使总和等于 target。巧妙转化为 0-1 背包。

# 01. 题目

nums = [1,1,1,1,1], target = 3 → 5 种（-1+1+1+1+1, +1-1+1+1+1, ...）

# 02. 题目分析

数学转化

设正数子集和为 P，则负数子集绝对值为 sum-P。

$$P - (sum - P) = target \quad\Rightarrow\quad P = \frac{sum + target}{2}$$

问题转化为：选出一些数，和为 (sum+target)/2 的方案数。

这就是 0-1 背包求方案数！

# 03. 代码

Java：

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int n : nums) sum += n;
    if ((sum + target) % 2 == 1 || sum + target < 0) return 0;
    int bag = (sum + target) / 2;
    int[] dp = new int[bag + 1];
    dp[0] = 1;
    for (int n : nums)
        for (int j = bag; j >= n; j--)   // 倒序
            dp[j] += dp[j - n];
    return dp[bag];
}
1
2
3
4
5
6
7
8
9
10
11
12

Python：

def findTargetSumWays(self, nums: List[int], target: int) -> int:
    total = sum(nums)
    if (total + target) % 2 or total + target < 0: return 0
    bag = (total + target) // 2
    dp = [0] * (bag + 1); dp[0] = 1
    for n in nums:
        for j in range(bag, n - 1, -1):
            dp[j] += dp[j - n]
    return dp[bag]
1
2
3
4
5
6
7
8
9

C++：

int findTargetSumWays(vector<int>& nums, int target) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if ((sum + target) % 2 || sum + target < 0) return 0;
    int bag = (sum + target) / 2;
    vector<int> dp(bag + 1); dp[0] = 1;
    for (int n : nums)
        for (int j = bag; j >= n; j--)
            dp[j] += dp[j - n];
    return dp[bag];
}
1
2
3
4
5
6
7
8
9
10

复杂度：O(N·bag) / O(bag)。

# 04. N013 vs N014 对比

N013 分割等和 N014 目标和
dp 含义 能否凑成 凑成方案数
状态转移 dp[j] \|= dp[j-n] dp[j] += dp[j-n]
初始化 dp[0]=true dp[0]=1

核心：同一个 0-1 背包框架，改 dp[0] 和转移运算即可切换"是否"和"多少"。

相关题目：N013 分割等和子集

# N015 完全平方数（Perfect Squares）

LeetCode 279 · ⭐⭐ · 完全背包

硬币就是完全平方数——N011 零钱兑换的特例。

# 01. 题目

n = 12 → 3（4+4+4）；n = 13 → 2（4+9）

# 02. 分析

与 N011 完全相同的完全背包框架。硬币集合 = {1, 4, 9, 16, ...}。

# 03. 代码

Java：

public int numSquares(int n) {
    int[] dp = new int[n + 1];
    Arrays.fill(dp, n + 1);
    dp[0] = 0;
    for (int i = 1; i * i <= n; i++)
        for (int j = i * i; j <= n; j++)
            dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
    return dp[n];
}
1
2
3
4
5
6
7
8
9

Python：

def numSquares(self, n: int) -> int:
    dp = [n + 1] * (n + 1)
    dp[0] = 0
    for i in range(1, int(n**0.5) + 1):
        sq = i * i
        for j in range(sq, n + 1):
            dp[j] = min(dp[j], dp[j - sq] + 1)
    return dp[n]
1
2
3
4
5
6
7
8

C++：

int numSquares(int n) {
    vector<int> dp(n + 1, n + 1);
    dp[0] = 0;
    for (int i = 1; i * i <= n; i++)
        for (int j = i * i; j <= n; j++)
            dp[j] = min(dp[j], dp[j - i*i] + 1);
    return dp[n];
}
1
2
3
4
5
6
7
8

复杂度：O(N·√N) / O(N)。

# 04. 四平方和定理（选读）

任何正整数都可以表示为最多 4 个完全平方数之和（Lagrange定理）。因此答案只能是 1/2/3/4。

相关题目：N011 零钱兑换、N012 零钱兑换II

# N016 单词拆分

LeetCode 139 · ⭐⭐ · DP+哈希

public boolean wordBreak(String s, List<String> dict) { Set<String> set=new HashSet<>(dict); boolean[] dp=new boolean[s.length()+1]; dp[0]=true; for(int i=1;i<=s.length();i++) for(int j=0;j<i;j++) if(dp[j]&&set.contains(s.substring(j,i))){ dp[i]=true; break; } return dp[s.length()]; }
1

Python：

def wordBreak(self, s, wordDict):
    wd=set(wordDict); dp=[False]*(len(s)+1); dp[0]=True
    for i in range(1,len(s)+1):
        for j in range(i):
            if dp[j] and s[j:i] in wd: dp[i]=True; break
    return dp[-1]
1
2
3
4
5
6

复杂度：O(N²)/O(N)。

# 最长回文子串 (5) / 回文子串 (647) / 最大正方形 (221)

# 187 最长回文子串 (5) 中心扩展 O(N²)/O(1)

public String longestPalindrome(String s) {
    int n=s.length(),start=0,max=0;
    for(int i=0;i<n;i++){ int l1=expand(s,i,i),l2=expand(s,i,i+1),l=Math.max(l1,l2); if(l>max){ max=l; start=i-(l-1)/2; } }
    return s.substring(start,start+max);
}
int expand(String s,int l,int r){ while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){ l--; r++; } return r-l-1; }
1
2
3
4
5
6

Python：

def longestPalindrome(self, s):
    n,start,mx=len(s),0,0
    def expand(l,r):
        while l>=0 and r<n and s[l]==s[r]: l-=1; r+=1
        return r-l-1
    for i in range(n):
        l=max(expand(i,i),expand(i,i+1))
        if l>mx: mx,start=l,i-(l-1)//2
    return s[start:start+mx]
1
2
3
4
5
6
7
8
9

# 188 回文子串个数 (647)

int cnt=0;
public int countSubstrings(String s) { for(int i=0;i<s.length();i++){ expand(s,i,i); expand(s,i,i+1); } return cnt; }
void expand(String s,int l,int r){ while(l>=0&&r<s.length()&&s.charAt(l)==s.charAt(r)){ cnt++; l--; r++; } }
1
2
3

# 189 最大正方形 (221)

public int maximalSquare(char[][] m) { int r=m.length,c=m[0].length,mx=0; int[][] dp=new int[r+1][c+1]; for(int i=1;i<=r;i++) for(int j=1;j<=c;j++) if(m[i-1][j-1]=='1'){ dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1])); mx=Math.max(mx,dp[i][j]); } return mx*mx; }
1

Python：

def maximalSquare(self, m):
    r,c,mx=len(m),len(m[0]),0; dp=[[0]*(c+1) for _ in range(r+1)]
    for i in range(1,r+1):
        for j in range(1,c+1):
            if m[i-1][j-1]=='1': dp[i][j]=1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]); mx=max(mx,dp[i][j])
    return mx*mx
1
2
3
4
5
6

复杂度：回文 O(N²)/O(1)，最大正方形 O(MN)/O(MN)。

# N018 回文子串个数

LeetCode 647 · ⭐⭐ · 中心扩展

# 01. 题目

统计字符串中所有回文子串的个数。"abc" → 3 ("a","b","c")

# 02. 代码

Java：

int count = 0;
public int countSubstrings(String s) {
    for (int i = 0; i < s.length(); i++) { expand(s, i, i); expand(s, i, i + 1); }
    return count;
}
void expand(String s, int l, int r) {
    while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
        count++; l--; r++;
    }
}
1
2
3
4
5
6
7
8
9
10

Python：

def countSubstrings(self, s: str) -> int:
    n, ans = len(s), 0
    for i in range(n):
        l = r = i
        while l >= 0 and r < n and s[l] == s[r]: ans += 1; l -= 1; r += 1
        l, r = i, i + 1
        while l >= 0 and r < n and s[l] == s[r]: ans += 1; l -= 1; r += 1
    return ans
1
2
3
4
5
6
7
8

C++：

int countSubstrings(string s) {
    int n = s.size(), ans = 0;
    auto expand = [&](int l, int r) {
        while (l >= 0 && r < n && s[l] == s[r]) { ans++; l--; r++; }
    };
    for (int i = 0; i < n; i++) { expand(i, i); expand(i, i + 1); }
    return ans;
}
1
2
3
4
5
6
7
8

复杂度：O(N²)/O(1)。

相关：N017 最长回文子串、N019 最大正方形

# N019 最大正方形

LeetCode 221 · ⭐⭐ · 网格DP

# 01. 题目

给定 0/1 矩阵，找出只含 1 的最大正方形面积。

# 02. 分析

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

# 03. 代码

Java：

public int maximalSquare(char[][] matrix) {
    int m=matrix.length, n=matrix[0].length, max=0;
    int[][] dp=new int[m+1][n+1];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(matrix[i-1][j-1]=='1') {
                dp[i][j]=1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
                max=Math.max(max,dp[i][j]);
            }
    return max*max;
}
1
2
3
4
5
6
7
8
9
10
11

Python：

def maximalSquare(self, matrix):
    m,n,max_len=len(matrix),len(matrix[0]),0
    dp=[[0]*(n+1) for _ in range(m+1)]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if matrix[i-1][j-1]=='1':
                dp[i][j]=1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
                max_len=max(max_len,dp[i][j])
    return max_len*max_len
1
2
3
4
5
6
7
8
9

复杂度：O(MN)/O(MN)。

相关：N007 最小路径和

# N020 正则表达式匹配

LeetCode 10 · ⭐⭐⭐ · 双串DP

# 01. 题目

s="aab", p="c*a*b" → true。.匹配任意单字符，*匹配零或多个前面元素。

# 02. 分析

关键在 * 的处理：

  • 不用 *：dp[i][j] = dp[i][j-2]
  • 用 *：(p[j-2]=='.'||p[j-2]==s[i-1]) && dp[i-1][j]

# 03. 代码

Java：

public boolean isMatch(String s, String p) {
    int m=s.length(), n=p.length();
    boolean[][] dp=new boolean[m+1][n+1]; dp[0][0]=true;
    for(int j=2;j<=n;j++) if(p.charAt(j-1)=='*') dp[0][j]=dp[0][j-2];
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(p.charAt(j-1)=='*'){
                dp[i][j]=dp[i][j-2];
                if(p.charAt(j-2)=='.'||p.charAt(j-2)==s.charAt(i-1))
                    dp[i][j]|=dp[i-1][j];
            } else {
                dp[i][j]=dp[i-1][j-1]&&(p.charAt(j-1)=='.'||p.charAt(j-1)==s.charAt(i-1));
            }
    return dp[m][n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Python：

def isMatch(self, s, p):
    m,n=len(s),len(p)
    dp=[[False]*(n+1) for _ in range(m+1)]; dp[0][0]=True
    for j in range(2,n+1):
        if p[j-1]=='*': dp[0][j]=dp[0][j-2]
    for i in range(1,m+1):
        for j in range(1,n+1):
            if p[j-1]=='*':
                dp[i][j]=dp[i][j-2]
                if p[j-2]=='.' or p[j-2]==s[i-1]: dp[i][j]|=dp[i-1][j]
            else:
                dp[i][j]=dp[i-1][j-1] and (p[j-1]=='.' or p[j-1]==s[i-1])
    return dp[m][n]
1
2
3
4
5
6
7
8
9
10
11
12
13

复杂度：O(MN)/O(MN)。

相关：N010 编辑距离

#算法
上次更新: 2026/06/17, 12:46:05
回溯算法题合集
位运算算法题合集

← 位运算算法题合集→

最近更新
01
信号崩溃快速排查
06-15
02
CoreDump破案
06-15
03
perf火焰图实战
06-15
更多文章>
Theme by Vdoing | Copyright © 2019-2026 杨充 | MIT License | 桂ICP备2024034950号 | 桂公网安备45142202000030