1824. Minimum Sideway Jumps

create一個跟青蛙要走路線一樣的dp, dp的值為要上下跳躍的最小值
第一步
先更新dp, dp會等於前一次的值,如果石頭在這個位置上,,我們就給他最大值
第二步
假設石頭不再,可以通過比較其餘兩個的值, 跳過來加1是否可以比當前值還要小, 可以的話就換掉

class Solution {
public:
    int minSideJumps(vector<int>& obs) {
        vector<vector<int>>dp (obs.size(), vector<int>(3, 0));
        dp[0][0] = 1;
        dp[0][1] = 0;
        dp[0][2] = 1;
        int maxValue = obs.size();
        for(int i = 1; i < obs.size();i++){
            dp[i][0] = obs[i] == 1? maxValue:dp[i-1][0];
            dp[i][1] = obs[i] == 2? maxValue:dp[i-1][1];
            dp[i][2] = obs[i] == 3? maxValue:dp[i-1][2];
            // update each
            if(obs[i] != 1 ){
                dp[i][0] = min({dp[i][0], dp[i][1] + 1, dp[i][2] + 1});
            }
            if(obs[i] != 2 ){
                dp[i][1] = min({dp[i][1], dp[i][0] + 1, dp[i][2] + 1});
            }
            if(obs[i] != 3 ){
                dp[i][2] = min({dp[i][2], dp[i][1] + 1, dp[i][0] + 1});
            }
}
        int res = maxValue;
        for(int i = 0;i < 3;i++){
            res = min(dp[dp.size() - 1][i], res);
        }
        return res;
    }
};