一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 639|回复: 6
收起左侧

[算法题] DP 给定矩阵起点和终点,求走K步有多少条路

[复制链接] |试试Instant~ |关注本帖
神罗天征 发表于 2016-8-18 21:15:35 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 神罗天征 于 2016-8-18 21:16 编辑

请教各位大神,这到底该是什么思路呢?
我看别人说的用DP,也给出了代码,但是没看懂DP表达的是什么,主要是第三维的表达不太懂,为什么要求余呢?而且还是2麻烦大家了,谢谢
  1.     public static void main(String[] args) {
  2.       
  3.       int result = pathNum(new Point(0,0),new Point(2,2),3,3);
  4.       System.out.println(result);
  5.     }

  6.     public static int pathNum(Point A,Point B, int size, int k) {
  7.             int[][][]dp = new int[size][size][2];
  8.             dp[A.x][A.y][0] = 1;
  9.             int i;
  10.             // O(M*N*K) //
  11.             for(i = 1; i<=k ; i++){
  12.                     for(int m = 0; m < size; m++){
  13.                             for(int n = 0; n < size; n++){
  14.                                     dp[m][n][i%2] = sumNeighbor(dp,i,m,n,size);
  15.                             }        
  16.                     }
  17.             }
  18.             return dp[B.x][B.y][k%2];
  19.                
  20.         }
  21.         

  22.         public static int sumNeighbor(int[][][]dp, int i, int x, int y, int size){
  23.                 int[] dx = {1, 1,1,-1,-1,-1,0, 0 };
  24.                 int[] dy = {1,-1,0, 1,-1, 0,1,-1 };
  25.                 int sum = 0;
  26.                 for(int k = 0; k<8; k++){
  27.                         int newX = x + dx[k];
  28.                         int newY = y + dy[k];
  29.             
  30.                         if(newX>=0 && newX<size && newY>=0 && newY<size){
  31.                                 sum += dp[newX][newY][(i-1)%2];
  32.                         }
  33.                 }
  34.                 return sum;
  35.         }
  36.          static class Point{
  37.             int x;
  38.             int y;
  39.             Point(int x, int y){
  40.                     this.x = x;
  41.                     this.y = y;
  42.             }
  43.     }
复制代码
mnmunknown 发表于 2016-8-18 23:16:40 | 显示全部楼层
取 mod 2 是滚动数组空间优化,int[][][2] 也就是说第三个维度只需要保存两个状态~ (类似 unique paths 或者 backpack 问题中只需要存当前和上一行的结果)
回复 支持 反对

使用道具 举报

ArthurChen 发表于 2016-8-19 01:03:35 | 显示全部楼层
用dp太慢了,如果给了矩阵长x宽y且规定只能向下或者向右的话直接组合数求解了C(上x 下x+y)。时间复杂度O(n) 空间O(1)
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-8-19 09:10:00 | 显示全部楼层
ArthurChen 发表于 2016-8-19 01:03
用dp太慢了,如果给了矩阵长x宽y且规定只能向下或者向右的话直接组合数求解了C(上x 下x+y)。时间复杂度O(n) ...

但是这道题是上下左右都可以走
回复 支持 反对

使用道具 举报

hijkstra 发表于 2016-8-19 10:43:44 | 显示全部楼层
dp[][][0] 表示初始状态,dp[][][1] 表示走1步之后的状态,每个cell dp[i][j][1] 表示有多少种方法走到(i, j), dp[][][0] = dp[][][2%2] 表示有2步之后的状态,依次类推。相当于用2个2D vectors dp[][] 和 dp2[][] 相互切换计算状态,共切换k次,所以O(k*n^2)。
回复 支持 反对

使用道具 举报

chenzhan171 发表于 2016-8-19 11:55:14 | 显示全部楼层
snapchat onsite碰到了这题, 其实思路很简单, 就是楼上的代码那样, 当然二维也可以, 新建一个temp矩阵, 和原矩阵不停的替换就可以了。
回复 支持 反对

使用道具 举报

 楼主| 神罗天征 发表于 2016-8-19 16:19:58 | 显示全部楼层
hijkstra 发表于 2016-8-19 10:43
dp[][][0] 表示初始状态,dp[][][1] 表示走1步之后的状态,每个cell dp[j][1] 表示有多少种方法走到(i, j) ...

多谢,但是还是有点不太清楚,就是为什么需要两种状态呢
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 18:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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