Dec 20, 2021
Edit me
#. Problem
1. My approach
brute force
very inefficient.
2. Solution
Dynamic Programming
Link is here
Quite clever. Basically, if(map(i,j) == 1) then, dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1
So, you can go from left top to right bottom, O(M*N). It’s easy to understand if you draw the matrix and try it by yourself.
