Dynamic Programming II: Grids, Strings and Knapsack

// Grid DP: dp[r][c] = number of ways to reach cell (r, c) from the top-left, moving only right or down.
// The last move came from above or from the left, so add those two cells. Walls (1) have 0 ways.
export function countPaths(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0)); // NOT fill(new Array(...)): shared row!
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 1) continue;                     // a wall: no path ends here
      if (r === 0 && c === 0) dp[r][c] = 1;               // the start: one way, standing still
      else dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);
    }
  }
  return dp[rows - 1][cols - 1];
}

// The same table kept as ONE row. Before row[c] is updated it still holds the value from the row above,
// and row[c - 1] already holds the current row's value: exactly "above + left".
export function countPathsOneRow(grid) {
  const cols = grid[0].length;
  const row = new Array(cols).fill(0);
  row[0] = 1;
  for (const cells of grid) {
    for (let c = 0; c < cols; c++) {
      if (cells[c] === 1) row[c] = 0;
      else if (c > 0) row[c] += row[c - 1];
    }
  }
  return row[cols - 1];
}

// Two-string DP: dp[i][j] = length of the longest common subsequence of a.slice(0, i) and b.slice(0, j).
// Row 0 and column 0 stand for the empty prefix (LCS 0), so the loops start at 1 and read a[i - 1], b[j - 1].
// After filling, walk back from dp[m][n] to rebuild one longest common subsequence.
export function lcsString(a, b) {
  const m = a.length;
  const n = b.length;
  const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (a[i - 1] === b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; // both last letters are used
      else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);       // drop one of them
    }
  }
  const out = [];
  let i = m;
  let j = n;
  while (i > 0 && j > 0) {
    if (a[i - 1] === b[j - 1]) {
      out.push(a[i - 1]); // this cell came from the diagonal: the letter is in the answer
      i--;
      j--;
    } else if (dp[i - 1][j] >= dp[i][j - 1]) i--; // the value came from above
    else j--;                                      // the value came from the left
  }
  return out.reverse().join("");
}

// 0/1 knapsack in one row: each item at most once. dp[c] = best value with capacity c, using the items so far.
// Capacities go DOWN, so dp[c - w] is still the value from BEFORE this item: no item is counted twice.
export function knapsack01(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let c = capacity; c >= weights[i]; c--) {
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

// Unbounded knapsack: each item as many times as you like.
// Capacities go UP, so dp[c - w] may already include this item, which is exactly what allows reuse.
export function knapsackUnbounded(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    for (let c = weights[i]; c <= capacity; c++) {
      dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

// 0/1 knapsack with the full table, so the chosen items can be read back.
// dp[i][c] = best value using the first i items with capacity c. Item i was taken iff dp[i][c] !== dp[i - 1][c].
export function knapsackItems(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    const w = weights[i - 1];
    for (let c = 0; c <= capacity; c++) {
      dp[i][c] = dp[i - 1][c];                                                // skip item i
      if (w <= c) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w] + values[i - 1]); // or take it once
    }
  }
  const chosen = [];
  for (let i = n, c = capacity; i > 0; i--) {
    if (dp[i][c] !== dp[i - 1][c]) {
      chosen.push(i - 1); // 0-based index of the item
      c -= weights[i - 1];
    }
  }
  return { best: dp[n][capacity], items: chosen.reverse() };
}