Whimsical_HITMAN's blog

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

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

at least put the problem link lol

→ Reply
  • »
    »
    4 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    sorry. I thought i pasted the link.

    → Reply
»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Whimsical_HITMAN (previous revision, new revision, compare).

→ Reply
»
107 minutes ago, # |
  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