题目描述

https://leetcode-cn.com/problems/minimum-sideway-jumps/

算法 dp

集合表示 ：f[N][3]; 表示从起点走到 (i,j) 的方案的集合，属性：minSideJumps

集合划分： f[i][j] 按上一步在哪进行划分 f[i - 1][0] || f[i - 1][1] || f[i - 1][2]
从 f[i - 1][k] 到 f[i][j] 规定先直走到 (i, k) 再侧跳到 (i, j)，这样总侧跳数最少.（反证法：如果从 (i-1, k) 可以先侧跳到 (i - 1, j) 再直走到 (i, j) ，则必然可以从 (i - 1, j) 直走到 (i, j) 这样就省了一步, 而从 (i - 1, j) 到 (i, j) 在枚举中会枚举到，故最短路可以被找到，不需要先侧跳再直走）

故 枚举过程中若 （当前点是障碍） 或 （上一步直走时遇到障碍物），都需要 continue;

状态转移方程： f[i][j] = min(f[i - 1][k] + 侧跳数0或1)

时间复杂度

O(n)

C++ 代码

const int N = 5e5 + 10;

int f[N][3];        // 表示从起点走到 (i,j) 的方案的集合，属性：minSideJumps

class Solution {
public:
    int minSideJumps(vector<int>& b) {

        f[0][1] = 0, f[0][0] = f[0][2] = 1; // 边界初始化

        int n = b.size() - 1;
        for (int i = 1; i <= n; i ++)
            for (int j = 0; j < 3; j ++)
            {
                f[i][j] = 1e9;
                if (b[i] == j + 1) continue;   // 如果该点是障碍物，continue
                for (int k = 0; k < 3; k ++)
                {
                    if (b[i] == k + 1) continue;  // 从上一步前进时有障碍，则continue
                    int cost = 0;
                    if (k != j) cost = 1;     // 上一步和该点不在同一行，侧跳数为1
                    f[i][j] = min(f[i][j], f[i - 1][k] + cost);
                }
            }
        return min(f[n][0], min(f[n][1], f[n][2]));
    }
}