During last weekend, I just tried to challenge myself with algorithms. And I found the dynamic programming so interesting.
In this article, I will mention about this problem House Robber
For the first steps, I tried to write down the base sub problems by using the specific input. Base on that, I can analyze which are sub — problems.
1/ Simplify the problem
Find a subset of an array that has maximum sum, and has no adjacent index in the subset (e.g i & i+1 cannot be picked)
We can see some keywords like subset and maximum which can help us to identify that we can solve this by using sub-problems (DP)
Variants:
- Subset without adjacent indexes (i & i+1 is invalid)
2/ Choose a specific input & analyze the sub problems
- Start small (len = 1, len = 2, len =3, …)
- Specific input — and try to abstract in each step (e.g if having 2 elements a[0], a[1] -> a[0]<a[1], a[0] > a[1], a[0]=a[1]) -> using Math.max/Math.min to solve this
- Iterate by adding more elements to the array — thinking in a natural way is the key
3/ Abstract the sub-problems and find the formula
- Basing on our analyst in the step 2, we will try to abstract it
- We replace the absolute number by relative number
Using relative number:
maximumSum[3] = Math.max(maximumSum[3–2] + a[3], maximumSum[3–1])not absolute number:
maximumSum[3] = Math.max(maximumSum[1] + a[3], maximumSum[2])
- Tada, after that, we can see the clear picture
My solution is here:
https://github.com/namKolo/algooito/tree/master/src/DynamicProgramming/HouseRobber
