Intuition for DP | Help Needed

help
1

I am going through one problem, - LeetCode
In this problem, we need to find the largest square of matrix having 1 only.
So my thinking approach like:

  1. Came with brute force like going each grid point, if its 1 then check the largest square we can form starting from this corner.
  2. Directly, I jump over to solve it using line sweep algorithm. Never came up with the solution though but I think it can be made.

When I looked into the solution tab, its solved using dynamic programming. I couldn’t have thought using DP(unless looking at solution). It its time complexity is also very efficient(efficient over linesweep)
So my question is, how one should approach this problem. Like what would have been clicked in your mind when you are looking this problem and dynamic programming approach strike.

2

Errichto explained this problem . Check it out. Maximal Square of Ones (LeetCode Day 27) - YouTube
The logic behind this is to check the minimum of top, top-left and left squares. If any of them are zeroes, min will be zeroes otherwise you will get a 1 and add it to the current square(only if it is a 1) and thus you will have a square of 4 1s.

3

Dp intuition is all about practice, as you solve more and more questions, you will automatically start applying various dp approaches which you accepted/rejected while solving previous questions. And there will always be questions demanding more and thus you will learn more.

The practice is the key.