C++刷LeetCode（1824. 最少侧跳次数）【动态规划】

糖逗

1. 给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。
   
2. 
   
3. 给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。
   
4. 
   
5. 比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。
   
6. 这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。
   
7. 
   
8. 比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
   
9. 这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。
   
10. 
    
11. 注意：点 0 处和点 n 处的任一跑道都不会有障碍。
    
12. 
    
13.  
    
14. 
    
15. 示例 1：
    
16. 
    
17. 
    
18. 输入：obstacles = [0,1,2,3,0]
    
19. 输出：2
    
20. 解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
    
21. 注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。
    
22. 示例 2：
    
23. 
    
24. 
    
25. 输入：obstacles = [0,1,1,3,3,0]
    
26. 输出：0
    
27. 解释：跑道 2 没有任何障碍，所以不需要任何侧跳。
    
28. 示例 3：
    
29. 
    
30. 
    
31. 输入：obstacles = [0,2,1,0,3,0]
    
32. 输出：2
    
33. 解释：最优方案如上图所示。总共有 2 次侧跳。
    
34.  
    
35. 
    
36. 提示：
    
37. 
    
38. obstacles.length == n + 1
    
39. 1 <= n <= 5 * 105
    
40. 0 <= obstacles[i] <= 3
    
41. obstacles[0] == obstacles[n] == 0
    
42. 
    
43. 来源：力扣（LeetCode）
    
44. 链接：https://leetcode-cn.com/problems/minimum-sideway-jumps
    
45. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     int minSideJumps(vector<int>& obstacles) {
   
4.         int len = obstacles.size();
   
5.         vector<vector<int> >dp(len, vector<int>(3, INT_MAX-1));
   
6.         //初始化
   
7.         dp[0][1] = 0;
   
8.         dp[0][0] = 1;
   
9.         dp[0][2] = 1;
   
10.         //动态规划，dp[i][j]当前在i点处，j跑道的最少侧跳数
    
11.         for(int i = 1; i < len; i++){
    
12.             if(obstacles[i] == 1){
    
13.                 dp[i][1] = min(dp[i-1][1], dp[i-1][2] + 1);
    
14.                 dp[i][2] = min(dp[i-1][2], dp[i-1][1] + 1);
    
15.             }else if(obstacles[i] == 2){
    
16.                 dp[i][0] = min(dp[i-1][0], dp[i-1][2] + 1);
    
17.                 dp[i][2] = min(dp[i-1][2], dp[i-1][0] + 1);
    
18.             }else if(obstacles[i] == 3){
    
19.                 dp[i][0] = min(dp[i-1][0], dp[i-1][1] + 1);
    
20.                 dp[i][1] = min(dp[i-1][1], dp[i-1][0] + 1);
    
21.             }else if(obstacles[i] == 0){
    
22.                 dp[i][0] = min(dp[i-1][0], min(dp[i-1][1] + 1, dp[i-1][2] + 1));
    
23.                 dp[i][1] = min(dp[i-1][1], min(dp[i-1][0] + 1, dp[i-1][2] + 1));
    
24.                 dp[i][2] = min(dp[i-1][2], min(dp[i-1][0] + 1, dp[i-1][1] + 1));
    
25.             }
    
26.         }
    
27.         
    
28.         return min(dp[len-1][0], min(dp[len-1][1], dp[len-1][2]));
    
29.     }
    
30. };

复制代码