https://leetcode.com/problems/out-of-boundary-paths/description/
http://www.cnblogs.com/grandyang/p/6927921.html
Solution：
思路：
使用一个三维的DP数组，其中dp[k][i][j]表示总共走k步，从(i,j)位置走出边界的总路径数。
递推式:对于dp[k][i][j]，走k步出边界的总路径数等于其周围四个位置的走k-1步出边界的总路径数之和，如果周围某个位置已经出边界了，那么就直接加上1，否则就在dp数组中找出该值，这样整个更新下来，我们就能得出每一个位置走任意步数的出界路径数了，最后只要返回dp[N][i][j]就是所求结果了。
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;
}
}
