题解 | #简单变向#

思路：

题目的主要信息：

$3*n$ 的跑道，要从 $(1,1)$ 到 $(3,n)$
每次下一步列号必须加1，行号可以是本行或者邻近的一行，比如1行可以到1行或者2行，2行可以到1行或者2行或者3行，3行可以到2行或者3行
数组x，y分别是路障的行列坐标，有路障的位置不能经过
问路径种类有多少，取模1e+7

方法一：动态规划
具体做法：
用辅助数组dp， $dp[i][j]$ 表示起点到第 $i$ 行第 $j$ 列的方案数。那么如果 $i=1$ ，它就可以从第 $j-1$ 列第1行或者第2行走过来，因此方案数就是这二者相加。另外两种情况类似，转移方程如下：
图片说明
需要注意的是路障位置，我们一开始将dp数组中路障位置设置为-1，再后续如果遇到-1则路障位置的方案数设置为0，省去了额外表达路障的空间。

class Solution {
public:
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        int mod = 1e9 + 7;
        vector<vector<int> > dp(4, vector<int>(n + 1)); //dp[i][j]表示起点到i行j列方案数
        for(int i = 0; i < m; i++)
            dp[x[i]][y[i]] = -1;//路障点设置为-1
        dp[1][1] = 1; //一步到
        dp[2][1] = 0; //初始化为0
        dp[3][1] = 0;
        for(int i = 2; i <= n; i++){
            //每个格子由自己跑到前一列加上隔壁跑道前一列组成
            dp[1][i] = (dp[1][i] == -1) ? 0 : (dp[1][i - 1] + dp[2][i - 1]) % mod;
            dp[2][i] = (dp[2][i] == -1) ? 0 : ((dp[1][i - 1] + dp[2][i - 1]) % mod + dp[3][i - 1]) % mod;
            dp[3][i] = (dp[3][i] == -1) ? 0 : (dp[2][i - 1] + dp[3][i - 1]) % mod;
        }
        return dp[3][n];
    }
};

复杂度分析：

时间复杂度： $O(n+m)$ ，两次单独的遍历
空间复杂度： $O(n)$ ，虽是二维数组，但是最后是 $4$ 个 $n$ 长度的一维数组

方法二：递归+空间记忆
具体做法：
上述动态规划我们也可以用递归来做。
依照上述公式，对于 $(3,n)$ 的问题可以分成 $(3,n-1)+(2,n-1)$ 的子问题来相加得到，只要不断递归向前，最后加到 $(1,1)$ 就可以解决问题。为了防止重复计算递归树底层的元素，我们使用一个数组dp记录第一次递归得到的值，后续再遇到直接取数组即可。
如下图，其中红色的框就是子问题：
图片说明

class Solution {
public:
    int mod = 1e9 + 7;
    int recursion(int n, int k, vector<vector<int>>& dp){
        if(n == 1){
            dp[1][1] = 1; //一步到
            dp[2][1] = 0; //初始化为0
            dp[3][1] = 0;
            return dp[k][n];
        }
        if(dp[k][n] != -1){ //不是路障位置
            if(dp[k][n] == INT_MIN){ //没有遍历到
                if(k == 1) //三种情况的递归
                    dp[k][n] = (recursion(n - 1, 1, dp) + recursion(n - 1, 2, dp)) % mod;
                else if(k == 2)
                    dp[k][n] = ((recursion(n - 1, 1, dp) + recursion(n - 1, 2, dp)) % mod + recursion(n - 1, 3, dp)) % mod;
                else
                    dp[k][n] = (recursion(n - 1, 2, dp) + recursion(n - 1, 3, dp)) % mod;
            }
        }
        else
            dp[k][n] = 0; //路障
        return dp[k][n];
    }
    int solve(int n, int m, vector<int>& x, vector<int>& y) {
        vector<vector<int> > dp(4, vector<int>(n + 1, INT_MIN)); //dp[i][j]表示起点到i行j列方案数，记忆遍历到的，防止重复计算
        for(int i = 0; i < m; i++)
            dp[x[i]][y[i]] = -1;//路障点设置为-1
        return recursion(n, 3, dp);
    }
};

复杂度分析：

时间复杂度： $O(n+m)$ ，一次遍历，一次递归，递归相当于填充数组dp，所以还是 $O(n)$
空间复杂度： $O(n)$ ，递归栈最大深度及辅助数组dp长度