https://leetcode.com/problems/out-of-boundary-paths/description/
http://www.cnblogs.com/grandyang/p/6927921.html
Solution：
思路：
使用一個(gè)三維的DP數(shù)組腹纳，其中dp[k][i][j]表示總共走k步，從(i,j)位置走出邊界的總路徑數(shù)驱犹。
遞推式:對(duì)于dp[k][i][j]嘲恍，走k步出邊界的總路徑數(shù)等于其周?chē)膫€(gè)位置的走k-1步出邊界的總路徑數(shù)之和，如果周?chē)硞€(gè)位置已經(jīng)出邊界了雄驹，那么就直接加上1蛔钙，否則就在dp數(shù)組中找出該值，這樣整個(gè)更新下來(lái)荠医，我們就能得出每一個(gè)位置走任意步數(shù)的出界路徑數(shù)了，最后只要返回dp[N][i][j]就是所求結(jié)果了桑涎。
Time Complexity: O(mnN) Space Complexity: O(mn)
Solution Code：
public class Solution {
public int findPaths(int m, int n, int N, int i, int j) {
if (N <= 0) return 0;
final int MOD = 1000000007;
int[][] count = new int[m][n];
count[i][j] = 1;
int result = 0;
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int step = 0; step < N; step++) {
int[][] temp = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
for (int[] d : dirs) {
int nr = r + d[0];
int nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
result = (result + count[r][c]) % MOD;
}
else {
temp[nr][nc] = (temp[nr][nc] + count[r][c]) % MOD;
}
}
}
}
count = temp;
}
return result;
}
}
