Arnob's blog

By Arnob, history, 3 years ago, In English

Can someone help me with this problem

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it +7 Vote: I do not like it

Calculate $$$\textit{dp}(i, j)$$$ the minimum time to reach $$$a_i$$$ such that the bike is at position $$$j$$$ (prepend and append $$$0$$$ to array $$$a$$$ to make the implementation easier). To compute this $$$\textit{dp}$$$ array, consider transitions $$$\textit{dp}(i, j) \Rightarrow \textit{dp}(i + 1, j')$$$, meaning:

  1. Walk to $$$j$$$ and take bike
  2. Pedal to $$$j'$$$ leave bike there
  3. Walk to $$$a_{i + 1}$$$

Code