1824.最少侧跳次数.md

1824.最少侧跳次数

/*
 * @lc app=leetcode.cn id=1824 lang=typescript
 *
 * [1824] 最少侧跳次数
 */

// @lc code=start
function minSideJumps(o: number[]): number {}
// @lc code=end

解法 1: 动态规划

function minSideJumps(o: number[]): number {
  const n = o.length,
    dp = [1, 0, 1]
  for (let i = 0; i < n; i++) {
    if (o[i]) dp[o[i] - 1] = Infinity
    let min = Math.min(...dp)
    for (let j = 0; j < 3; j++) {
      if (o[i] !== j + 1) dp[j] = Math.min(dp[j], min + 1)
    }
  }
  return Math.min(...dp)
}

Case

test.each([
  { input: { obstacles: [0, 1, 2, 3, 0] }, output: 2 },
  { input: { obstacles: [0, 1, 1, 3, 3, 0] }, output: 0 },
  { input: { obstacles: [0, 2, 1, 0, 3, 0] }, output: 2 },
])('input: obstacles = $input.obstacles', ({ input: { obstacles }, output }) => {
  expect(minSideJumps(obstacles)).toEqual(output)
})