题目的主要信息：

• 要从一个$n\ast mn*m$网格的$(1,1)(1,1)$位置走到$(n\mathrm{.}m)(n.m)$，每次只能往下或者往右，其中网格中有一块区域不能走
• 不能走的区域，左下角坐标是$(x_0,y_0)(x\_0,y\_0)$，右下角坐标是$(x_1,y_1)(x\_1,y\_1)$
• 问有多少条路径，要取模1000000007

方法一：空间记忆递归

具体做法：

我们考虑没有那个不能走的区域的情况，一个$(n,m)(n,m)$问题，可以由两个$(n-1,m)(n-1,m)$ $(n,m-1)(n,m-1)$子问题相加而来，因为最后一个位置要么来自自己左边要么来自自己右边。子问题又可以继续划分为子问题，于是我们想到了递归。但是这个递归太过于复杂，会重复计算很多子问题，因此我们可以用一个数组来存储这些计算得到的子问题，于是我们有$dp[i][j]dp[i][j]$表示从起点到第$(i,j)(i,j)$位置上的路径条数。在递归时优先考虑dp数组有无以前算好的，没有再继续递归，有的话可以直接使用。递归的边界当前是$mm$或者$nn$为0的时候。

再来考虑不能走的区域，每次递归时我们检查当前的坐标是否在这个区域，如果不在正常走，如果在就将dp数组置为0，并且无法往后面递归，直接返回。

class Solution {
public:
    int recursion(int n, int m, int x0, int y0, int x1, int y1, vector<vector<int>>& dp){
        if(n == 0 || m == 0) //递归结束
            return 0;
        if(n == 1 && m == 1){ //初始位置
            dp[1][1] = 1;
            return 1;
        }
        if(x0 <= n && x1 >= n && y0 <= m && y1 >= m){//在不能走的区域
            dp[n][m] = 0;
            return 0;
        }
        if(dp[n - 1][m] == -1) //检查有无结果可以直接使用
            dp[n - 1][m] = recursion(n - 1, m, x0, y0, x1, y1, dp); //更新结果
        if(dp[n][m - 1] == -1) //检查有无结果可以直接使用
            dp[n][m - 1] = recursion(n, m - 1, x0, y0, x1, y1, dp); //更新结果
        dp[n][m] = (dp[n - 1][m] + dp[n][m - 1]) % 1000000007;
        return dp[n][m];
    }
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, -1)); //记录递归过程中的结果
        return recursion(n, m, x0, y0, x1, y1, dp);
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，递归次数相当于填充数组dp，一共$mnmn$次
• 空间复杂度：$O(nm)O(nm)$，递归栈的大小及数组dp的大小

方法二：动态规划

具体做法：

上述的递归是从$(n,m)(n,m)$逆推到$(1,1)(1,1)$，但是相加的时候是顺序相加，因此我们可以用动态规划数组直接相加，转移方程为$dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]=dp[i-1][j]+dp[i][j-1]$，当然也要检查当前位置$(i,j)(i,j)$是否在不能走的区域内，如果在则置为0.

class Solution {
public:
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
        dp[1][1] = 1; //初始位置
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(x0 <= i && x1 >= i && y0 <= j && y1 >= j)//在不能走的区域
                    continue;
                if(i != 1 || j != 1) //非起点
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000007;
            }
        }
        return dp[n][m];
    }
};

复杂度分析：

• 时间复杂度：$O(nm)O(nm)$，一个二层嵌套循环
• 空间复杂度：$O(nm)O(nm)$，数组dp的大小