Guidelines

Before trying to solve a problem with DP approach first ask yourself if the problem respects the rule of optimality. To determine that see if you can solve the problem by first solving a simpler problem and then using that calculation to solve the initial one. There has to be a natural transition from smaller to larger subproblem (solving a problem for a subarray 0..2, and then using that to solve the problem for subarray 0..5). "Left to right" data structures like arrays, strings, leaves of a tree are natural candidates to apply DP approach to.

You can classify almost any DP problem into 5 categories:

1. 0/1 Knapsack Target Sum
2. Unbounded Knapsack Coin Change
3. Shortest/Critical Path Unique Paths
4. Fibonacci Sequence Climbing Stairs
5. Longest Common Substring/Subsequeunce Number of Longest Increasing Subsequence

How to tranform recursive top down solution to tabulation (bottom up) -> Climbing Stairs.

// order of loops

// (item1, item2) and (item2, item1) is the same (shouldn't be counted twice)
for items
    for 0..target

// bounded knapsack (can't choose the item multiple times)
for items
    for target..0 // reverse order of for loop

// (item1, item2) and (item2, item1) aren't the same
for 0..target
    for items

For string is often useful to create a matrix (row and column match one character in the input string) Longest Palindromic Substring

Topdown recursion: base case + final case + exploration

Java

private int helper(int x, int y, int m, int n){
    if(x > m || y > n) return 0;
    if(x == m && y == n) return 1;

    return helper(x+1, y, m, n) + helper(x, y + 1, m, n);
}

JavaScript

function helper(x, y, m, n) {
  if (x > m || y > n) return 0;
  if (x === m && y === n) return 1;

  return helper(x + 1, y, m, n) + helper(x, y + 1, m, n);
}

Python

def helper(x, y, m, n):
    if x > m or y > n:
        return 0
    if x == m and y == n:
        return 1

    return helper(x + 1, y, m, n) + helper(x, y + 1, m, n)

C++

int helper(int x, int y, int m, int n) {
  if (x > m || y > n) return 0;
  if (x == m && y == n) return 1;

  return helper(x + 1, y, m, n) + helper(x, y + 1, m, n);
}

In most problem we only care about the output of the subproblem, we don't care about the specific configuration that led to that subresult. But sometimes subresults configuration are interdependent (you can't choose the configuration for one subproblem, if it's already choosen for another). In that case we're only left with testing all subsets (all configurations) like we did in Partition to K Equal Sum Subsets. Note that we can't choose an element for partition if it's been already choosen by another partition (subproblem). The pattern we can use to solve this problem is showed below:

Java

for (int mask = 0; mask < (1<<n); ++mask) {
    if (dp[mask] == -1) continue;
    for (int i = 0; i < n; ++i) {
        if ((mask & ( 1<<i )) == 0 && anotherCondition) {
            dp[mask|(1<<i)] = (dp[mask] + nums[i]) % target; // calculation in this case addition
        }
    }
}

JavaScript

for (let mask = 0; mask < 1 << n; ++mask) {
  if (dp[mask] === -1) continue;
  for (let i = 0; i < n; ++i) {
    if ((mask & (1 << i)) === 0 && anotherCondition) {
      dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target; // calculation in this case addition
    }
  }
}

Python

for mask in range(1 << n):
    if dp[mask] == -1:
        continue
    for i in range(n):
        if (mask & (1 << i)) == 0 and anotherCondition:
            dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target  # calculation in this case addition

C++

for (int mask = 0; mask < (1 << n); ++mask) {
  if (dp[mask] == -1) continue;
  for (int i = 0; i < n; ++i) {
    if ((mask & (1 << i)) == 0 && anotherCondition) {
      dp[mask | (1 << i)] = (dp[mask] + nums[i]) % target; // calculation in this case addition
    }
  }
}