NC554 题解 | #简单变向#

题意分析

• 给出一个3xn的矩阵，同时给出若干个障碍物的位置，不能移动到障碍物。当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：
  • 跑到第i行第j+1列
  • 跑到第i-1行第j+1列（如果i=1则不可以这么跑）
  • 跑到第i+1行第j+1列（如果i=3则不可以这么跑）
• 现在需要我们计算出从(1,1)走到(3,n)所需要的最少的步数。

思路分析

解法一 动态规划

• 这个题目我们有两种办法进行求解，首先是一种动态规划，我们定义dp[i][j]表示到达第i行第j列需要的最少的步数，然后我们就可以利用一下方程进行转移.

• 初始化条件是$dp[1][1]=1dp[1][1]=1$

• 图示转移过程如下

• 代码如下
  • 需要遍历所有的位置一遍，时间复杂度为矩形的大小，就是$O(3n)O(3n)$,也就是$O(n)O(n)$
  • 需要标记每个位置是否为障碍物和这个位置的状态信息，空间复杂度为$O(3n)O(3n)$,也就是$O(n)O(n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型vector 
     * @param y int整型vector 
     * @return int整型
     */
    typedef long long ll;
    const int mod = 1e9+7;
    ll dp[4][100010];
    bool vis[4][100010];
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        // write code here
        memset(dp,0,sizeof(dp));
        memset(vis,false,sizeof(vis));
        for(int i=0;i<m;i++){
            // vis对应的下标为true表示这个位置上面放了一个障碍物
            vis[x[i]][y[i]]=true;
        }
        dp[1][1]=1;
        for(int j=1;j<=n;j++){
            for(int i=1;i<=3;i++){
                // 起始点和障碍物的点直接跳过
                if(i==1&&j==1||vis[i][j]) continue;
                if(i==1){
                    // 如果是第一行，那么可以从左边和左下角转移过来
                    dp[i][j]=(dp[i][j]+dp[i+1][j-1]+dp[i][j-1])%mod;
                }else if(i==2){
                    // 如果是第二行，那么可以从左边和左上角和左下角转移
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1]+dp[i][j-1]+dp[i+1][j-1])%mod;
                }else{
                    // 如果是第三行，那么可以从左边和左上角转移过来
                    dp[i][j]=(dp[i][j]+dp[i-1][j-1]+dp[i][j-1])%mod;
                }
            }
        }
        return dp[3][n];
    }
};

解法二 记忆化搜索

• 按照上面的思路我们可以用DFS记忆化搜索解决这个题目。我们一样需要先记录这个位置的是否被计算过，计算过的我们可以直接返回使用。

• 递归的出口是这个位置是障碍物或者这个状态被计算过。然后同样按照上面的状态转移方程进行递归即可。

• 代码如下

  • 可能最坏需要计算所有的状态，时间复杂度为$O(3n)O(3n)$,也就是$O(n)O(n)$
  • 需要标记每个位置是否为障碍物和这个位置的状态信息，空间复杂度为$O(3n)O(3n)$,也就是$O(n)O(n)$

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型vector 
     * @param y int整型vector 
     * @return int整型
     */
    typedef long long ll;
    const int mod = 1e9+7;
    ll dp[4][100010];
    bool vis[4][100010];
    ll dfs(int x,int y){
        // 如果超过了边界
        if(x<1||y<1) return 0;
        // 如果这种情况已经访问过，那么直接返回即可
        if(dp[x][y]!=-1) return dp[x][y];
        // 如果是递归的边界
        if(x==1&&y==1) return dp[x][y]=1;
        // 如果是障碍
        if(vis[x][y]) return dp[x][y]=0;
        if(x==1){
            // 如果是第一行
            return dp[x][y]=(dfs(x,y-1)+dfs(x+1,y-1))%mod;
        }else if(x==2){
            // 如果是第二行
            return dp[x][y]=(dfs(x,y-1)+dfs(x+1,y-1)+dfs(x-1,y-1))%mod;
        }else{
            // 如果是第三行
            return dp[x][y]=(dfs(x,y-1)+dfs(x-1,y-1))%mod;
        }
    }
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        // write code here
        memset(dp,-1,sizeof(dp));
        memset(vis,false,sizeof(vis));
        for(int i=0;i<m;i++){
            // vis对应的下标为true表示这个位置上面放了一个障碍物
            vis[x[i]][y[i]]=true;
        }
        
        return dfs(3,n);
    }
};