Graphs and dynamic programming · Lesson 22 of 23

DP on grids and strings

A `dp[i][j]` table: grid paths, longest common subsequence and the knapsack.

15 minutes2 games

When a state needs two numbers, the table becomes two-dimensional: dp[i][j]. The three classic shapes:

Grid: dp[r][c] = the answer up to this cell (from above and the left).
Two strings: dp[i][j] = the answer for the first i letters of one and first j of the other.
Choices with a limit: dp[i][c] = the answer with the first i items and capacity c (knapsack).

JavaScript

// Grid: number of right/down paths from the top-left to the bottom-right
function gridPaths(rows, cols) {
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(1))
  for (let r = 1; r < rows; r++)
    for (let c = 1; c < cols; c++) dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
  return dp[rows - 1][cols - 1]
}

// Two strings: longest common subsequence
function lcs(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0))
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1])
  return dp[a.length][b.length]
}

console.log(gridPaths(3, 7), lcs("abcde", "ace"), lcs("seacode", "decode"))

	a	c	e
""	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

The LCS table for abcde and ace. Matching letters take the diagonal + 1; otherwise the larger of above and left. The answer sits in the last cell: 3.

The 0/1 knapsack

JavaScript

// best[c] = most value with capacity c using the items seen so far.
// Looping capacity downward keeps each item to a single use.
function knapsack(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0)
  for (let i = 0; i < weights.length; i++)
    for (let c = capacity; c >= weights[i]; c--)
      best[c] = Math.max(best[c], best[c - weights[i]] + values[i])
  return best[capacity]
}

console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))

What's the output?

const dp = [[1, 1, 1], [1, 0, 0], [1, 0, 0]]
for (let r = 1; r < 3; r++)
  for (let c = 1; c < 3; c++) dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
console.log(dp[2][2])

What will this code print?

Exercise

Write minPath(grid): the smallest sum from the top-left to the bottom-right moving only right or down. It must print 7 12.

Expected output: 7 12

JavaScript

function minPath(grid) {
  
}

console.log(minPath([[1, 3, 1], [1, 5, 1], [4, 2, 1]]), minPath([[1, 2, 3], [4, 5, 6]]))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 2 games

DSA

Graphs and dynamic programming · Lesson 22 of 23

DP on grids and strings

A `dp[i][j]` table: grid paths, longest common subsequence and the knapsack.

15 minutes2 games

When a state needs two numbers, the table becomes two-dimensional: dp[i][j]. The three classic shapes:

Grid: dp[r][c] = the answer up to this cell (from above and the left).
Two strings: dp[i][j] = the answer for the first i letters of one and first j of the other.
Choices with a limit: dp[i][c] = the answer with the first i items and capacity c (knapsack).

JavaScript

// Grid: number of right/down paths from the top-left to the bottom-right
function gridPaths(rows, cols) {
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(1))
  for (let r = 1; r < rows; r++)
    for (let c = 1; c < cols; c++) dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
  return dp[rows - 1][cols - 1]
}

// Two strings: longest common subsequence
function lcs(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () => new Array(b.length + 1).fill(0))
  for (let i = 1; i <= a.length; i++)
    for (let j = 1; j <= b.length; j++)
      dp[i][j] = a[i - 1] === b[j - 1] ? dp[i - 1][j - 1] + 1 : Math.max(dp[i - 1][j], dp[i][j - 1])
  return dp[a.length][b.length]
}

console.log(gridPaths(3, 7), lcs("abcde", "ace"), lcs("seacode", "decode"))

	a	c	e
""	0	0	0
a	1	1	1
b	1	1	1
c	1	2	2
d	1	2	2
e	1	2	3

The LCS table for abcde and ace. Matching letters take the diagonal + 1; otherwise the larger of above and left. The answer sits in the last cell: 3.

The 0/1 knapsack

JavaScript

// best[c] = most value with capacity c using the items seen so far.
// Looping capacity downward keeps each item to a single use.
function knapsack(weights, values, capacity) {
  const best = new Array(capacity + 1).fill(0)
  for (let i = 0; i < weights.length; i++)
    for (let c = capacity; c >= weights[i]; c--)
      best[c] = Math.max(best[c], best[c - weights[i]] + values[i])
  return best[capacity]
}

console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7))

What's the output?

const dp = [[1, 1, 1], [1, 0, 0], [1, 0, 0]]
for (let r = 1; r < 3; r++)
  for (let c = 1; c < 3; c++) dp[r][c] = dp[r - 1][c] + dp[r][c - 1]
console.log(dp[2][2])

What will this code print?

Exercise

Write minPath(grid): the smallest sum from the top-left to the bottom-right moving only right or down. It must print 7 12.

Expected output: 7 12

JavaScript

function minPath(grid) {
  
}

console.log(minPath([[1, 3, 1], [1, 5, 1], [4, 2, 1]]), minPath([[1, 2, 3], [4, 5, 6]]))

Practise on real problems

Practice problems that use what you learned here. Solve them in JavaScript, Python or C++.

Learn more from

Played 0 of 2 games