> For the complete documentation index, see [llms.txt](https://docs.1l.lol/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs.1l.lol/advanced-dp/dp-2d.md).

# 二维 DP 与最值优化

### 二维状态

当决策依赖两个维度时，用二维数组 `dp[i][j]`。例如网格路径、编辑距离、双序列问题。

```cpp
// 网格从 (1,1) 到 (n,m) 的路径数（只能向右/下）
dp[1][1] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
        if (i == 1 && j == 1) continue;
        dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
```

### 最值优化

```cpp
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];   // 最大路径和
```

### 解题套路

1. 确定状态含义；
2. 初始化边界；
3. 写出转移方程；
4. 确定遍历顺序（保证依赖项已算好）；
5. 输出答案。

### 常见二维 DP

* 网格路径 / 最大路径和
* 最长公共子序列、编辑距离
* 二维背包、区间问题


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://docs.1l.lol/advanced-dp/dp-2d.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `automate deployments from our CI pipeline` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.