NC641 走网格

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

案例 输入：4,4,2,2,3,3
返回值：2
说明：只有两条可达路径

方法一:记忆搜索

走到(i,j)的方法有两种一种是从上到下一种是从左到右,所以能得出第(i,j)的数量 = (i - 1,j)的数量 + (i, j - 1)的数量，然后开个二维数组dp记录每一位的方案数，考虑递归返回的情况有:\

1. (i,j)出界了 返回0
2. (i,j)在非法范围内 返回0
3. (i,j)走过了 返回$dp[i][j]dp[i][j]$
4. 当前未走过返回$dp[i][j]=dfs(i-1,j)+dfs(i,j-1)dp[i][j]\; =\; dfs(i\; -\; 1,\; j)\; +\; dfs(i,\; j\; -\; 1)$

class Solution {
public:
    long long dp[1010][1010], mod = 1000000007;
    int cnt =0 ;
    long long dfs(int x, int y, int x0, int y0, int x1, int y1, int n, int m){
        if(dp[x][y]) return dp[x][y]; //如果当前位置走过了返回dp[x][y];
        if(x > n || x < 1 || y > m || y < 1) return 0ll; //如果越界则返回0
        if(x >= x0 && x <= x1 && y >= y0 && y <= y1) return 0ll; //如果进入不能走的区域返回0
        if(x == 1 && y == 1) return 1;//如果为（1，1）的时候返回1
        long long res = 0;
        //左边到当前位置的数量和上到下的数量
        res = dfs(x - 1, y, x0, y0, x1, y1, n, m) + dfs(x, y - 1, x0, y0, x1, y1, n, m);
        res %= mod;
        return dp[x][y] = res;
    }
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        return dfs(n, m, x0, y0, x1, y1, n, m);
    }
    
};

时间复杂度: $O(nm)O(nm)$ 递归次数相当与dp数组的大小$O(nm)O(nm)$
空间复杂度: $O(nm)O(nm)$ 递归栈的大小及dp数组的大小

方法二 动态规划

如方法一的方程设dp数组转移式为:

$dp[i][j]=dp[i-1][j]+dp[i][j-1]dp[i][j]\; =\; dp[i\; -\; 1][j]\; +\; dp[i][j\; -\; 1]$
并初始化$dp[1][1]=1dp[1][1]\; =\; 1$

class Solution {
public:
    long long dp[1010][1010], mod = 1000000007;
    
    int GetNumberOfPath(int n, int m, int x0, int y0, int x1, int y1) {
        // write code here
        dp[1][1] = 1;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= m; j ++){
                if(i >= x0 && i <= x1 && j >= y0 && j <= y1) continue; //如果在不能走的区域跳过
                if(i == 1 && j == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //从上走到下走的数量和从左走到右
                dp[i][j] %= mod;
            }
        }
        return dp[n][m];
    }
};

时间复杂度: $O(nm)O(nm)$ 网格大小
空间复杂度: $O(nm)O(nm)$ dp数组的大小