二维动态规划

1、二维动态规划

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

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

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

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

2、例子－路径总数

P282 走出迷宫的方法数

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

假设A为(1, 1)的点，B为(m, n)

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

则状态转移方程为：

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

P502 最长公共子序列

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

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

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

状态转移方程：

当i=0或j=0时：dp[i, j] = 0
当i、j>0且ai=bj：dp[i, j] = dp[i-1, j-1] + 1
当i、j>0且ai!=bj：dp[i, j] = max(dp[i-1, j], dp[i, j-1])

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

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

以上：

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

参考代码

#include<iostream>
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 f2(int x, int y)
{
  for(int i = 1; i <= m; ++i)
    dp[i][1] = 1;
  for(int i = 1; i <= n; ++i)
    dp[1][i] = 1;
  for(int i = 2; i <= m; ++i)
  {
    for(int j = 2; j <= n; ++j)
    {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }
  }
  return dp[m][n];
}
int main()
{
  cin >> n >> m;
  cout << f2(m, n);
  return 0;
}

三、练习

取苹果

P343 取苹果

题目

平面上有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. 输出

四、参考代码

#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;
}

例题-限数棋子摆放

限数棋子摆放

在棋盘的某一行上（长度为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]

三、实验步骤

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

参考代码

#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;
}

例题：1258：【例9.2】数字金字塔

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

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

【输入】

第一个行包含R(1<= R<=1000)，表示行的数目。 后面每行为这个数字金字塔特定行包含的整数。 所有的被供应的整数是非负的且不大于100。

【输出】单独的一行，包含那个可能得到的最大的和。

【输入样例】

5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11

【输出样例】

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

NOIP普及组真题

真题列表

1. NOIPJ2002D 过河卒

2. 数字游戏，NOIP2003普及组

3. 传球游戏，NOIP2008普及组 T3

4. 子矩阵，NOIP2014普及组T4