thanks for the great explanation, was able to come with complete solution, only thing left was didn't think separate base case would be required for i = m - 1 && j = n - 1.
Another approach I thought of is : Calculate the total sum from (0,0) till (m−1,n−1), including negative values. During the traversal, track the two smallest (most negative) values. In the final answer, add the absolute values of these two smallest negatives to the total sum. Is this approach correct?
Can I do dp without doing recursion?? Actually somebody told me to do recursion first as dp follows but even after spending 2 weeks I'm not getting recursion totally. Can u pls guide if dp can be done independently.or not?
@@NeelakshiSachdeva DP can be done without recursion, that method is called tabulation where loops are involved. However, I highly suggest you to follow through learning recursion. Try doing striver's SDE sheet's recursion questions and watch his vids on those questions. You can also check out Love Babbar's C++ course. Recursion is very important as it has applications in higher data structures like trees and graphs. Also , an update now that the rating has been updated on leetcode. It turns out leetcode rejected my solution on this question since it gave TLE on the 577 test case.
Superb solution, I spent more than 1 hour on this problem during the contest while using 2-d DP.
Same here
thanks for the great explanation, was able to come with complete solution, only thing left was didn't think separate base case would be required for i = m - 1 && j = n - 1.
Another approach I thought of is : Calculate the total sum from (0,0) till (m−1,n−1), including negative values. During the traversal, track the two smallest (most negative) values. In the final answer, add the absolute values of these two smallest negatives to the total sum.
Is this approach correct?
no because you can't track which path you have selected so might be possible that 2 min elements are not the part of that path
Thanks Great explanation..For interviews if i explain till memoization will it be enough?or i need to use bottom up approach?
If you able to solve memorization, you will able to solve bottom up already (once watch Love Babbar 's DP series)
(If q. Is easy-moderate)
@@25-cse-csmohitkumarmandal59okk
Was able to solve this question during the contest thankfully 😊
Can I do dp without doing recursion?? Actually somebody told me to do recursion first as dp follows but even after spending 2 weeks I'm not getting recursion totally. Can u pls guide if dp can be done independently.or not?
@@NeelakshiSachdeva DP can be done without recursion, that method is called tabulation where loops are involved. However, I highly suggest you to follow through learning recursion. Try doing striver's SDE sheet's recursion questions and watch his vids on those questions. You can also check out Love Babbar's C++ course. Recursion is very important as it has applications in higher data structures like trees and graphs. Also , an update now that the rating has been updated on leetcode. It turns out leetcode rejected my solution on this question since it gave TLE on the 577 test case.
i have got an idea to solve this problem but ,Failed to handle the Base case.
Does AnyOne With same problem ?
yes
me toooo
Yeah just forgot the case where theres is a robber at the destination cell
Thanks ❤
you explain very well but i dont understand
Found this question tough
Same
Atmost 2 cells is the worse
nice..