简单变向

牛牛准备在一个3行n列的跑道上跑步。一开始牛牛位于(1,1)。
当牛牛位于第i行第j列时，他可以的下一步最多可能有三种选择：

1. 跑到第i行第j+1列
2. 跑到第i-1行第j+1列（如果i=1则不可以这么跑）。
3. 跑到第i+1行第j+1列（如果i=3则不可以这么跑）。
   跑道上有一些格子设置了路障(一个格子可能有多个路障)，牛牛不能跑到路障上。现在牛牛想知道，从(1,1)到(3,n)有多少条不同的路径？
   为了防止答案过大，答案对1e9+7取模。

案例说明
输入：4,1,[1],[2]
返回值：2
说明：
在第一行第二列的位置有一个障碍
牛牛有两种跑法：

1. (1,1)->(2,2)->(2,3)->(3,4)
2. (1,1)->(2,2)->(3,3)->(3,4)

方法一 动态规划

定义一个二维数组 表示再第i列第j行时达到该点到方案数,之后考虑条件，根据题意有3个转移条件

1. 可以从第i列第j行跑到第i = 1列第j行所以可以逆推出
2. 可以从第i列第j行跑到跑到第i-1列第j+1行所以可以逆推出
3. 可以从第i列第j行跑到跑到第i+1列第j+1行所以可以逆推出

因为可能会出现路障到情况所以需要特判一下dp转移具体看代码

class Solution {
public:
    long long dp[100010][5];
    long long mod = 1e9 + 7;
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        // write code here
        dp[1][1] = 1;
        for(int i = 0; i < m; i ++) dp[y[i]][x[i]] = -1;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= 3; j ++){
                if(i == 1 && j == 1) continue; //如果在1，1位则跳过因为他最开始就是站在(1,1)
                if(dp[i][j] == -1) continue;
                dp[i][j] = dp[i - 1][j] == -1 ? 0 : dp[i - 1][j]; //跑到第i行第j+1列的方案数
                dp[i][j] += dp[i - 1][j - 1] == -1 ? 0 : dp[i - 1][j - 1]; //跑到第i-1行第j+1列的方案数
                dp[i][j] += dp[i - 1][j + 1] == -1 ? 0 : dp[i - 1][j + 1]; // 跑到第i-1行第j+1列的方案数
                dp[i][j] %= mod;
            }
        }
        return dp[n][3];
    }
};

时间复杂度: 最多会遍历次也就是整张图所以复杂度为
空间复杂度: 最多会存储整张图所以总空间复杂度为

方法二 递归

递归的转移和方法一的思想差不多,从第(n,3)位置递归回(1,1)逆推回来，初始一个dp数组表示到第i，j位的方案数，并且如果第i，j位有路障设置为-1，考虑递归过程中的几个条件

• 如果在中 则返回1
• 如果在中则返回0
• 如果在中 说明遇到路障了返回0
• 如果在中说明该点已统计过方案数直接返回即可

class Solution {
public:
    long long dp[100100][5];
    long long mod = 1e9 + 7;
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        // write code here
        for(int i = 0; i < m; i ++) dp[y[i]][x[i]] = -1; //标记点
        return dfs(n, 3, n);
    }
    long long dfs(int x, int y, int n){
        if(x == 1 && y == 1) return 1; //如果到原始点则返回1
        if(dp[x][y] == -1) return 0;//如果该点有标记则返回-1
        if(dp[x][y]) return dp[x][y];// 如果该点已有答案则返回答案
        if(y <= 0 || x <= 0 || y > 3 || x > n) return 0; //如果越界则返回 0
        //通过题目要求反向遍历到（1 1）不断返回
        dp[x][y] = ((((dfs(x - 1, y, n) % mod) + (dfs(x - 1, y - 1, n) % mod)) % mod)+ (dfs(x - 1, y + 1, n) % mod)) % mod;
        return dp[x][y] % mod;
    }
};

时间复杂度: 递归的层数最多会为n
空间复杂度: 递归会用到深度为n的递归栈和dp数组的空间总空间复杂度最高会达到