- 设计思想:
-视频讲解链接B站视频讲解
- 复杂度分析:
- 代码:
c++版本:
class Solution { public: /** * * @param n int整型 * @param m int整型 * @param x0 int整型 * @param y0 int整型 * @param x1 int整型 * @param y1 int整型 * @return int整型 */ int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) { // write code here //dp[i][j]表示走到位置(i,j)时有多少种不同路径数目 vector<vector<int>> dp(n+1, vector<int>(m+1,0)); ///如果起点在不能走的矩形区域就retur 0 if(x0 <= 1 && x1 >= 1 && y0 <= 1 && y1 >= 1) return 0; dp[1][1] = 1;//起点 //dp值更新 for(int i = 1;i <= n;i ++){ for(int j = 1;j <= m;j ++){ if (i == 1 && j == 1) continue; //如果下一步在不能走的矩阵区域就直接continue if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue; dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007; } } return dp[n][m]; } };
Java版本:
import java.util.*; public class Solution { /** * * @param n int整型 * @param m int整型 * @param x0 int整型 * @param y0 int整型 * @param x1 int整型 * @param y1 int整型 * @return int整型 */ public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) { // write code here //dp[i][j]表示走到位置(i,j)时有多少种不同路径数目 int [][]dp = new int[n + 1][m + 1]; ///如果起点在不能走的矩形区域就retur 0 if(x0 <= 1 && x1 >= 1 && y0 <= 1 && y1 >= 1) return 0; dp[1][1] = 1;//起点 //dp值更新 for(int i = 1;i <= n;i ++){ for(int j = 1;j <= m;j ++){ if (i == 1 && j == 1) continue; //如果下一步在不能走的矩阵区域就直接continue if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue; //dp值的更新 dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007; } } return dp[n][m]; } }
Python版本:
# # # @param n int整型 # @param m int整型 # @param x0 int整型 # @param y0 int整型 # @param x1 int整型 # @param y1 int整型 # @return int整型 # class Solution: def GetNumberOfPath(self , n , m , x0 , y0 , x1 , y1 ): # write code here #dp[i][j]表示走到位置(i,j)时有多少种不同路径数目 dp = [[0 for i in range(m+1)] for j in range(n+1)] # 如果起点在不能走的矩形区域就retur 0 if x0 <= 1 and x1 >= 1 and y0 <= 1 and y1 >= 1: return 0 dp[1][1] = 1#起点 #dp值更新 for i in range(1,n+1): for j in range(1,m+1): if i == 1 and j == 1: continue #如果下一步在不能走的矩阵区域就直接continue if i >= x0 and i <= x1 and j >= y0 and j <= y1: continue #dp值的更新 dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007 return dp[n][m]
JavaScript版本:
/** * * @param n int整型 * @param m int整型 * @param x0 int整型 * @param y0 int整型 * @param x1 int整型 * @param y1 int整型 * @return int整型 */ function GetNumberOfPath( n , m , x0 , y0 , x1 , y1 ) { // write code here //dp[i][j]表示走到位置(i,j)时有多少种不同路径数目 let dp = Array.from(new Array(n+1),() => new Array(m+1).fill(0)); ///如果起点在不能走的矩形区域就retur 0 if(x0 <= 1 && x1 >= 1 && y0 <= 1 && y1 >= 1) return 0; dp[1][1] = 1;//起点 //dp值更新 for(let i = 1;i <= n;i ++){ for(let j = 1;j <= m;j ++){ if (i == 1 && j == 1) continue; //如果下一步在不能走的矩阵区域就直接continue if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue; //dp值的更新 dp[i][j]=(dp[i-1][j] + dp[i][j-1])%1000000007; } } return dp[n][m]; } module.exports = { GetNumberOfPath : GetNumberOfPath };