题解 | #走网格#

题意整理

给定一个 $n*m$ 的网格，求从起点(1,1)到终点(n,m)总共有多少不同的路劲。
规定每次只能向右走和向上走，并且不能走指定的矩形区域。

方法一（记忆化递归）

1.解题思路

递归终止条件：横坐标在1，纵坐标也在1时，递归终止，此时只有1条路径。
递归如何推进：每个位置的路径数可以由左边位置的情况得到，也可以由下边位置的情况得到，需要将这两种情况累加。
每层递归返回什么：返回当前位置的路径数。

由于朴素递归会有很多重复的计算，可以通过记忆数组来保存，从而避免不必要的重复计算。

2.代码实现

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整型
     */
    //矩形边界
    int x0,y0,x1,y1;
    //取余常数
    int mod=1000000007;
    //记忆化数组
    int[][] memo;
    public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        //初始化
        this.x0=x0;
        this.y0=y0;
        this.x1=x1;
        this.y1=y1;
        memo=new int[n+1][m+1];
        return path(n,m,n,m);
    }

    private int path(int n,int m,int i,int j){
        //如果越界或者处于指定矩形区域，直接返回0
        if(i<=0||j<=0||(i>=x0&&i<=x1&&j>=y0&&j<=y1)){
            return 0;
        }
        //递归终止条件
        if(i==1&&j==1) return 1;
        //如果记忆化数组中有，直接返回记忆化数组中存的值
        if(memo[i][j]!=0) return memo[i][j];
        //每次可以由左边过来，或者由下边过来
        int cnt=(path(n,m,i-1,j)+path(n,m,i,j-1))%mod;
        memo[i][j]=cnt;
        return cnt;
    }
}

3.复杂度分析

时间复杂度：行递归的深度为n，列递归的深度为m，所以时间复杂度为 $O(n*m)$ 。
空间复杂度：需要额外大小为 $(n+1)*(m+1)$ 的记忆数组，所以空间复杂度为 $O(n*m)$ 。

方法二（动态规划）

1.解题思路

状态定义： $dp[i][j]$ 表示从起点走到 $(i,j)$ 处的路径条数。
状态初始化：当终点在 $(1,1)$ 处时，只有1条路径，所以 $dp[1][1]=1$ 。
状态转移：当前位置可以由左边位置过来，也可以由下边位置过来。所以 $dp[i][j]=dp[i-1][j]+dp[i][j-1]$ 。

动图展示：
图片说明

2.代码实现

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整型
     */
    //取余常数
    int mod=1000000007;
    public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {
        //定义dp数组，dp[i][j]表示从起点走到(i,j)处的路径条数
        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>=x0&&i<=x1&&j>=y0&&j<=y1){
                    continue;
                }
                //当前位置可以由左边位置过来
                if(i>1){
                    dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
                }
                //当前位置可以由下边位置过来
                if(j>1){
                    dp[i][j]=(dp[i][j]+dp[i][j-1])%mod;
                }
            }
        }
        return dp[n][m];
    }

}

3.复杂度分析

时间复杂度：循环最多遍历 $n*m$ 次，所以时间复杂度为 $O(n*m)$ 。
空间复杂度：需要额外大小为 $(n+1)*(m+1)$ 的dp数组，所以空间复杂度为 $O(n*m)$ 。