Skip to content
RSS feed tkhwang on GitHub tkhwang on Twitter

Dynamic programming patterns

This template is based on the article Dynamic Programming Patterns in leetcode discuss and I changed for myself a little bit.

  • Minimum (Maximum) Path to Reach a Target
  • Distinct Ways
  • Merging Intervals
  • DP on Strings
  • Decision Making

🔥 1. Minimum (Maximum) Path to Reach a Target

1.1 Statement

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

1.2 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]

⬇️ Top-Down 

for (int j = 0; j < ways.size(); ++j) {
    result = min(result, topDown(target - ways[j]) + cost/ path / sum);
}
return memo[/*state parameters*/] = result;

⬆️ Bottom-Up 

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] = min(dp[i], dp[i - ways[j]] + cost / path / sum) ;
       }
   }
}

return dp[target]

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

🗒️ 1.3. Typical problems

🔥 2. Distinct Ways

2.1 Statement 

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

2.2 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 (int j = 0; j < ways.size(); ++j) {
    result += topDown(target - ways[j]);
}
return memo[/*state parameters*/] = result;

⬆️ Bottom-Up 

for (int i = 1; i <= target; ++i) {
   for (int j = 0; j < ways.size(); ++j) {
       if (ways[j] <= i) {
           dp[i] += dp[i - ways[j]];
       }
   }
}

return dp[target]

🗒️ 2.3. Typical problems

🔥 3. Merging Intervals

3.1 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.

3.2 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.

🗒️ 3.3. Typical problems

🔥 4. DP on Strings

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

4.1 Statement 

Given two strings s1 and s2, return some result.

4.2 Approach

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

4.2.1 two string [object Object] and [object Object] given

  • dp[i][j] = result with s1[i-1] and s2[j-1].
for (int i = 1; i <= n; ++i) {
   for (int j = 1; j <= m; ++j) {
       if (s1[i-1] == s2[j-1]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}

4.2.2 one string [object Object] given

  • dp[i][j] = result with s1[0:i] and s1[0:j]
for (let i = 1; i < N; i += 1) {
    for (let j = i; j < N; j += 1) {
        if (s[i] === s[j]) {
            dp[i][j] = /*code*/;
        } else {
            dp[i][j] = /*code*/;
        }
    }
}

for (let i = 1; i < N; i += 1) {
    for (let delta = 0; delta < N - l; delta += 1) {
        let j = i + delta;

        if (s[i] === s[j]) {
            dp[i][j] = /*code*/;
        } else {
            dp[i][j] = /*code*/;
        }
    }
}

🔥 5. Decision Making

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.

5.1 (Decision Making) Statement 

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

5.2 (Decision Making) 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 (int i = 1; i < n; ++i) {
   for (int j = 1; j <= k; ++j) {
       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]});
   }
}

🗒️ 5.3. Typical problems

🗒️ Typical problems

List

🏷️ Related tags

📚 References