576. Out of Boundary Paths
https://www.cnblogs.com/grandyang/p/6927921.html
dp表示上一次移动,所有位置的路径数;t表示的是当前移动,所有位置的路径数。然后每次用t去更新dp,即当前次移动去更新上一次移动。
每次只要超过了边界,就记录可能的路径数更新最终的结果。
class Solution { public: int findPaths(int m, int n, int N, int i, int j) { int res = 0; vector<vector<int>> dp(m,vector<int>(n,0)); dp[i][j] = 1; for(int k = 0;k < N;k++){ vector<vector<int>> tmp(m,vector<int>(n,0)); for(int r = 0;r < m;r++){ for(int c = 0; c < n;c++){ for(auto dir:dirs){ int x = r + dir[0]; int y = c + dir[1]; if(x < 0 || x >= m || y < 0 || y >= n) res = (res + dp[r][c])% 1000000007; else tmp[x][y] = (tmp[x][y] + dp[r][c])% 1000000007; } } } dp = tmp; } return res; } private: vector<vector<int>> dirs{{-1,0},{1,0},{0,-1},{0,1}}; };
688. Knight Probability in Chessboard