格子取数问题
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.03.md
https://github.com/tdoly/The-Art-Of-Programming-by-July/blob/master/ebook/zh/34-35.0.md
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/code/c/4.2%EF%BC%9A%E6%A0%BC%E5%AD%90%E5%8F%96%E6%95%B0%E9%97%AE%E9%A2%98.c
============================================
有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。
一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。
发现两人每走一步都有：x1+y1=x2+y2=当前走的步数
如果知道走的步数，只要知道某人的横坐标即可推算出其纵坐标。因此设dp[i][j][k]表示两人走i步，第一个人到达第i行，第二个人到达第k行时的最大价值。
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-1][k],dp[i-1][j][k-1],dp[i-1][j-1][k-1])+M[x1][y1]+M[x2][y2] (x1!=x2)
时间和空间复杂度优化到O((n+m)*n^2)
注意到，状态转移方程中dp[i][j][k]的状态只与前一步的状态有关，因此空间复杂度还可以优化到O(n^2)
上面的状态转移方程为x1!=x2时的，由于当两人走过同一个格子时，该格子价值只算一次，因此当x1=x2时，加上M[x1][y1]即可。
http://accepted.com.cn/51nod1084/
还是尝试两个人同时走……，有个好处是，两个人一起走的话，只能在同一步经过相同的格子，这是由距离决定的。因为第step步，所在的格子距离起点的曼哈顿距离|x - x' | + |y - y'| = step……所以走一次时，状态是dp[(x,y)]由(x - 1, y) (x, y - 1)决定，现在状态是dp[(x1,y1)(x2,y2)]由4个状态确定即dp[(x1 - 1, y1)(x2 - 1, y2)] dp[(x1 - 1, x2, y2 - 1)] dp[(x1, y1 - 1)(x2 - 1, y2)] dp[(x1, y1 - 1) (x2 , y2 - 1)]确定
Read full article from 格子取数问题
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/05.03.md
https://github.com/tdoly/The-Art-Of-Programming-by-July/blob/master/ebook/zh/34-35.0.md
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/code/c/4.2%EF%BC%9A%E6%A0%BC%E5%AD%90%E5%8F%96%E6%95%B0%E9%97%AE%E9%A2%98.c
1、给定m*n的矩阵，每个位置是一个非负整数，从左上角开始，每次只能朝右和下走，走到右下角，但只走一次，求总和最小的路径。
提示：因为只走一次，所以相对来说比较简单，dp[0, 0]=a[0, 0]，且dp[x, y] = min(dp[x-1, y] + a[x, y]dp[x, y-1] + a[x, y])。
2、给定m*n的矩阵，每个位置是一个整数，从左上角开始，每次只能朝右、上和下走，并且不允许两次进入同一个格子，走到右上角，最小和。
分析：@cpcs ：我们按列dp，假设前一列的最优值已经算好了，一旦往右就回不去了。枚举我们从对固定的(y-1)列，我们已经算好了最优值，我们枚举行x，朝右走到(x,y),然后再从(x,y)朝上走到(x,0)，再从(x,y)朝下走到(x,n-1)，所有这些第y列的值，作为第y列的候选值，取最优。 实际上，我们枚举了进入第y列的位置和在最终停在第y列的位置。这样保证我们不重复经过一个格子，也能保证我们不会往“左”走。
============================================
有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。
也就是说，上面图二中的走法太追求每一次最优，所以第一次最优，导致第二次将是很差；而图三第一次虽然不是最优，但保证了第二次不差，所以图三的结果优于图二。由此可知不要只顾局部而贪图一时最优，而丧失了全局最优。
解法一、直接搜索
局部贪优不行，我们可以考虑穷举，但最终将导致复杂度过高，所以咱们得另寻良策。 @西芹_new，针对此题，可以使用直接搜索法，一共搜（2n-2）步，每一步有四种走法，考虑不相交等条件可以剪去很多枝，代码如下：
//copyright@西芹_new 2013
#include "stdafx.h"
#include <iostream>
using namespace std;
#define N 5
int map[5][5]={
{2,0,8,0,2},
{0,0,0,0,0},
{0,3,2,0,0},
{0,0,0,0,0},
{2,0,8,0,2}};
int sumMax=0;
int p1x=0;
int p1y=0;
int p2x=0;
int p2y=0;
int curMax=0;
void dfs( int index){
if( index == 2*N-2){
if( curMax>sumMax)
sumMax = curMax;
return;
}
if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))
{
if( p1x>= p2x && p1y >= p2y )
return;
}
//right right
if( p1x+1<N && p2x+1<N ){
p1x++;p2x++;
int sum = map[p1x][p1y]+map[p2x][p2y];
curMax += sum;
dfs(index+1);
curMax -= sum;
p1x--;p2x--;
}
//down down
if( p1y+1<N && p2y+1<N ){
p1y++;p2y++;
int sum = map[p1x][p1y]+map[p2x][p2y];
curMax += sum;
dfs(index+1);
curMax -= sum;
p1y--;p2y--;
}
//rd
if( p1x+1<N && p2y+1<N ) {
p1x++;p2y++;
int sum = map[p1x][p1y]+map[p2x][p2y];
curMax += sum;
dfs(index+1);
curMax -= sum;
p1x--;p2y--;
}
//dr
if( p1y+1<N && p2x+1<N ) {
p1y++;p2x++;
int sum = map[p1x][p1y]+map[p2x][p2y];
curMax += sum;
dfs(index+1);
curMax -= sum;
p1y--;p2x--;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
curMax = map[0][0];
dfs(0);
cout <<sumMax-map[N-1][N-1]<<endl;
return 0;
}
2、为了方便描述，再对矩阵做一个编号（给这个矩阵起个名字叫M2）：
M2
0 0 0 0 0
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
把之前定的M1矩阵也再贴下：
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
我们先看M1，在经过6步后，肯定处于M1中编号为6的位置。而M1中共有3个编号为6的，它们分别对应M2中的2 3 4。故对于M2来说，假设第1次经过6步走到了M2中的2，第2次经过6步走到了M2中的4，DP[s,i,j] 则对应 DP[6,2,4]。由于s = 2n - 2,0 <= i<= <= j <= n，所以这个DP共有O(n^3)个状态。
M1
0 1 2 3 4
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
再来分析一下状态转移，以DP[6,2,3]为例(就是上面M1中加粗的部分)，可以到达DP[6,2,3]的状态包括DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]。
3、下面，我们就来看看这几个状态：DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]，用加粗表示位置DP[5,1,2] DP[5,1,3] DP[5,2,2] DP[5,2,3] （加红表示要达到的状态DP[6,2,3]）
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
2 3 4 5 6 2 3 4 5 6 2 3 4 5 6 2 3 4 5 6
3 4 5 6 7 3 4 5 6 7 3 4 5 6 7 3 4 5 6 7
4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8
因此：
DP[6,2,3] = Max(DP[5,1,2] ，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]) + 6,2和6,3格子中对应的数值 （式一）
上面（式一）所示的这个递推看起来没有涉及：“如果两次经过同一个格子，那么该数只加一次的这个条件”，讨论这个条件需要换一个例子，以DP[6,2,2]为例：DP[6,2,2]可以由DP[5,1,1]，DP[5,1,2]，DP[5,2,2]到达，但由于i = j，也就是2次走到同一个格子，那么数值只能加1次。 所以当i = j时，
DP[6,2,2] = Max(DP[5,1,1]，DP[5,1,2]，DP[5,2,2]) + 6,2格子中对应的数值 （式二）
4、故，综合上述的（式一），（式二）最后的递推式就是
if(i != j)
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j - 1], DP[s - 1, i, j]) + W[s,i] + W[s,j]
else
DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j]) + W[s,i]
其中W[s,i]表示经过s步后，处于i位置，位置i对应的方格中的数字。下一节我们将根据上述DP方程编码实现。
2.2、DP方法实现
为了便于实现，我们认为所有不能达到的状态的得分都是负无穷，参考代码如下
http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1084一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。
如果知道走的步数，只要知道某人的横坐标即可推算出其纵坐标。因此设dp[i][j][k]表示两人走i步，第一个人到达第i行，第二个人到达第k行时的最大价值。
dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-1][k],dp[i-1][j][k-1],dp[i-1][j-1][k-1])+M[x1][y1]+M[x2][y2] (x1!=x2)
时间和空间复杂度优化到O((n+m)*n^2)
注意到，状态转移方程中dp[i][j][k]的状态只与前一步的状态有关，因此空间复杂度还可以优化到O(n^2)
上面的状态转移方程为x1!=x2时的，由于当两人走过同一个格子时，该格子价值只算一次，因此当x1=x2时，加上M[x1][y1]即可。
http://accepted.com.cn/51nod1084/
int main()
{
int n,m,i,j,x1,x2;
scanf("%d%d",&m,&n);
for(i=0;i<n;++i)
for(j=0;j<m;++j)
scanf("%d",&M[i][j]);
memset(dp,0,sizeof(dp));
dp[0][0][0]=M[0][0];
for(i=1;i<n+m;++i)
for(x1=0;x1<n&&i-x1>=0;++x1)
for(x2=0;x2<n&&i-x2>=0;++x2)
{
if(x1-1>=0&&x2-1>=0)
dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2-1]+M[x1][i-x1]+(x1==x2?0:M[x2][i-x2]));
if(x1-1>=0&&i-x2-1>=0)
dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1-1][x2]+M[x1][i-x1]+(x1==x2?0:M[x2][i-x2]));
if(x2-1>=0&&i-x1-1>=0)
dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2-1]+M[x1][i-x1]+(x1==x2?0:M[x2][i-x2]));
if(i-x2-1>=0&&i-x1-1>=0)
dp[i][x1][x2]=max(dp[i][x1][x2],dp[i-1][x1][x2]+M[x1][i-x1]+(x1==x2?0:M[x2][i-x2]));
}
printf("%d\n",dp[n+m-1][n-1][n-1]);
return 0;
}
int maxPath(vector<vector<int> > &num) {
const int m = num.size();
const int n = num[0].size();
const int l = m + n - 1;
vector<vector<int> > g(m + 1, vector<int>(m + 1));
vector<vector<int> > h(m + 1, vector<int>(m + 1));
for (int k = 1; k <= l; k++) {
int st = k <= n ? 1 : k - n + 1;
int ed = k <= m ? k : m;
for (int i = st; i <= ed; i++)
for (int j = i; j <= ed; j++) {
h[i][j] = num[i - 1][k - i] +max(max(g[i - 1][j - 1], g[i - 1][j]), max(g[i][j - 1], g[i][j]));
if (i != j)
h[i][j] += num[j - 1][k - j];
}
swap(g, h);
}
return g[m][m];
}
http://www.meetqun.com/thread-2686-1-1.html还是尝试两个人同时走……，有个好处是，两个人一起走的话，只能在同一步经过相同的格子，这是由距离决定的。因为第step步，所在的格子距离起点的曼哈顿距离|x - x' | + |y - y'| = step……所以走一次时，状态是dp[(x,y)]由(x - 1, y) (x, y - 1)决定，现在状态是dp[(x1,y1)(x2,y2)]由4个状态确定即dp[(x1 - 1, y1)(x2 - 1, y2)] dp[(x1 - 1, x2, y2 - 1)] dp[(x1, y1 - 1)(x2 - 1, y2)] dp[(x1, y1 - 1) (x2 , y2 - 1)]确定
//解法二
//2.2、DP方法实现
//copyright@caopengcs 2013
const int N = 202;
const int inf = 1000000000; //无穷大
int dp[N * 2][N][N];
bool isValid(int step, int x1, int x2, int n) //判断状态是否合法
{
int y1 = step - x1, y2 = step - x2;
return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
}
int getValue(int step, int x1, int x2, int n) //处理越界 不存在的位置 给负无穷的值
{
return isValid(step, x1, x2, n) ? dp[step][x1][x2] : (-inf);
}
//状态表示dp[step][i][j] 并且i <= j, 第step步 两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 空间复杂度O(n^3)
int getAnswer(int a[N][N], int n)
{
int P = n * 2 - 2; //最终的步数
int i, j, step;
//不能到达的位置 设置为负无穷大
for (i = 0; i < n; ++i)
{
for (j = i; j < n; ++j)
{
dp[0][i][j] = -inf;
}
}
dp[0][0][0] = a[0][0];
for (step = 1; step <= P; ++step)
{
for (i = 0; i < n; ++i)
{
for (j = i; j < n; ++j)
{
dp[step][i][j] = -inf;
if (!isValid(step, i, j, n)) //非法位置
{
continue;
}
//对于合法的位置进行dp
if (i != j)
{
dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j, n));
dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j - 1, n));
dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j, n));
dp[step][i][j] += a[i][step - i] + a[j][step - j]; //不在同一个格子，加两个数
}
else
{
dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j, n));
dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j, n));
dp[step][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次
}
}
}
}
return dp[P][n - 1][n - 1];
}
//2.3、DP实现优化版
//copyright@caopengcs 8/24/2013
int dp[2][N][N];
bool isValid(int step, int x1, int x2, int n) //判断状态是否合法
{
int y1 = step - x1, y2 = step - x2;
return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
}
int getValue(int step, int x1, int x2, int n) //处理越界 不存在的位置 给负无穷的值
{
return isValid(step, x1, x2, n) ? dp[step % 2][x1][x2] : (-inf);
}
//状态表示dp[step][i][j] 并且i <= j, 第step步 两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 使用滚动数组 空间复杂度O(n^2)
int getAnswer(int a[N][N], int n)
{
int P = n * 2 - 2; //最终的步数
int i, j, step, s;
//不能到达的位置 设置为负无穷大
for (i = 0; i < n; ++i)
{
for (j = i; j < n; ++j)
{
dp[0][i][j] = -inf;
}
}
dp[0][0][0] = a[0][0];
for (step = 1; step <= P; ++step)
{
for (i = 0; i < n; ++i)
{
for (j = i; j < n; ++j)
{
dp[step][i][j] = -inf;
if (!isValid(step, i, j, n)) //非法位置
{
continue;
}
s = step % 2; //状态下表标
//对于合法的位置进行dp
if (i != j)
{
dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j, n));
dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j - 1, n));
dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j, n));
dp[s][i][j] += a[i][step - i] + a[j][step - j]; //不在同一个格子，加两个数
}
else
{
dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j, n));
dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j, n));
dp[s][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次
}
}
}
}
return dp[P % 2][n - 1][n - 1];
}
http://www.jiuzhang.com/problem/26/
进阶：如果可以从左上角往下走k次，每个方格中的数被取走之后第二次经过则不再累加数值。请问走k次最多能取到的数值之和是多少。
进阶：采用网络流算法。将每个格子拆为两个点——入点和出点，入点到出点之间的流量限制为1，费用为格子的数值。所有出点均向它右方和下方的入点连一条流量限制为无穷大，费用为0的边。连接源点到左上角入点，流量设为k，费用设为0。设右下角的出点为汇点。从源点到汇点做一次最小费用最大流算法，即可得到答案。
