Dynamic Programming

I have noticed that there are few patterns that can be found in different problems. So I did a research on that and find the following topics. These patterns will be tagged in each solution.

Patterns:

1. Minimum/Maximum Path to Reach a Target

• Problems where you must reach a target state (end of an array, bottom of a grid, certain sum, etc.) and the goal is to minimize or maximize the cost along the path.
• Idea: At each step, the cost to reach a state depends on the minimum/maximum cost of reaching the previous states.
• Recurrence form: dp[state] = cost[state] + min_or_max(dp[prev_states])

2. Distinct Ways

• Problems where you need to count the number of ways to reach a state (instead of optimizing cost).
• Idea: Sum over all the possible previous states that lead to the current state.
• Recurrence: dp[state] = Σ dp[prev_states]

3. Merging Intervals

• Problems where the optimal solution depends on splitting or merging segments/subproblems. These often require considering every possible partition point.
• Idea: Recurrence is usually two-dimensional: choose a partition, solve subproblems, then merge.
• Recurrence: dp[i][j] = min_or_max( dp[i][k] + dp[k+1][j] + merge_cost )

4. DP on Strings

• Problems involving substrings, subsequences, or character transformations. Usually solved with 2D DP tables (dp[i][j] represents something about substring s[i..j]).
• Idea: Think in terms of expanding substrings or matching characters one by one.

5. Decision Making

• Problems where at each step you must choose between multiple decisions (take or skip, buy or sell, cut or not cut).
• Idea: Use DP to compare the outcomes of different decisions and store the optimal result.
• Recurrence: dp[state] = max( decision1_result, decision2_result, ... )

Maximal Square

Pattern: 1. Minimum/Maximum Path to Reach a Target

A farmer wants to farm their land with the maximum area where good land is present. The "land" is represented as a matrix with 1s and Os, where 1s mean good land and 0s mean bad land. The farmer only want to farm in a square of good land with the maximum area. Please help the farmer to find the maximum area of the land they can farm in good land.

Example:

01101 
11010 
01110
11110
11111
 
> Output: 3 (max area is 3 by 3)

Solution

Any problem that involves maximizing/minimazing and the input is a 2-D array is often solved with Dynamic Programming for a optimal solution.

Here, we define dp[i][j] as the side length of the largest square whose bottom-right corner is at cell (i, j).

Hence, the transition is:

If land[i][j] == 0, then dp[i][j] = 0 (since no square can end here).

If land[i][j] == 1, then dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.

This works because to form a square ending at (i, j), we need a square from the top, left, and diagonal-top-left. The limiting factor is the smallest among them.

Finally, the answer is the maximum value in the dp table, squared (because we need area).

function maxSquare(land) {
  const rows = land.length
  const cols = land[0].length
  const dp = Array.from({ length: rows }, () => Array(cols).fill(0));
 
  land.forEach((row, rowIndex) => {
    row.forEach((item, columnIndex) => {
      if (land[rowIndex][colimnIndex] == 0) return
 
      let [top, left, diagonal] = [0,0,0]
      if (rowIndex > 0) top = dp[rowIndex - 1][columnIndex]
      if (columnIndex > 0) left = dp[rowIndex][columnIndex - 1] 
      if (rowIndex > 0 && columnIndex > 0) diag = dp[rowIndex - 1][columnIndex - 1] 
 
      dp[rowIndex][columnIndex] = Math.min(top, left, diagonal) + 1
    })
 
    const rowWiseMax = dp.map((row) => Math.max(row))
    return Math.max(...rowWiseMax)
  })
}