Whimsical_HITMAN's blog

Leetcode 2617. Minimum Number of Visited Cells in a Grid
By Whimsical_HITMAN, history, 23 months ago, In English

Can someone point out the mistake in my approach... Problem Link Code

  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
23 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

at least put the problem link lol

→ Reply
»
23 months ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Your full dp state is $$$[i,j,steps]$$$ but you are only memoizing $$$[i,j]$$$. You probably wanted your dp to be $$$dp[i][j]$$$ the least steps to go from $$$(i,j)$$$ to $$$(m-1,n-1)$$$. You calculate the transitions similarly for a total time of $$$O(mn(m+n))$$$ which is correct but too slow, so you'd need a way to calculate transitions faster.

→ Reply