入门级-线性动态规划-二维

# 二维动态规划

---

## 1、二维动态规划

动态规划入门里，状态都只有一个维度，一般为dp[k]，称之为线性动态规划。

当维度有两个的时候，需要用二维的状态来解决问题，例如棋盘、矩阵、路径等类别的问题。

更准确的说，二维动态规划指线性动态规划的拓展，在一个平面上做动态规划。

规律：当前格子的状态，往往与左边、上边、左上的格子状态有关。

---

## 2、例子－路径总数

[P282 走出迷宫的方法数](http://39.99.183.126:8888/p/282)

对于m*n的矩阵，每个点只能往下或者往右，计算从A点走到B点一共有多少种路径。

---

假设A为(1, 1)的点，B为(m, n)
![image](http://39.99.183.126:8888/file/2/RSJlG37cv2mPS8Gt1O67v.png)

---

定义状态：定义`dp[i][j]`为从A点到达点(i, j)的路径总数

则状态转移方程为：

```c++
i=0 或 j= 0：dp[i][j] = 0
dp[1][1] = 1
i, j >1：dp[i][j] = dp[i-1][j] + dp[i][j-1]
```

---

## 3、例子－LCS

[P2248 最长公共子序列](http://39.99.183.126:8888/p/2248)

最长公共子序列(LCS)的长度：子序列中的每个元素都能在两个序列中找到， 而且先后顺序和原序列中的先后顺序一致。

例如：$A=[1, 2, 3, 4, 5], B=[6, 1, 3, 2, 4, 7]$，最长公共子序列为1 2 4， 或 1 3 4，长度都为3

---

定义状态 $dp[i][j]$ 为$A_i$ 与$B_j$的LCS的长度，i 和 j 就代表了两个维度。

状态转移方程：

- 当i=0或j=0时：$dp[i, j] = 0 $
- 当i、j>0且$A_i=B_j$：$dp[i, j] = dp[i-1, j-1] + 1$
- 当i、j>0且$A_i\ne B_j$：$dp[i, j] = max(dp[i-1, j], dp[i, j-1])$

---

对于二维动态规划的理解，实际就是根据矩阵进行递推，如下：

|A\B|-|6|1|3|2|4|7|
|---|---|---|---|---|---|---|---|
|0|0|0|0|0|0|0|0|
|1|0|0|1|1|1|1|1|
|2|0|0|1|1|2|2|2|
|3|0|0|1|2|2|2|2|
|4|0|0|1|2|2|3|3|
|5|0|0|1|2|2|3|3|

以上：

第一行和第一列都为0，然后依次往左往右填充
如果两个元素相同，则取左上的值加1
如果两个元素不同，则取左边、上边的最大值
最右下就是递推的结果

---

### 参考代码

```c++
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1005;
string s1, s2;
int ans, n;
int dp[N][N];  //表示第一个序列i位置，第二个序列j位置时最长公共子序列的长度
void handle(void)
{
    for (int i = 1; i < s1.size(); i++)
        for (int j = 1; j < s2.size(); j++)
        {
            if (s1[i] == s2[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    cout << dp[s1.size() - 1][s2.size() - 1] << endl;
}
void initInput(void)
{
    cin >> s1 >> s2;
    s1 = ' ' + s1, s2 = ' ' + s2;
}
int main(void)
{
    initInput();
    handle();
    return 0;
}
```

---

## 三、练习

[P343  取苹果](http://39.99.183.126:8888/p/343)

平面上有N*M个格子，每个格子中放着一定数量的苹果。

你从左上角的格子开始， 每一步只能向下走或是向右走，每次走到一个格子上就把格子里的苹果收集起来， 这样下去，你最多能收集到多少个苹果。

输入样例：第一行为n和m，然后是n行每行m个数（苹果数）：

```
3 3
1 4 4
5 3 2
3 5 1
```

输出样例：最大苹果数

```
15
```

数据范围：

```
1<=n, m<=1000
0<=每个数<=10000
```

---

### 二、分析

##### 1、理解题目

二维动态规划，每个格子只能从左边或上边过来，总数要么是左边格子总共收集的苹果数＋当前格子苹果数，要么是上边格子总共收集的苹果数＋当前格子苹果数。

---

##### 2、思路

定义状态：设`dp[i][j]`为从最左上到达格子(i, j)能收集的最大苹果数。

状态转移方程：

```
i=0 或 j= 0：dp[i][j] = 0
dp[1][1] = a[1][1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]
```

注意这里的0坐标是为了统一转移方程用。

---

#### 三、操作步骤

请自己实现以下步骤：

1. 数据定义和输入
2. 状态初始化
3. 状态转移方程
4. 输出

---

#### 四、参考代码

```c++
#include<iostream>
#include<cmath>
using namespace std;
int m, n;
int cnt; 
int f1(int x, int y)
{
  if( x < 1 || y < 1)
  {
    return 0;
  }
  if(x == 1 || y == 1)
  {
    return 1;
  }
  return f1(x, y - 1) + f1(x - 1, y);
}

const int M = 1005;
const int N = 1005;
int dp[M][N];
int a[M][N];
int f2(int x, int y)
{
  for(int i = 1; i <= n; i++)
  {
    for(int j = 1; j <= m; ++j)
    {
      cin >> a[i][j];
    }
  }
  dp[1][1] = a[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] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
    }
  }
  return dp[n][m];
}
int main()
{
  cin >> n >> m;
  
  cout << f2(n, m);
  return 0;
}
```

---

### 练习-
[限数棋子摆放](http://39.99.183.126:8888/p/4135)

在棋盘的某一行上（长度为n），摆放m个棋子，使得棋子之间互不相邻，求方案数。

输入样例：

5 2
输出样例：

6
数据范围：1<=n、m<=5000

---

#### 二、分析

##### 1、思路

设`f[i][j]`表示前i个位置，放置j个棋子，第i位置不放的方案数， `g[i][j]`表示第i个位置必放的方案数。

则有：

```
f[i][j] = f[i-1][j] + g[i-1][j]
g[i][j] = f[i-1][j-1]
```

---

理解：

第i位置不放，则前一位置可放，也可以不放，棋子数不变。
第i位置必放，用掉一个棋子，前一位置只能不放。
最后答案为`f[n][m]+ g[n][m]`。

---

##### 2、状态递推

初始值：

```
f[0][0]=1;
g[0][0]=0;
```

递推公式：

```
f[i][j] = f[i-1][j] + g[i-1][j]
g[i][j] = f[i-1][j-1]
```

---
### 参考代码
```c
#include <iostream>
using namespace std;

const int N=5005;
int n, m;
int f[N][N], g[N][N];

int main() {
  cin>>n>>m;
  f[0][0]=1;
  for(int i=1;i<=n; i++)
    for(int j=0; j<=min(m, i); j++) {
      if(j != 0)
      g[i][j] = f[i-1][j-1];
      f[i][j] = f[i-1][j] + g[i-1][j];
    }
  
  cout<<(f[n][m] + g[n][m])<<endl;  
  return 0;
}

```
---

#### 三、步骤

1. 数据定义与输入
2. 状态定义与转移
3. 输出结果

---

## 例题：[2241：【例9.2】数字金字塔](http://39.99.183.126:8888/p/2241)

观察下面的数字金字塔。写一个程序查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以从当前点走到左下方的点也可以到达右下方的点。

![img](http://ybt.ssoier.cn:8088/pic/1284.gif)

在上面的样例中,从13到8到26到15到24的路径产生了最大的和86。

---

### 分析

|dp[i][j]|1|2|3|4|5|
|---|---|---|----|-----|----|
|1||||||
|2||||||
|3|||-|-|-|
|4|$12+max(dp[i+1][j],dp[i+1][j+1])=39$|||-||
|5|max(12,7)+6=18|max(7,13)+14=27|max(13,24)+15=39|max(24,11)+8=32|-|
|6|12|7|13|24|11|

---

## 习题
 
1. [**NOIPJ2002D**  过河卒](http://39.99.183.126:8888/p/NOIPJ2002D)
 
4. [数字游戏，NOIP2003普及组](http://39.99.183.126:8888/p/445)
5. [传球游戏，NOIP2008普及组 T3](http://39.99.183.126:8888/p/NOIPJ2008C)
6. [子矩阵，NOIP2014普及组T4](http://39.99.183.126:8888/p/NOIPJ2014D)