1824.最少侧跳次数

链接：1824.最少侧跳次数
难度：Medium
标签：贪心、数组、动态规划
简介：这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。

题解 1 - cpp

• 编辑时间：2023-01-21
• 执行用时：584ms
• 内存消耗：313.1MB
• 编程语言：cpp
• 解法介绍：dp。

#define MAX 0x3f3f3f3f
class Solution {
public:
    int minSideJumps(vector<int>& obstacles) {
        int n = obstacles.size();
        vector<vector<int>> dp(n, vector<int>(4, MAX));
        dp[0][2] = 0;
        dp[0][1] = dp[0][3] = 1;
        for (int i = 1; i < n; i++) {
            if (obstacles[i] != 1) dp[i][1] = dp[i - 1][1];
            if (obstacles[i] != 2) dp[i][2] = dp[i - 1][2];
            if (obstacles[i] != 3) dp[i][3] = dp[i - 1][3];
            if (obstacles[i - 1] == 1) dp[i][1] = min(dp[i][2], dp[i][3]) + 1;
            if (obstacles[i - 1] == 2) dp[i][2] = min(dp[i][1], dp[i][3]) + 1;
            if (obstacles[i - 1] == 3) dp[i][3] = min(dp[i][1], dp[i][2]) + 1;
        }
        return min({dp[n - 1][1], dp[n - 1][2], dp[n - 1][3]});
    }
};

题解 2 - rust

• 编辑时间：2023-01-21
• 执行用时：100ms
• 内存消耗：30.7MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn min_side_jumps(obstacles: Vec<i32>) -> i32 {
        let n = obstacles.len();
        let mut dp = vec![vec![0x3f3f3f3f; 4]; n];
        dp[0][1] = 1;
        dp[0][2] = 0;
        dp[0][3] = 1;
        for i in 1..n {
            if obstacles[i] != 1 {
                dp[i][1] = dp[i - 1][1];
            }
            if obstacles[i] != 2 {
                dp[i][2] = dp[i - 1][2];
            }
            if obstacles[i] != 3 {
                dp[i][3] = dp[i - 1][3];
            }
            if obstacles[i - 1] == 1 {
                dp[i][1] = dp[i][2].min(dp[i][3]) + 1;
            }
            if obstacles[i - 1] == 2 {
                dp[i][2] = dp[i][1].min(dp[i][3]) + 1;
            }
            if obstacles[i - 1] == 3 {
                dp[i][3] = dp[i][1].min(dp[i][2]) + 1;
            }
        }
        dp[n - 1][1].min(dp[n - 1][2]).min(dp[n - 1][3])
    }
}

题解 3 - python

• 编辑时间：2023-01-21
• 执行用时：1964ms
• 内存消耗：88MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
def minSideJumps(self, obstacles: List[int]) -> int:
    n = len(obstacles)
    dp = [[0x3f3f3f3f for _ in range(4)] for _ in range(n)]
    dp[0][2] = 0
    dp[0][1] = dp[0][3] = 1
    for i in range(1, n):
        if obstacles[i] != 1:
            dp[i][1] = dp[i - 1][1]
        if obstacles[i] != 2:
            dp[i][2] = dp[i - 1][2]
        if obstacles[i] != 3:
            dp[i][3] = dp[i - 1][3]
        if obstacles[i - 1] == 1:
            dp[i][1] = min(dp[i][2], dp[i][3]) + 1
        if obstacles[i - 1] == 2:
            dp[i][2] = min(dp[i][1], dp[i][3]) + 1
        if obstacles[i - 1] == 3:
            dp[i][3] = min(dp[i][1], dp[i][2]) + 1
    return min(dp[n - 1][1], dp[n - 1][2], dp[n - 1][3])