题解 | #简单变向#

题意整理

牛牛在一个3行n列的跑道上跑步。
牛牛的下一步只能在原来的那一行，或者由相邻行跳转过来（不能跨行或者越界）。
求牛牛从(1,1)到(3,n)有多少条不同的路径可走。

方法一（记忆化递归）

1.解题思路

递归终止条件：起点第1行第1列的位置肯定是可达的。
递归如何推进：总共有1，2，3三行跑道。当牛牛在第1行跑道上时，只能由上一列第1行或第2行的跑道跳转过来；当牛牛在第2行跑道上时，可以由上一列第1行、第2行或第3行的跑道跳转过来；当牛牛在第3行跑道上时，只能由上一列第2行或第3行的跑道跳转过来。
每一层递归返回什么：返回到达当前位置总共有多少条不同的路径。

由于递归会有很多重复的计算，可以通过记忆数组记录之前计算过的状态。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型一维数组 
     * @param y int整型一维数组 
     * @return int整型
     */
    //声明取余常数
    int mod=1000000007;
    //声明障碍物数组
    int[][] obs;
    //声明记忆数组
    int[][] memo;

    public int solve (int n, int m, int[] x, int[] y) {
        //初始化
        obs=new int[n+1][n+1];
        for(int i=0;i<m;i++){
            obs[x[i]][y[i]]=1;
        }
        memo=new int[n+1][4];

        return dfs(n,3);
    }

    private int dfs(int n,int k){
        //如果在记忆数组，直接返回
        if(memo[n][k]!=0) return memo[n][k];
        //递归终止条件
        if(n==1&&k==1) return 1;
        //遇到障碍物，直接返回0
        if(obs[k][n]==1) return 0;

        //k为1表示在第1行跑道，只能由上一列第1行或第2行的状态转化过来
        if(n>1&&k==1){
            memo[n][1]=(dfs(n-1,1)+dfs(n-1,2))%mod;
            return (dfs(n-1,1)+dfs(n-1,2))%mod;
        }
        //k为2表示在第2行跑道，可以由上一列第1行、第2行和第3行的状态转化过来
        if(n>1&&k==2){
            memo[n][2]=((dfs(n-1,1)+dfs(n-1,2))%mod+dfs(n-1,3))%mod;
            return ((dfs(n-1,1)+dfs(n-1,2))%mod+dfs(n-1,3))%mod;
        }
        //k为3表示在第3行跑道，只能由上一列第2行或第3行的状态转化过来
        if(n>1&&k==3){
            memo[n][3]=(dfs(n-1,2)+dfs(n-1,3))%mod;
            return (dfs(n-1,2)+dfs(n-1,3))%mod;
        }
        return 0;
    }
}

3.复杂度分析

时间复杂度：递归的层数为n，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外深度为n的递归栈，同时需要大小为 $(n+1)^2$ 的障碍物数组和大小为 $(n+1)*4$ 的记忆数组，所以空间复杂度是 $O(n^2)$ 。

方法二（动态规划）

1.解题思路

状态定义： $dp[i][k]$ (k=1,2,3)表示从起点到达(k,i)总共有多少条不同的路径。
状态初始化：起点（1,1）总是可达的，所以 $dp[1][1]=1$ 。
状态转移：当牛牛在第1行跑道上时，只能由上一列第1行或第2行的跑道跳转过来，即 $dp[i][1]=dp[i-1][1]+dp[i-1][2]$ ；当牛牛在第2行跑道上时，可以由上一列第1行、第2行或第3行的跑道跳转过来，即 $dp[i][2]=dp[i-1][1]+dp[i-1][2]+dp[i-1][3]$ ；当牛牛在第3行跑道上时，只能由上一列第2行或第3行的跑道跳转过来，即 $dp[i][3]=dp[i-1][2]+dp[i-1][3]$ 。由于每一次相加，答案都可能越界，所以在所有的状态相加地方对mod取余

动图展示：
图片说明

2.代码实现

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) {
        //初始化障碍物数组
        int[][] obs=new int[n+1][n+1];
        for(int i=0;i<m;i++){
            obs[x[i]][y[i]]=1;
        }

        //初始化dp数组
        int[][] dp=new int[n+1][4];
        //状态初始化
        dp[1][1]=1;
        for(int i=2;i<=n;i++){
            //状态转移
            dp[i][1]=(dp[i-1][1]+dp[i-1][2])%mod;
            dp[i][2]=((dp[i-1][1]+dp[i-1][2])%mod+dp[i-1][3])%mod;
            dp[i][3]=(dp[i-1][2]+dp[i-1][3])%mod;
            //存在障碍物，则置零
            if(obs[1][i]==1) dp[i][1]=0;
            if(obs[2][i]==1) dp[i][2]=0;
            if(obs[3][i]==1) dp[i][3]=0;
        }
        return dp[n][3];
    }
}

3.复杂度分析

时间复杂度：循环体总共执行n-1次，所以时间复杂度是 $O(n)$ 。
空间复杂度：需要额外大小为 $(n+1)^2$ 的障碍物数组和大小为 $(n+1)*4$ 的dp数组，所以空间复杂度是 $O(n^2)$ 。