帮我总结下算法题常用的思路和模板（先写个伪代码，然后用java实现）

Question

Answer 1

下面给你一份「算法题高频思路 + 常用模板」速查，按套路 → 伪代码 → Java 模板来写。你刷题时基本就是在这些框架里换“状态/转移/判定”。

0）通用刷题流程（先想清楚再写）

思路清单：

输入规模 n, m, 值域 → 决定复杂度目标（O(n), O(n log n), O(n^2)）
题目要求：最值/计数/可行性/路径/方案数
数据特征：有序？区间？图？树？字符串？可重复？
选套路：双指针/滑窗、二分、前缀和、DP、BFS/DFS、并查集、堆、单调栈/队列、贪心、回溯、KMP/Trie
写伪代码 → 再落 Java（先写核心函数，再补输入输出）

1）双指针 / 滑动窗口

适用： 子数组/子串，要求“最长/最短/计数”，且窗口性质可维护（通常非负、或可用计数表维护）。

伪代码（典型：最长满足条件）

text
l = 0
for r in [0..n-1]:
    add(a[r])
    while window invalid:
        remove(a[l]); l++
    ans = max(ans, r-l+1)

Java 模板

java
int l = 0, ans = 0;
for (int r = 0; r < n; r++) {
    // add a[r]
    // update freq / sum / distinct...
    while (/* invalid */) {
        // remove a[l]
        l++;
    }
    ans = Math.max(ans, r - l + 1);
}

2）二分答案（最常用的“可行性判定”）

适用： “最大化最小值/最小化最大值/最小满足条件”，答案单调。

伪代码

text
lo, hi = possible range
while lo < hi:
    mid = (lo + hi) // 2
    if check(mid) true:
        hi = mid
    else:
        lo = mid + 1
return lo

Java 模板（找最小可行）

java
long lo = L, hi = R;
while (lo < hi) {
    long mid = lo + (hi - lo) / 2;
    if (check(mid)) hi = mid;
    else lo = mid + 1;
}
return lo;

若是“找最大可行”，常用 mid = lo + (hi - lo + 1)/2，然后可行则 lo = mid 否则 hi = mid - 1。

3）前缀和 / 差分

适用： 区间和、区间频繁查询；差分适合区间加减更新。

前缀和伪代码

text
pre[0]=0
for i in 1..n: pre[i]=pre[i-1]+a[i-1]
sum(l,r)=pre[r+1]-pre[l]

Java 模板

java
long[] pre = new long[n + 1];
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];

long rangeSum(int l, int r) { // inclusive
    return pre[r + 1] - pre[l];
}

差分伪代码（区间加 v）

text
diff[l]+=v
diff[r+1]-=v
最后做前缀还原

4）单调栈（Next Greater / 区间贡献）

适用： 下一个更大/更小元素，柱状图最大矩形，子数组最小值之和等。

伪代码（下一个更大）

text
stack empty (存下标)
for i in 0..n-1:
    while stack not empty and a[stack.top] < a[i]:
        j = stack.pop
        nextGreater[j] = i
    stack.push(i)

Java 模板

java
int[] next = new int[n];
Arrays.fill(next, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    while (!st.isEmpty() && a[st.peek()] < a[i]) {
        next[st.pop()] = i;
    }
    st.push(i);
}

5）堆 / TopK

适用： 动态取最小/最大，TopK，合并K路。

伪代码（TopK 小根堆保留 K 大）

text
heap empty
for x in arr:
    push x
    if heap size > K: pop
答案在堆中

Java 模板

java
PriorityQueue<Integer> pq = new PriorityQueue<>(); // min-heap
for (int x : arr) {
    pq.offer(x);
    if (pq.size() > K) pq.poll();
}

6）BFS（最短路：无权图 / 网格）

适用： 边权全1，求最短步数；层序遍历。

伪代码

text
queue push(start), dist[start]=0
while queue not empty:
    u = pop
    for v in neighbors(u):
        if dist[v] unset:
            dist[v]=dist[u]+1
            push(v)

Java 模板

java
ArrayDeque<int[]> q = new ArrayDeque<>();
q.offer(new int[]{sx, sy});
dist[sx][sy] = 0;

while (!q.isEmpty()) {
    int[] cur = q.poll();
    int x = cur[0], y = cur[1];
    for (int[] d : dirs) {
        int nx = x + d[0], ny = y + d[1];
        if (/* in bounds and not visited */) {
            dist[nx][ny] = dist[x][y] + 1;
            q.offer(new int[]{nx, ny});
        }
    }
}

7）DFS / 回溯

适用： 枚举方案、排列组合、搜索路径、约束满足。

伪代码（组合）

text
dfs(pos, path):
    if满足终止: record
    for choice in choices from pos:
        choose
        dfs(next, path)
        undo

Java 模板

java
void dfs(int idx) {
    if (/* done */) { res.add(new ArrayList<>(path)); return; }
    for (int i = idx; i < n; i++) {
        path.add(a[i]);
        dfs(i + 1);
        path.remove(path.size() - 1);
    }
}

8）动态规划 DP（最值/计数）

核心： 状态定义 + 转移 + 初始化 + 遍历顺序 + 答案位置。

伪代码（线性 DP）

text
dp[0]=base
for i=1..n-1:
    dp[i]=min/max over transitions
return dp[n-1] or best(dp)

Java 模板

java
long[] dp = new long[n];
Arrays.fill(dp, INF);
dp[0] = base;
for (int i = 1; i < n; i++) {
    // dp[i] from dp[i-1], dp[i-2]...
}

背包 DP 伪代码（0/1）

text
dp[0]=0
for each item (w,v):
    for j from W down to w:
        dp[j]=max(dp[j], dp[j-w]+v)

Java（0/1 背包）

java
int[] dp = new int[W + 1];
for (Item it : items) {
    for (int j = W; j >= it.w; j--) {
        dp[j] = Math.max(dp[j], dp[j - it.w] + it.v);
    }
}

9）并查集 DSU（连通性）

适用： 动态连通、成环判断、最小生成树 Kruskal。

伪代码

text
init parent[i]=i, size[i]=1
find(x): path compression
union(a,b): by size/rank

Java 模板

java
static class DSU {
    int[] p, sz;
    DSU(int n){ p=new int[n]; sz=new int[n]; for(int i=0;i<n;i++){p[i]=i; sz[i]=1;} }
    int find(int x){ return p[x]==x? x : (p[x]=find(p[x])); }
    boolean union(int a,int b){
        a=find(a); b=find(b);
        if(a==b) return false;
        if(sz[a]<sz[b]){ int t=a; a=b; b=t; }
        p[b]=a; sz[a]+=sz[b];
        return true;
    }
}

10）图最短路 Dijkstra（非负权）

适用： 边权非负。

伪代码

text
dist[start]=0
pq push (0,start)
while pq not empty:
    (d,u)=pop
    if d!=dist[u]: continue
    for (v,w) in edges[u]:
        if dist[v] > d+w:
            dist[v]=d+w
            push(dist[v], v)

Java 模板

java
long[] dist = new long[n];
Arrays.fill(dist, (long)4e18);
dist[s] = 0;
PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
pq.offer(new long[]{0, s});

while (!pq.isEmpty()) {
    long[] cur = pq.poll();
    long d = cur[0];
    int u = (int)cur[1];
    if (d != dist[u]) continue;
    for (int[] e : g[u]) { // e={v,w}
        int v = e[0], w = e[1];
        if (dist[v] > d + w) {
            dist[v] = d + w;
            pq.offer(new long[]{dist[v], v});
        }
    }
}

11）字符串：KMP（找模式串）

适用： 子串查找 O(n+m)。

伪代码（next 数组）

text
next[0]=0
for i=1..m-1:
    j=next[i-1]
    while j>0 and p[i]!=p[j]: j=next[j-1]
    if p[i]==p[j]: j++
    next[i]=j

Java（next + 匹配骨架）

java
int[] buildNext(char[] p){
    int m=p.length;
    int[] ne=new int[m];
    for(int i=1,j=0;i<m;i++){
        while(j>0 && p[i]!=p[j]) j=ne[j-1];
        if(p[i]==p[j]) j++;
        ne[i]=j;
    }
    return ne;
}
int kmp(String s, String pat){
    char[] a=s.toCharArray(), p=pat.toCharArray();
    int[] ne=buildNext(p);
    for(int i=0,j=0;i<a.length;i++){
        while(j>0 && a[i]!=p[j]) j=ne[j-1];
        if(a[i]==p[j]) j++;
        if(j==p.length) return i - p.length + 1; // first index
    }
    return -1;
}

12）输入输出：竞赛常用 FastScanner

java
static class FastScanner {
    private final byte[] buffer = new byte[1 << 16];
    private int ptr = 0, len = 0;
    private final InputStream in;
    FastScanner(InputStream is){ in = is; }
    private int read() throws IOException {
        if (ptr >= len) {
            len = in.read(buffer);
            ptr = 0;
            if (len <= 0) return -1;
        }
        return buffer[ptr++];
    }
    long nextLong() throws IOException {
        int c;
        do { c = read(); } while (c <= ' ' && c != -1);
        long sign = 1;
        if (c == '-') { sign = -1; c = read(); }
        long val = 0;
        while (c > ' ') {
            val = val * 10 + (c - '0');
            c = read();
        }
        return val * sign;
    }
    int nextInt() throws IOException { return (int) nextLong(); }
    String next() throws IOException {
        int c;
        do { c = read(); } while (c <= ' ' && c != -1);
        StringBuilder sb = new StringBuilder();
        while (c > ' ') { sb.append((char)c); c = read(); }
        return sb.toString();
    }
}

如果你愿意，我还可以把这些模板整理成一份可直接复制的 Java “刷题母板（Main + 常用工具类 + 典型函数）”，以及按题型给你一个“看到题目关键词就选模板”的快速索引。你平时主要刷 LeetCode 还是牛客/洛谷/Codeforces？（不回答也行，我也可以按通用竞赛风格直接给母板。）

Answer 2

好，我们把 动态规划 DP 单独、系统、从“怎么想 → 怎么写伪代码 → 怎么落 Java” 讲透。你以后看到 DP 题，基本就按这个流程机械套。

一、什么情况下“应该想到 DP”？

题目同时满足下面 2～3 个特征，80% 是 DP：

最值 / 方案数 / 可行性
- 最大 / 最小 / 最多 / 最少
- 有多少种方案
- 是否能做到
有“阶段性决策”
- 前 i 个元素
- 走到第 i 步
- 用了前 i 件物品
- 处理到字符串第 i 位
子问题会被重复用到
- 暴力递归会算很多次同一个状态

👉 一句话判断法：
“当前选择只和之前的状态有关，而与更早的细节无关”

二、DP 的 5 个固定步骤（必背）

90% 的 DP 题，差别只在第 1、2 步

① 定义状态（最关键）

一句话描述一个 dp 状态：

dp[i][j] 表示：在「前 i 个 / 到位置 i / 用了 i 步」的前提下，状态为 j 时的最优值 / 方案数

📌 常见状态含义模板：

状态	含义
dp[i]	到第 i 个位置的最优解
dp[i][j]	前 i 个元素，某种限制为 j
dp[i][j][k]	多加一个维度（次数/状态）

② 写转移方程（怎么从过去来）

想最后一步在干嘛

最后一步选了什么？
最后一步不选会怎样？
最后一步和谁有关？

👉 一般形式：

dp[当前状态] = min / max / sum ( dp[之前状态] + 当前代价 )

③ 初始化（边界条件）

dp[0] 怎么办？
不可能的状态设为 ∞ / -∞ / 0

④ 确定遍历顺序

从小到大？
从大到小？
哪些状态必须先算？

⑤ 返回答案

dp[n]？
max(dp[i])？
dp[n][m]？

三、最基础的 DP：线性 DP（一维）

例 1：爬楼梯（模板题）

题意：一次走 1 或 2 步，走到 n 有多少种方式？

状态定义

dp[i] = 到第 i 阶的方法数

转移

dp[i] = dp[i-1] + dp[i-2]

初始化

text
dp[0] = 1
dp[1] = 1

Java

java
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];

👉 空间优化

java
int a = 1, b = 1;
for (int i = 2; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
}
return b;

例 2：打家劫舍（不能选相邻）

状态

dp[i] = 抢到第 i 家为止的最大金额

转移

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Java

java
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];

int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);

for (int i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];

四、二维 DP（最重要）

1️⃣ 背包问题（DP 的祖宗）

0/1 背包（每个物品只能选一次）

状态定义

dp[i][j] = 用前 i 件物品，容量为 j 的最大价值

转移

text
不选：dp[i][j] = dp[i-1][j]
选：  dp[i][j] = dp[i-1][j-w[i]] + v[i]

伪代码

text
for i in 1..n:
    for j in 0..W:
        dp[i][j] = dp[i-1][j]
        if j >= w[i]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])

Java（二维）

java
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= w[i - 1]) {
            dp[i][j] = Math.max(dp[i][j],
                    dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
    }
}

一维压缩（高频考点）

j 必须倒序

java
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

2️⃣ 子序列 DP（最长递增子序列 LIS）

状态

dp[i] = 以 i 结尾的 LIS 长度

转移

dp[i] = max(dp[j] + 1) where j < i and a[j] < a[i]

Java（O(n²) 版）

java
int n = a.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);

int ans = 1;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (a[j] < a[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    ans = Math.max(ans, dp[i]);
}
return ans;

五、区间 DP（难点）

特征：

对一个区间 [l, r] 做决策
最后一次“分割点 / 合并点”

例：矩阵链乘法 / 合并石子

状态

dp[l][r] = 合并区间 [l,r] 的最小代价

转移

dp[l][r] = min(dp[l][k] + dp[k+1][r] + cost(l,r))

遍历顺序（重点！）

按区间长度从小到大

伪代码

text
for len = 2..n:
    for l = 0..n-len:
        r = l+len-1
        dp[l][r] = INF
        for k = l..r-1:
            dp[l][r] = min(...)

六、DP 常见“坑点总结”

❌ 状态定义不清
👉 一定要能用一句人话解释 dp[i][j]

❌ 转移方向写反
👉 看“当前状态依赖谁”，谁在前就先算谁

❌ 忘了初始化不合法状态
👉 最小值问题用 INF，最大值用 -INF

❌ 背包 j 顺序写错
👉

0/1 背包：倒序
完全背包：正序

七、DP 解题万能模板（先写这个）

java
// 1. 定义 dp 数组
// dp[i][j] 含义

// 2. 初始化
Arrays.fill(dp, INF);
dp[0][0] = base;

// 3. 状态转移
for (...) {
    for (...) {
        dp[...] = ...
    }
}

// 4. 返回答案
return dp[...];

如果你愿意，下一步我可以帮你做 3 件事之一（都很实用）：

1️⃣ 把 DP 题型分类成「看到关键词就会选状态」的速查表
2️⃣ 用 一道 LeetCode 中等题，从 0 带你完整推 DP
3️⃣ 给你一套 “DP 模板 + 常见错误对照表”（适合考前速看）

你选哪个？

Answer 3

好，那我直接给你一套 「DP 经典用例大全」，每一道都做到：

题目直觉 → 为什么是 DP → 状态如何定义 → 转移怎么想 → 伪代码 → Java 实现 → 常见坑

你把这几道吃透，80% 的 DP 题都会“眼熟”。

例 1：爬楼梯（最基础的一维 DP）

题目

一次可以走 1 或 2 步，走到第 n 阶有多少种方法？

一眼为什么是 DP？

有 阶段性：走到第 i 阶
求 方案数
走到第 i 阶的方法，只和 i-1、i-2 有关

👉 典型线性 DP

状态定义

dp[i] = 走到第 i 阶的方法数

为什么这样定义？

问题目标正是“走到某一阶”
子问题自然：走到更小的阶

状态转移（关键）

最后一步：

从 i-1 走 1 步
从 i-2 走 2 步

dp[i] = dp[i-1] + dp[i-2]

初始化

text
dp[0] = 1  // 什么都不做也是一种方式
dp[1] = 1

⚠️ dp[0] = 1 很关键，否则 dp[2] 算不对

伪代码

text
dp[0]=1, dp[1]=1
for i=2..n:
    dp[i]=dp[i-1]+dp[i-2]
return dp[n]

Java

java
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];

常见坑

❌ dp[0] 忘了初始化
❌ 用递归导致超时（重复子问题）

例 2：打家劫舍（不能选相邻）

题目

一排房子，不能抢相邻的，求最大金额。

为什么是 DP？

每个位置都要做“选 / 不选”的决策
当前选择只影响后续相邻关系

状态定义

dp[i] = 抢到第 i 家为止的最大金额

转移怎么想？

最后一家（第 i 家）：

情况 1：不抢 i

dp[i] = dp[i-1]

情况 2：抢 i

dp[i] = dp[i-2] + nums[i]

取最大：

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

初始化

text
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])

Java

java
int n = nums.length;
if (n == 0) return 0;
if (n == 1) return nums[0];

int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);

for (int i = 2; i < n; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[n - 1];

本质总结

选当前 ⇒ 跳过上一个

例 3：0/1 背包（DP 核心模型）

题目

n 件物品，每件有重量 w 和价值 v，背包容量 W，求最大价值。

为什么是 DP？

多维限制（物品 + 容量）
每件物品只能选一次（0/1）

状态定义（标准）

dp[i][j] = 用前 i 件物品，容量为 j 的最大价值

转移怎么想？

第 i 件物品：

不选

dp[i][j] = dp[i-1][j]

选（前提 j>=w[i]）

dp[i][j] = dp[i-1][j-w[i]] + v[i]

取最大

伪代码

text
for i=1..n:
    for j=0..W:
        dp[i][j]=dp[i-1][j]
        if j>=w[i]:
            dp[i][j]=max(dp[i][j], dp[i-1][j-w[i]]+v[i])

Java（二维）

java
int[][] dp = new int[n + 1][W + 1];
for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= W; j++) {
        dp[i][j] = dp[i - 1][j];
        if (j >= w[i - 1]) {
            dp[i][j] = Math.max(dp[i][j],
                    dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
    }
}

一维压缩（高频）

java
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
    for (int j = W; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

⚠️ 必须倒序，否则会重复选物品

例 4：最长递增子序列 LIS（子序列 DP）

题目

求最长严格递增子序列长度。

状态定义

dp[i] = 以 i 结尾的 LIS 长度

转移逻辑

枚举前一个位置 j：

text
if a[j] < a[i]:
    dp[i] = max(dp[i], dp[j] + 1)

Java

java
int n = a.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);

int ans = 1;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (a[j] < a[i]) {
            dp[i] = Math.max(dp[i], dp[j] + 1);
        }
    }
    ans = Math.max(ans, dp[i]);
}
return ans;

思想

“我做结尾，前面谁能接我？”

例 5：最长公共子序列 LCS（二维 DP 代表）

状态

dp[i][j] = s1 前 i 个字符 与 s2 前 j 个字符 的 LCS 长度

转移

相等：

dp[i][j] = dp[i-1][j-1] + 1

不相等：

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Java

java
int n = s1.length(), m = s2.length();
int[][] dp = new int[n + 1][m + 1];

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (s1.charAt(i - 1) == s2.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[n][m];

总结一句话（非常重要）

DP = 明确状态 + 想最后一步 + 找依赖 + 控制顺序

下一步我强烈建议你做其中一个：

1️⃣ 我带你 手推一整道 DP 中等题（含画表）
2️⃣ 给你一张 「DP 题型 → 状态定义」速查表
3️⃣ 专门讲 DP 面试常问 & 易错点合集

你选一个，我继续给你“打通任督二脉”。

سؤال

الإجابة

0）通用刷题流程（先想清楚再写）

1）双指针 / 滑动窗口

伪代码（典型：最长满足条件）

Java 模板

2）二分答案（最常用的“可行性判定”）

伪代码

Java 模板（找最小可行）

3）前缀和 / 差分

前缀和伪代码

Java 模板

差分伪代码（区间加 v）

4）单调栈（Next Greater / 区间贡献）

伪代码（下一个更大）

Java 模板

5）堆 / TopK

伪代码（TopK 小根堆保留 K 大）

Java 模板

6）BFS（最短路：无权图 / 网格）

伪代码

Java 模板

7）DFS / 回溯

伪代码（组合）

Java 模板

8）动态规划 DP（最值/计数）

伪代码（线性 DP）

Java 模板

背包 DP 伪代码（0/1）

Java（0/1 背包）

9）并查集 DSU（连通性）

伪代码

Java 模板

10）图最短路 Dijkstra（非负权）

伪代码

Java 模板

11）字符串：KMP（找模式串）

伪代码（next 数组）

Java（next + 匹配骨架）

12）输入输出：竞赛常用 FastScanner

سؤال

الإجابة

一、什么情况下“应该想到 DP”？

二、DP 的 5 个固定步骤（必背）

① 定义状态（最关键）

② 写转移方程（怎么从过去来）

③ 初始化（边界条件）

④ 确定遍历顺序

⑤ 返回答案

三、最基础的 DP：线性 DP（一维）

例 1：爬楼梯（模板题）

状态定义

转移

初始化

Java

例 2：打家劫舍（不能选相邻）

状态

转移

Java

四、二维 DP（最重要）

1️⃣ 背包问题（DP 的祖宗）

0/1 背包（每个物品只能选一次）

状态定义

转移

伪代码

Java（二维）

一维压缩（高频考点）

2️⃣ 子序列 DP（最长递增子序列 LIS）

状态

转移

Java（O(n²) 版）

五、区间 DP（难点）

例：矩阵链乘法 / 合并石子

状态

转移

遍历顺序（重点！）

伪代码

六、DP 常见“坑点总结”

七、DP 解题万能模板（先写这个）

سؤال