【LeetCode】5728. 最少侧跳次数

本文主要是介绍【LeetCode】5728. 最少侧跳次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最少侧跳次数显示英文描述
通过的用户数1397
尝试过的用户数2030
用户总通过次数1416
用户总提交次数3621
题目难度Medium
给你一个长度为 n 的 3 跑道道路，它总共包含 n + 1 个点，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道出发，它想要跳到点 n 处。然而道路上可能有一些障碍。

给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中最多有一个障碍。

比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。
这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在同一个点处侧跳到另外一条跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的任一跑道，请你返回最少侧跳次数。

注意：点 0 处和点 n 处的任一跑道都不会有障碍。

示例 1：

输入：obstacles = [0,1,2,3,0]
输出：2
解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。
示例 2：

输入：obstacles = [0,1,1,3,3,0]
输出：0
解释：跑道 2 没有任何障碍，所以不需要任何侧跳。
示例 3：

输入：obstacles = [0,2,1,0,3,0]
输出：2
解释：最优方案如上图所示。总共有 2 次侧跳。

提示：

obstacles.length == n + 1
1 <= n <= 5 * 105
0 <= obstacles[i] <= 3
obstacles[0] == obstacles[n] == 0

我写了这么多也没过

class Solution {
public:int minSideJumps(vector<int>& obstacles) {int len = obstacles.size();vector<vector<int>>v(len,vector<int>(3,999999));v[0][1]=0;if(obstacles[0]!=0){v[0][0]=1;}if(obstacles[0]!=2){v[0][2]=1;}for(int i=1;i<len;i++){if(obstacles[i]==0){v[i][0]=v[i-1][0];v[i][1]=v[i-1][1];v[i][2]=v[i-1][2];}else if(obstacles[i]==1){//v[i][0]=v[i-1][0];v[i][1]=v[i-1][1];v[i][2]=v[i-1][2];}else if(obstacles[i]==2){v[i][0]=v[i-1][0];//v[i][1]=v[i-1][1];v[i][2]=v[i-1][2];}else if(obstacles[i]==3){v[i][0]=v[i-1][0];v[i][1]=v[i-1][1];//v[i][2]=v[i-1][2];}int mix = 999999;if(v[i][0]<mix)mix =v[i][0];if(v[i][1]<mix)mix =v[i][1];if(v[i][2]<mix)mix =v[i][2];if(obstacles[i]==0){if(v[i][0]>(mix+1))v[i][0]=mix+1;if(v[i][1]>(mix+1))v[i][1]=mix+1;if(v[i][2]>(mix+1))v[i][2]=mix+1;}else if(obstacles[i]==1){//if(v[i][0]>mix)v[i][0]=mix+1;if(v[i][1]>(mix+1))v[i][1]=mix+1;if(v[i][2]>(mix+1))v[i][2]=mix+1;}else if(obstacles[i]==2){if(v[i][0]>(mix+1))v[i][0]=mix+1;//if(v[i][1]>mix)v[i][1]=mix+1;if(v[i][2]>(mix+1))v[i][2]=mix+1;}else if(obstacles[i]==3){if(v[i][0]>(mix+1))v[i][0]=mix+1;if(v[i][1]>(mix+1))v[i][1]=mix+1;//if(v[i][2]>mix)v[i][2]=mix+1;}if(i>900){//cout<<mix<<endl;}}int i = len -1;int mix = 999999;if(v[i][0]<mix)mix =v[i][0];if(v[i][1]<mix)mix =v[i][1];if(v[i][2]<mix)mix =v[i][2];return mix;}
};

知道是 dp 为啥别人写的就很精简
其实思路都是那个思路
咋我那个就容易出问题
就没AC

class Solution
{
public:vector<int> run(vector<int> last, int ob) {vector<int> cur(3);for (int i = 0; i < 3; ++i) {cur[i] = (i == ob ? 1000000 : last[i]);}for (int i = 0; i < 3; ++i) {if (i != ob) {for (int j = 0; j < 3; ++j) {if (i != j) {cur[i] = min(cur[i], cur[j] + 1);}}}}return cur;}int minSideJumps(vector<int>& obstacles) {vector<int> dp = {1, 0, 1};for (int i = 1; i < obstacles.size(); ++i) {dp = run(dp, obstacles[i] - 1);}return min(dp[0], min(dp[1], dp[2]));}
};