找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4991|回复: 2
收起左侧

[基础刷题题目讨论] 走两次的方格取数问题

[复制链接]
发表于 12-4-2014 02:45 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

问题 给定n行n列的方阵,每个元素是一个整数,从左上角走到右下角,每次只能向右或者下,走两次,使得得到的总和最大。同一次经过两个元素的话,总和只计算一次。


分析: 如果是只走一次的话,是经典的dp。走两次的话,dp两次是不对的……因为状态之间有影响,第一次和最大的路径可能会影响第二次的路径。这个题还有一个变形,是等价的,就是说从起点到终点只能向右和下,再从终点回起点只能向上或者左,使得总和最大。

           搜索是指数的算法,贪心不靠谱,两次dp也不行。所以还是尝试两个人同时走……,有个好处是,两个人一起走的话,只能在同一步经过相同的格子,这是由距离决定的。因为第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)]确定。


  1. const int N = 202;
  2. const int inf = 1000000000;  //无穷大
  3. int dp[N * 2][N][N];  
  4. bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
  5. int y1 = step - x1, y2 = step - x2;
  6.     return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
  7. }

  8. int getValue(int step, int x1,int x2,int n) {  //处理越界 不存在的位置 给负无穷的值
  9.     return isValid(step, x1, x2, n)?dp[step][x1][x2]:(-inf);
  10. }

  11. //状态表示dp[step][i][j] 并且i <= j, 第step步  两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 空间复杂度O(n^3)
  12. int getAnswer(int a[N][N],int n) {
  13. int P = n * 2 - 2; //最终的步数
  14. int i,j,step;
  15.    
  16.     //不能到达的位置 设置为负无穷大
  17.     for (i = 0; i < n; ++i) {
  18.         for (j = i; j < n; ++j) {
  19.             dp[0][i][j] = -inf;
  20.         }
  21.    
  22.     }
  23.     dp[0][0][0] = a[0][0];

  24.       for (step = 1; step <= P; ++step) {
  25.         for (i = 0; i < n; ++i) {
  26.             for (j = i; j < n; ++j) {
  27.                 dp[step][i][j] = -inf;
  28.                 if (!isValid(step, i, j, n)) { //非法位置
  29.                     continue;
  30.                 }
  31.                 //对于合法的位置进行dp
  32.                 if (i != j) {
  33.                     dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
  34.                     dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j, n));
  35.                     dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j - 1, n));
  36.                     dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j,n));
  37.                     dp[step][i][j] += a[i][step - i] + a[j][step - j];  //不在同一个格子,加两个数
  38.                 }
  39.                 else {
  40.                     dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
  41.                     dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j,  n));
  42.                     dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j,  n));
  43.                     dp[step][i][j] += a[i][step - i]; // 在同一个格子里,只能加一次
  44.                 }
  45.                
  46.             }
  47.         }
  48.     }
  49.     return dp[P][n - 1][n- 1];
  50. }
复制代码

以上代码的复杂度空间复杂度是O(n^3),稍微想一下可以知道我们在推算dp[step]的时候 只有到了dp[step - 1],所以第一维,我们只开到2就可以了。就是step为奇数时,我们都用dp[1][j]表示状态,step为偶数我们都用dp[0][j]表示状态,这样我们只需要O(n^2)的空间,这就是滚动数组的方法。滚动数组写起来并不复杂,只需要对上面的代码稍作修改即可,优化后的代码如下:


  1. int dp[2][N][N];

  2. bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
  3. int y1 = step - x1, y2 = step - x2;
  4.     return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
  5. }

  6. int getValue(int step, int x1,int x2,int n) {  //处理越界 不存在的位置 给负无穷的值
  7.     return isValid(step, x1, x2, n)?dp[step % 2][x1][x2]:(-inf);
  8. }

  9. //状态表示dp[step][i][j] 并且i <= j, 第step步  两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 使用滚动数组 空间复杂度O(n^2)
  10. int getAnswer(int a[N][N],int n) {
  11. int P = n * 2 - 2; //最终的步数
  12. int i,j,step,s;

  13.    
  14.     //不能到达的位置 设置为负无穷大
  15.     for (i = 0; i < n; ++i) {
  16.         for (j = i; j < n; ++j) {
  17.             dp[0][i][j] = -inf;
  18.         }
  19.    
  20.     }
  21.     dp[0][0][0] = a[0][0];

  22.       for (step = 1; step <= P; ++step) {
  23.         for (i = 0; i < n; ++i) {
  24.             for (j = i; j < n; ++j) {
  25.                 dp[step][i][j] = -inf;
  26.                 if (!isValid(step, i, j, n)) { //非法位置
  27.                     continue;
  28.                 }
  29.                 s = step % 2;  //状态下表标
  30.                 //对于合法的位置进行dp
  31.                 if (i != j) {
  32.                     dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
  33.                     dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j, n));
  34.                     dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j - 1, n));
  35.                     dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j,n));
  36.                     dp[s][i][j] += a[i][step - i] + a[j][step - j];  //不在同一个格子,加两个数
  37.                 }
  38.                 else {
  39.                     dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
  40.                     dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j,  n));
  41.                     dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j,  n));
  42.                     dp[s][i][j] += a[i][step - i]; // 在同一个格子里,只能加一次
  43.                 }
  44.                
  45.             }
  46.         }
  47.     }
  48.     return dp[P % 2][n - 1][n- 1];
  49. }
复制代码


本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!

10

主题

4

精华

251

积分

高级会员

Rank: 3Rank: 3

积分
251
发表于 2-16-2015 02:11 AM | 显示全部楼层
曹神题解总让我脑洞大开,想到以前一个题目,就是一个从左上到右下来回走一遍,来回的路径不能公共点,问有多少种走法。正好用这种方法是可以的。

10

主题

4

精华

251

积分

高级会员

Rank: 3Rank: 3

积分
251
发表于 2-16-2015 02:12 AM | 显示全部楼层
ufoahw 发表于 2-16-2015 02:11 AM
曹神题解总让我脑洞大开,想到以前一个题目,就是一个从左上到右下来回走一遍,来回的路径不能公共点,问有 ...

同时走,保证当前点不会和另一条路径之前的点重复~
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表