力扣 最少侧跳次数

https://leetcode-cn.com/problems/minimum-sideway-jumps/
定义f[n][k]状态 表示距离n位置k的最小跳次数
距离n的状态由距离n-1状态更新，如果k一样就说明没有横跳,否则加一
代码

const int N=5e5+10,INF=1e8;
int f[N][3];
class Solution {
public:
    int minSideJumps(vector<int>& b) {
        f[0][1]=0,f[0][0]=1,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]=INF;//为更新的值默认赋为无穷大
                if(b[i]==j+1) continue;//该点为障碍不能加入判断
                for(int k=0;k<3;k++){
                    if(b[i]==k+1) continue;//该点为障碍不能加入判断
                    int cost=0;
                    if(k!=j) cost=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]));
    }
};

力扣 最少侧跳次数

原文：https://www.cnblogs.com/OfflineBoy/p/14649918.html