Skip to content

Latest commit

 

History

History
5 lines (3 loc) · 559 Bytes

File metadata and controls

5 lines (3 loc) · 559 Bytes

1824.Minimum-Sideway-Jumps

令dp[i][j]表示从初始状态到第i位置的第j个赛道(j=1,2,3)最少需要多少次jump。显然如果j赛道上有障碍物,那么记dp[i][j]为无限大。

如果j赛道上没有障碍物,那么只有两种方法到达j赛道:第一种是从前一个位置的相同赛道dp[i-1][j]直接走过来。第二种就是从当前位置的其他赛道跳过来。我们第一步先更新dp[i][j]=dp[i-1][j],第二步在所有dp[i][j]里面挑选最小的方案,然后+1就可以用于更新其他的dp[i][j].