People publish their solutions without sharing any information about how they derived.They do not provide much more explanation .

This particular problem and most of others can be approached using the following sequence:

1. Find recursive relation

2. Recursive (top-down)

3. Recursive + memo (top-down)

4. Iterative + memo (bottom-up)

5. Iterative + N variables (bottom-up)

Question.

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Step 1.Figure out recursive relation.

A robber has 2 options:

1. Rob current house i;
2. Don't rob current house. If an option "1" is selected it means she can't rob previous i-1 house but can safely proceed to the one before previous i-2 and gets all cumulative loot that follows. If an option "2" is selected the robber gets all the possible loot from robbery of i-1 and all the following buildings.

So it boils down to calculating what is more profitable: robbery of current house + loot from houses before the previous loot from the previous house robbery and any loot captured before that

rob(i) = max( rob(i - 2) + nums[i], rob(i - 1) )

Step 2. Recursive (top-down)

Converting the recurrent relation from Step 1 shound’t be very hard.

def rob(nums):
  return robdp(nums, nums.length - 1)
def robdp(nums, i):
  if (i < 0):
    return 0
  return max(rob(nums, i - 2) + nums[i], rob(nums, i - 1))

This algorithm will process the same i multiple times and it needs improvement. Time complexity: [to fill]

Step 3. Recursive + memo (top-down).

def rob(nums,n):
    memo = [-1]*(n+1)
    return robdp(nums, n- 1)
def robdp(int[] nums, int i): 
    if (i < 0):
        return 0

    if (memo[i] >= 0):
        return memo[i]

    result = max(rob(nums, i - 2) + nums[i], rob(nums, i - 1))
    memo[i] = result
    return result

Much better, this should run in O(n) time. Space complexity is O(n) as well, because of the recursion stack, let's try to get rid of it.

Step 4. Iterative + memo (bottom-up)

def rob(nums,n):
    if (n == 0):
        return 0
    memo = [0]*(n+1)
    memo[1] = nums[0]
    for i in range(n): 
        val = nums[i]
        memo[i+1] = max(memo[i], memo[i-1] + val)

    return memo[n]

Step 5. Iterative + 2 variables (bottom-up)

We can notice that in the previous step we use only memo[i] and memo[i-1], so going just 2 steps back. We can hold them in 2 variables instead. This optimization is met in Fibonacci sequence creation and some other problems.

def rob(nums,n): 
    if (n == 0):
        return 0
    prev1 = 0
    prev2 = 0
    for num in nums: 
        tmp = prev1
        prev1 = max(prev2 + num, prev1)
        prev2 = tmp

    return prev1

There are few patterns that can be found in different problems.These patterns may be helpful in solving DP.

Patterns

1. Minimum (Maximum) Path to Reach a Target
2. Distinct Ways
3. Merging Intervals
4. DP on Strings
5. Decision Making

Problem list: Leetcode

1.Min(Max) Path to Reach a Target

Generate problem statement for this pattern Statement

Given a target find minimum (maximum) cost / path / sum to reach the target.

Approach Choose minimum (maximum) path among all possible paths before the current state, then add value for the current state.

routes[i] = min(routes[i-1], routes[i-2], ... , routes[i-k]) + cost[i]

Generate optimal solutions for all values in the target and return the value for the target.

Top-Down

for j in range(n):
    result = min(result, topDown(target - ways[j]) + cost/ path / sum)

return memo[/*state parameters*/] = result;

Bottom-Up

for i in range(1,target+1):
    for j in range(len(ways)):
       if (ways[j] <= i): 
           dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum)       
return dp[target]

Similar Problems

746. Min Cost Climbing Stairs Easy Top-Down

result = min(minCost(n-1, cost, memo), minCost(n-2, cost, memo)) + (n == cost.size() ? 0 : cost[n])
return memo[n] = result

Bottom-Up

for i in range(2,n+1):
   dp[i] = min(dp[i-1], dp[i-2]) + (i == n ? 0 : cost[i])
return dp[n]

64. Minimum Path Sum Medium

Top-Down

result = min(pathSum(i+1, j, grid, memo), pathSum(i, j+1, grid, memo)) + grid[i][j]    
return memo[i][j] = result

Bottom-Up

for i in range(1,n):
   for j in range(1,m):
       grid[i][j] = min(grid[i-1][j], grid[i][j-1]) + grid[i][j]
return grid[n-1][m-1]

322. Coin Change Medium Top-Down

for i in range(len(coins)):
    if (coins[i] <= target):// check validity of a sub-problem
        result = min(ans, CoinChange(target - coins[i], coins) + 1)
return memo[target] = result

Bottom-Up

for j in range(1,amount+1):
   for i in range(len(coins)):
       if (coins[i] <= j):
           dp[j] = min(dp[j], dp[j - coins[i]] + 1)

931. Minimum Falling Path Sum Medium

983. Minimum Cost For Tickets Medium

650. 2 Keys Keyboard Medium

279. Perfect Squares Medium

1049. Last Stone Weight II Medium

120. Triangle Medium

474. Ones and Zeroes Medium

221. Maximal Square Medium

322. Coin Change Medium

1240. Tiling a Rectangle with the Fewest Squares Hard

174. Dungeon Game Hard

871. Minimum Number of Refueling Stops Hard

2.Distinct Ways

Problem List: Leetcode

Generate problem statement for this pattern Statement

Given a target find a number of distinct ways to reach the target.

Approach

Sum all possible ways to reach the current state.

routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]

Generate sum for all values in the target and return the value for the target.

Top-Down

for j in range(len(ways)):
    result += topDown(target - ways[j])

return memo[/*state parameters*/] = result

Bottom-Up

for i in range(1,target+1):
   for j in range(len(ways)):
       if (ways[j] <= i):
           dp[i] += dp[i - ways[j]]

return dp[target]

Similar Problems

70. Climbing Stairs Easy Top-Down

result = climbStairs(n-1, memo) + climbStairs(n-2, memo)

return memo[n] = result

Bottom-Up

for stair in range(2,n+1):
   for step in range(1,3): 
       dp[stair] += dp[stair-step]

62. Unique Paths Medium Top-Down

result = UniquePaths(x-1, y) + UniquePaths(x, y-1)return memo[x][y] = result

Bottom-Up

for i in range(1,m):
   for j in range(1,n):
       dp[i][j] = dp[i][j-1] + dp[i-1][j]

1155. Number of Dice Rolls With Target Sum Medium

for rep in range(1,d+1):
   new_ways=[0]*(target+1)
   for already in range(target+1):
       for pipe in range(1,f+1):
           if (already - pipe >= 0):
               new_ways[already] += ways[already - pipe]
               new_ways[already] %= mod
   ways = new_ways

Note

Some questions point out the number of repetitions, in that case, add one more loop to simulate every repetition.

688. Knight Probability in Chessboard Medium

494. Target Sum Medium

377. Combination Sum IV Medium

935. Knight Dialer Medium

1223. Dice Roll Simulation Medium

416. Partition Equal Subset Sum Medium

808. Soup Servings Medium

790. Domino and Tromino Tiling Medium

801. Minimum Swaps To Make Sequences Increasing

673. Number of Longest Increasing Subsequence Medium

63. Unique Paths II Medium

576. Out of Boundary Paths Medium

1269. Number of Ways to Stay in the Same Place After Some Steps Hard

1220. Count Vowels Permutation Hard

3.Merging Intervals

Problem List: Leetcode

Generate problem statement for this pattern Statement

Given a set of numbers find an optimal solution for a problem considering the current number and the best you can get from the left and right sides.

Approach

Find all optimal solutions for every interval and return the best possible answer.

// from i to j
dp[i][j] = dp[i][k] + result[k] + dp[k+1][j]

Get the best from the left and right sides and add a solution for the current position.

for l in range(1,n):
   for i in range(n-l):
       j = i+l
       for k in range(i,j):
           dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j])
return dp[0][n-1]

Similar Problems

1130. Minimum Cost Tree From Leaf Values Medium

for l in range(1,n):
   for i in range(n-l):
       j = i + l
       dp[i][j] = sys.maxsize
       for k in range(i,j):
           dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + maxs[i][k] * maxs[k+1][j])

96. Unique Binary Search Trees Medium

1039. Minimum Score Triangulation of Polygon Medium

546. Remove Boxes Medium

1000. Minimum Cost to Merge Stones Medium

312. Burst Balloons Hard

375. Guess Number Higher or Lower II Medium

4.DP on Strings

Problem List: Leetcode

General problem statement for this pattern can vary but most of the time you are given two strings where lengths of those strings are not big Statement Given two strings s1 and s2, return some result.

Approach

Most of the problems on this pattern requires a solution that can be accepted in O(n²) complexity.

// i - indexing string s1
// j - indexing string s2
for i in range(1,n+1):
   for j in range(1,m+1):
       if (s1[i-1] == s2[j-1]):
           dp[i][j] = /*code*/;
       else:
           dp[i][j] = /*code*/;

If you are given one string s the approach may little vary

for l in range(1,n):
   for i in range(n-l):
       j = i + l
       if (s[i] == s[j]):
           dp[i][j] = /*code*/;
       else:
           dp[i][j] = /*code*/;

1143. Longest Common Subsequence Medium

for i in range(1,n+1):
   for j in range(1,m+1):
       if (text1[i-1] == text2[j-1]):
           dp[i][j] = dp[i-1][j-1] + 1
       else:
           dp[i][j] = max(dp[i-1][j], dp[i][j-1])

647. Palindromic Substrings Medium

for l in range(1,n):
   for i in range(n-l):
       j = i + l
       if (s[i] == s[j] && dp[i+1][j-1] == j-i-1):
           dp[i][j] = dp[i+1][j-1] + 2
       else:
           dp[i][j] = 0

516. Longest Palindromic Subsequence Medium

1092. Shortest Common Supersequence Medium

72. Edit Distance Hard

115. Distinct Subsequences Hard

712. Minimum ASCII Delete Sum for Two Strings Medium

5. Longest Palindromic Substring Medium

5.Decision Making

Problem List: Leetcode

The general problem statement for this pattern is forgiven situation decide whether to use or not to use the current state. So, the problem requires you to make a decision at a current state. Statement

Given a set of values find an answer with an option to choose or ignore the current value.

Approach

If you decide to choose the current value use the previous result where the value was ignored; vice-versa, if you decide to ignore the current value use previous result where value was used.

// i - indexing a set of values
// j - options to ignore j values
for i in range(1,n):
   for j in range(1,k+1):
       dp[i][j] = max(dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1])
       dp[i][j-1] = max(dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i])

198. House Robber Easy

for i in range(1,n):
   dp[i][1] = max(dp[i-1][0] + nums[i], dp[i-1][1])
   dp[i][0] = dp[i-1][1]

121. Best Time to Buy and Sell Stock Easy

714. Best Time to Buy and Sell Stock with Transaction Fee Medium

309. Best Time to Buy and Sell Stock with Cooldown Medium

123. Best Time to Buy and Sell Stock III Hard

188. Best Time to Buy and Sell Stock IV Hard

I hope these tips will be helpful😊