<学习笔记>动态规划——中级进阶

2017-10-22

这篇文章我们开始考虑二维的问题了。
示例一
平面上有n*m个方格，每个格子中放一定数量苹果，我们从左上角的第一个格子开始走，接下来我们的每一步只能向下或者向右走，每到一个格子，
就把里面的苹果收集起来，走啊走，问最后最多可以收集多少个苹果。
所有的dp问题其实都大同小异，我们要求到达某个格子收集到的苹果的数量，就要求上一个格子已有的苹果的数量，这其实就好像一个逆推的
过程，最后就一直推到左上角的那个格子了。一回头，一步一步，我们的结果就出来了。
设格子的行row,列为col,某个格子最多收集到的苹果数量为s[i][j],某个格子放的苹果数量为a[i][j];
假设当前到达了i行j列的格子，那么到达这个方格的路径只有两种，就是它的上面和左面的格子，
那么我们就很容易写出我们的递推公式，

1	s[i][j]=a[i][j]+max{a[i-1][j],a[i][j-1];i>0,j>0,0};

依然根据递推公式写出代码：

#include<iostream>
using namespace std;
int main() {
	int a[6][7] = {
	{12,14,3,5,6,8,21},
	{3,5,7,1,9,34,12},
	{4,6,7,18,1,23,11},
	{9,11,13,24,6,5,3},
	{21,22,3,4,17,9,5},
	{12,3,5,8,22,9,10}
	};
	int s[6][7];
	s[0][0] = a[0][0];
	for (int i = 0; i < 6; i++) {
		for (int j = 0; j < 7; j++) {
			if (i > 0 && j > 0) {
				if (s[i][j - 1] > s[i - 1][j]) {
					s[i][j] = a[i][j] + s[i][j - 1];
				}
				else{
					s[i][j] = a[i][j] + s[i - 1][j];
				}
			}
			else if (i == 0&&j>0) {
				s[i][j] = a[i][j]+s[i][j-1];
			}
			else if(j==0&&i>0){
				s[i][j] = a[i][j] + s[i-1][j];
			}
		}
	}
	cout << s[5][6] << endl;
	return 0;
}

写到这里，似乎发现，我们做dp问题其实最重要的就是要找出递推方程，剩下的就是小case了。
示例二
这个问题和示例一太像了。。
有一个矩形滑雪场，可以用r行c列来表示它的地形，地形较高那么元素就较大一些，反之。
为了得到更快的滑雪速度，滑雪的方向必须是向下倾斜的，规定可以从上下左右四个方向来寻求路径。
我们要求的结果是要找到一条最长的路径溜下去。
先看我们的常规思路。
那么我们第一步肯定是要找到这块地形最高的位置了。
接下来，我们依然沿用求子问题的方式来进行求解。我们如果求最高位置为起点的最长路径，那么就是要求其周围四个
邻接位置的路径，然后取其中最大的那一条。
以此类推，假如我们找到了四个中的那个所谓的子问题解，那么就以这个邻接位置为当前位置，继续重复上述过程，求解
此时的邻接路径的最长的那一条。
设s[i][j]=k，表示在i行j列的位置取得的最长路径为k；
那么

1	s[i][j]=max{s[i-1][j],s[i+1][j],s[i][j-1],s[i][j+1]}+1;

通过记忆化搜索深度递归即可。
接下来我们看另一种思路。
对比一下求最长非降子序列的问题，其实我们可以将这道题进行化归。
我们仔细推敲一下，我们先把这个二维的矩阵化为一个一维的是数组，这一步实现了降维。
阅读我们问题，很明显有两个要点，一个是邻接，一个是下降。
那么我们必须将原来的二维数组的索引记录下来，为了判定是否相邻，还要高度，就是我们一数组的值。
那么我们可以定义一个类

class pos{
  int h;
  int x;
  int y;
};

我们将这个pos进行排序，排序的依据是高度。
降维后，我们得到一个存储着若干个pos对象的数组，然后依据对象的x和y属性，判断原矩阵的元素是否相邻进行处理。
类比最长非降序子列的问题，我们可以结合上述改造写出代码。

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
class pos {
public:
	int h;
	int x;
	int y;
};
bool operator<(pos p1, pos p2) {
	return p1.h < p2.h;
}
bool check(pos p1,pos p2) {
	if (((p1.x == p2.x&&abs(p1.y-p2.y) == 1)
		||(p1.y == p2.y&&abs(p1.x - p2.x) == 1))
		&&p1.h>p2.h) {
		return true;
	}
	return false;
}
int main() {
	int a[5][5] = {
	{1,2,3,4,5},
	{16,17,18,19,6},
	{15,24,25,20,7},
	{14,23,22,21,8},
	{13,12,11,10,9}
	};
	pos ps[25];
	int dp[25];
	int k = 0;
	for (int i = 0; i < 5; i++) {
		for (int j=0; j < 5; j++) {
			pos p;
			p.x = i;
			p.y = j;
			p.h = a[i][j];
			ps[k++]=p;
		}
	}
	int maxlen = 1;
	sort(ps,ps+25);
	for (int i = 0; i < 25; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (check(ps[i], ps[j])) {
				dp[i] =max(dp[i],dp[j]+1);
			}
		}
		if (dp[i] > maxlen)maxlen = dp[i];
	}
	cout << maxlen;
	int o;
	cin >> o;
	return 0;
}