首页 > 代码库 > leetcode 576. Out of Boundary Paths
leetcode 576. Out of Boundary Paths
https://leetcode.com/problems/out-of-boundary-paths/#/description
题意大概就是在一个m*n的网格中,在坐标为[i,j]的网格上放一个物体,在规定时间N(t<=N)中,有多少种方法把物体移动出去。物体只能上下左右移动,一次移动一格,移动一次为一个单位时间。
求总的个数,并且每个N都是来自四个方向的N-1之和。很明显用dp做的。还是比较经典的一个dp题把。。
1 class Solution { 2 public: 3 int findPaths(int m, int n, int N, int i, int j) { 4 int dp[51][50][50]; 5 for(int Ni=0;Ni<=N;Ni++) 6 for(int mi=0;mi<m;mi++) 7 for(int ni=0;ni<n;ni++){ 8 if(!Ni) {dp[Ni][mi][ni]==0; continue;} 9 dp[Ni][mi][ni]=((long long) (!mi?1:dp[Ni-1][mi-1][ni])+(mi==m-1?1:dp[Ni-1][mi+1][ni])+ 10 (!ni?1:dp[Ni-1][mi][ni-1])+(ni==n-1?1:dp[Ni-1][mi][ni+1]))%1000000007; 11 } 12 return dp[N][i][j]; 13 } 14 };
要注意的是来自边界外面的个数全都为1,结合图像看一下就明白了。
有一个地方比较有意思,就是我看Sloution的答案,他的Sloution中没有初始Ni==0的情况,我想这样不是不能直接用嘛,因为这时候数组元素不是任意值嘛。。后来我实验了一下。。
int dp[51][50][50]={};
原来这样可以直接初始化为0。。
学到了学到了。。比较特别。。
leetcode 576. Out of Boundary Paths
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。