描述
一个nxm的网格中，起点在(1,1)，终点在(n,m)，网格中有一块不能走的矩形区域，左下坐标为(x0,y0)，右上坐标为(x1,y1)，求从起点到终点的路径条数。

示例1

输入：
4,4,2,2,3,3

返回值：
2

说明：
只有两条可达路径

思路

这道题是求从起点到一个格子的所有路径。大家看上面的红点所在的格子，想要到红点所在的格子有两条路：一是：从红点左侧的格子过来；二是：从红点下侧的格子过来；然后我想要知道 红点 左侧格子有几条路径，也是用同样的方法。这样看来，我想求某个格子的路径数量应该是如下公式：

  dp[m][n] = dp[m - 1][n] + dp[m][n - 1];  
  dp[m][n]: 某个格子的坐标；  
  dp[m - 1][n]:是格子左侧的格子路径数量；  
  dp[m][n - 1]:是格子下侧的格子路径数量；  

这么就是动态规划的 状态转移方程。
动态规划除了状态转移方程还有一个重要的元素，那就是 初始值。
这道题的初始值很好确定，dp[1][1] = 1。就是起点位置默认是一条路径。

AC代码

public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        // write code hereå
        if (m < 1 || n < 1) {
            return 0;
        }
        // 初始化dp数组
        int[][] dp = new int[n + 1][m + 1];å
        // 设置默认值
        dp[1][1] = 1;
        // 开始遍历所有格子
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                if (i == 1 && j == 1) {
                    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];
    }

• 时间复杂度：O(m*n)， m 和 n 分别是长宽，因为所有的格子都要遍历到。
• 空间复杂度：O(m*n)，要将这些格子存储到 dp[m][n]，二维数组中。

最后

更多的刷题已经知识，大家可以来我的博客看一看