题解 | #简单变向#

解题思路（参考爬楼梯的例子）：
1. 障碍物记录，用字典，方便查找
2. 障碍物在同一列超过3个，就返回0
3. 动态转移方程
dp[0][i] = 0 if "有障碍" else int((dp[0][i-1] + dp[1][i-1]) % base_num)
dp[1][i] = 0 if "有障碍" else int((dp[0][i-1] + dp[1][i-1] + dp[2][i-1]) % base_num)
dp[2][i] = 0 if "有障碍" else int((dp[1][i-1] + dp[2][i-1]) % base_num)
4. 中间剪枝，提前遇到不可以通过，就返回0
if sum([dp[0][i], dp[1][i], dp[2][i]]) == 0:
return 0

class Solution:
    def solve(self , n , m , x , y ):
        # write code here

        base_num = 1e9+7

        # 初始化
        block_dict = dict()
        y_dict = dict()      # 记录每列的障碍数（超过3个说明无法通过）
        for x_i, y_i in zip(x, y):
            x_i, y_i = x_i -1, y_i - 1
            block_dict["%d_%d" % (x_i, y_i)] = (x_i, y_i)
            y_dict[y_i] = y_dict.get(y_i, set())
            y_dict[y_i].add(y_i)
            if len(y_dict[y_i]) >= 3:
                return 0

        dp = [[0 for i in range(n)] for j in range(3)]
        dp[0][0] = 1
        dp[0][1] = 0
        dp[0][2] = 0
        for i in range(1, n):
            dp[0][i] = 0 if "%d_%d" % (0, i) in block_dict else int((dp[0][i-1] + dp[1][i-1]) % base_num)
            dp[1][i] = 0 if "%d_%d" % (1, i) in block_dict else int((dp[0][i-1] + dp[1][i-1] + dp[2][i-1]) % base_num)
            dp[2][i] = 0 if "%d_%d" % (2, i) in block_dict else int((dp[1][i-1] + dp[2][i-1]) % base_num)

            if sum([dp[0][i], dp[1][i], dp[2][i]]) == 0:
                return 0

        return dp[2][n-1]