题解 | #简单变向#

题目：
矩阵大小为3xn，以(1,1)为起点可以向右走，右上对角线走，右下对角线走（不能出界），有些位置设置了路障，走不了，求出从(1,1)到(3,n)的路径数量

方法一：记忆化递归
可以用自顶向下的递归解决
图片说明
初始化路障数组，遇到路障直接返回0，为了避免重复计算，初始化记忆数组每个位置为0，用记忆数组记录已经计算过的位置，如果该位置不为0，说明该位置已经计算过，直接返回结果
递归结束条件为i=1并且j=1时，返回1
递归表达式为:

$j>1:$

$i=1:dfs(1,j)=dfs(1,j-1)+dfs(2,j-1)$
$i=2:dfs(2,j)=dfs(1,j-1)+dfs(2,j-1)+dfs(3,j-1)$
$i=3:dfs(3,j)=dfs(2,j-1)+dfs(3,j-1)$

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型一维数组 
     * @param y int整型一维数组 
     * @return int整型
     */

    int[][]memory;
    boolean[][]trap;
    int mod=1000000007;
    public int solve (int n, int m, int[] x, int[] y) {
        // write code here
        memory=new int[4][n+1];//记忆数组保存
        trap=new boolean[4][n+1];
        for(int i=0;i<m;i++)trap[x[i]][y[i]]=true;//标记路障
        return dfs(3,n);
    }
    private int dfs(int i,int j){
        if(memory[i][j]!=0)return memory[i][j];
        if(i==1&&j==1)return 1;//递归终止条件
        if(trap[i][j])return 0;//遇到路障直接返回0
        //第一行除（1,1）位置都是从左边+左下角递推而来
        if(i==1&&j>1){
            memory[1][j]=(dfs(1,j-1)+dfs(2,j-1))%mod;
            return memory[1][j];}
        //第二行除(2,1)都是从左边+左上角+左下角递推而来
        else if(i==2&&j>1){
            memory[2][j]=((dfs(2,j-1)+dfs(1,j-1))%mod+dfs(3,j-1))%mod;
            return memory[2][j];
        }//第三行除(3,1)都是从左边+左上角递推而来
        else if(i==3&&j>1){
            memory[3][j]=(dfs(3,j-1)+dfs(2,j-1))%mod;
            return memory[3][j];
        }
        else 
            return 0;//遇到第一列的元素返回0
    }
}

复杂度：
时间复杂度:递归深度为n，每次递归复杂度为常数级，因此时间复杂度为 $O(n)$
空间复杂度：递归栈最大深度为n， $dp$ 数组和记忆数组大小都为 $4*(n+1)$ ,因此空间复杂度为 $O(n)$

方法二：动态规划
$dp[i][j]$ 定义为从(1,1)走到 $dp[i][j]$ 的路径数量，将路障处的 $dp[i][j]$ 置为-1
初始条件: $dp[1][1]=1$ ,除 $dp[1][1]$ 外初始化为0
由于后面的状态是由前面已知状态推过来的，因此，我们需要一列一列的扫描
状态转移方程:

$i=1$ :左+左下-> $dp[i][j]=dp[i][j-1]+dp[i+1][j-1]$
$i=2$ :左上+左+左下-> $dp[i][j]=dp[i-1][j-1]+dp[i][j-1]+dp[i+1][j-1]$
$i=3$ :左上+左-> $dp[i][j]=dp[i-1][j-1]+dp[i][j-1]$
例如：3,3,[1,3,2],[2,2,1]
dp表：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型一维数组 
     * @param y int整型一维数组 
     * @return int整型
     */


    int mod=1000000007;
    public int solve (int n, int m, int[] x, int[] y) {
        // write code here
        long[][]dp=new long[4][n+1];//表示从(1,1)走到(i,j)的路径数量
        for(int i=0;i<m;i++)dp[x[i]][y[i]]=-1;//标记路障为-1
        for(int i=2;i<4;i++)dp[i][1]=0;//第二行开始的第一列（包括路障）都初始化为0
        dp[1][1]=1;//（1,1）为1
        //从第二列开始一列一列填充dp表
        for(int j=2;j<n+1;j++){
            for(int i=1;i<4;i++){
                if(dp[i][j]==-1){dp[i][j]=0;continue;}//遇到路障路径数置0
                if(i==1)dp[i][j]=(dp[i][j-1]+dp[i+1][j-1])%mod;//第一行由左+左下递推
                else if(i==2)dp[i][j]=(dp[i-1][j-1]+dp[i][j-1]+dp[i+1][j-1])%mod;//第二行由左上+左+左下递推
                else if(i==3)dp[i][j]=(dp[i-1][j-1]+dp[i][j-1])%mod;//第三行由左上+左递推
            }
        }return (int)(dp[3][n]%mod);
    }
}

复杂度：
时间复杂度：设置路障循环m次，填充 $dp$ 表两层循环次数 $3n$ ,时间复杂度为 $O(m+n)$
空间复杂度： $dp$ 数组大小为 $4*(n+1)$ ，空间复杂度为 $O(n)$