Patterns

dp[i][j] depends on dp[i-1][j], dp[i][j-1] (or similar neighbors)

When to useUnique paths, min path sum, maximal square, cherry pickup

Maximal Minimum Value Path I

maximum_minimum_value_path_i

Minimum Difficulty of a Job Schedule

min_job_difficulty

Minimum Path Sum

minimal_path_sum

Minimum Total Container Size

minimum_total_container_size

Number of Unique Paths to Go from Top Left to Bottom Right

robot_unique_path

Longest Palindromic Substringmedium

longest_palindromic_substring · no slots

Palindromic Substringsmedium

palindromic_substrings · no slots

Unique Pathsmedium

unique_paths · no slots

Unique Paths II

unique_paths_with_obstacles

Dungeon Game

dungeon_game

DECLARE

dp = m × n table initialized

const dp = Array.from({ length: m }, () => new Array(n).fill(0));
dp[0][0] = grid[0][0];

—

const m = grid.length, n = grid[0].length;
const dp = Array.from({ length: m }, () => new Array(n).fill(0));

const dp = Array.from({ length: m }, () => new Array(n).fill(0));
let best = 0;

const dp = Array.from({ length: d + 1 }, () => new Array(n + 1).fill(Infinity));
dp[0][0] = 0;

const dp = Array.from({ length: m }, () => new Array(n).fill(0));
dp[0][0] = grid[0][0];

const dp = Array.from({ length: days + 1 }, () => new Array(n + 1).fill(Infinity));
dp[0][0] = 0;

const dp = Array.from({ length: m }, () => new Array(n).fill(1));

—

const dp = Array.from({ length: m }, () => new Array(n).fill(0));
if (obstacleGrid[0][0] === 1) return 0;
dp[0][0] = 1;

const dp = Array.from({ length: m }, () => new Array(n).fill(0));
dp[m - 1][n - 1] = Math.max(1, 1 - dungeon[m - 1][n - 1]);

BASE CASES

initialize first row and first column

for (let i = 1; i < m; i++) dp[i][0] = Math.min(dp[i-1][0], grid[i][0]);
for (let j = 1; j < n; j++) dp[0][j] = Math.min(dp[0][j-1], grid[0][j]);

—

dp[0][0] = grid[0][0];
for (let r = 1; r < m; r++) dp[r][0] = dp[r-1][0] + grid[r][0];
for (let c = 1; c < n; c++) dp[0][c] = dp[0][c-1] + grid[0][c];

for (let i = 0; i < m; i++) { dp[i][0] = matrix[i][0] === 1 ? 1 : 0; best = Math.max(best, dp[i][0]); }
for (let j = 0; j < n; j++) { dp[0][j] = matrix[0][j] === 1 ? 1 : 0; best = Math.max(best, dp[0][j]); }

// dp[0][0] = 0; all dp[0][i>0] = Infinity (implicit from fill)

for (let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];

// dp[0][0] = 0; all dp[0][i>0] = Infinity (implicit from fill)

// first row and first column stay at 1 (implicit via fill(1))

—

for (let i = 1; i < m; i++) dp[i][0] = obstacleGrid[i][0] === 1 ? 0 : dp[i-1][0];
for (let j = 1; j < n; j++) dp[0][j] = obstacleGrid[0][j] === 1 ? 0 : dp[0][j-1];

for (let i = m - 2; i >= 0; i--) dp[i][n-1] = Math.max(1, dp[i+1][n-1] - dungeon[i][n-1]);
for (let j = n - 2; j >= 0; j--) dp[m-1][j] = Math.max(1, dp[m-1][j+1] - dungeon[m-1][j]);

BUILD

for i, j (nested) starting at (1, 1)

for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {

—

for (let r = 1; r < m; r++) {
  for (let c = 1; c < n; c++) {

for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {

for (let day = 1; day <= d; day++) {
  for (let i = day; i <= n; i++) {
    let maxJob = 0;
    for (let j = i; j >= day; j--) {

for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {

for (let day = 1; day <= days; day++) {
  for (let i = day; i <= n; i++) {
    let maxSize = 0;
    for (let j = i; j >= day; j--) {

for (let r = 1; r < m; r++) {

—

for (let i = 1; i < m; i++) {
  for (let j = 1; j < n; j++) {

for (let i = m - 2; i >= 0; i--) {
  for (let j = n - 2; j >= 0; j--) {

[RECURRENCE]

dp[i][j] = f(dp[i-1][j], dp[i][j-1], grid[i][j])

    dp[i][j] = Math.min(grid[i][j], Math.max(dp[i-1][j], dp[i][j-1]));

—

    dp[r][c] = grid[r][c] + Math.min(dp[r-1][c], dp[r][c-1]);

    if (matrix[i][j] === 1) {
      dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
    }
    best = Math.max(best, dp[i][j]);

      if (jobs[j - 1] > maxJob) maxJob = jobs[j - 1];
      if (dp[day - 1][j - 1] !== Infinity) {
        const candidate = dp[day - 1][j - 1] + maxJob;
        if (candidate < dp[day][i]) dp[day][i] = candidate;
      }

    dp[i][j] = grid[i][j] + Math.min(dp[i-1][j], dp[i][j-1]);

      if (sizes[j - 1] > maxSize) maxSize = sizes[j - 1];
      if (dp[day - 1][j - 1] !== Infinity) {
        const candidate = dp[day - 1][j - 1] + maxSize;
        if (candidate < dp[day][i]) dp[day][i] = candidate;
      }

    dp[r][c] = dp[r - 1][c] + dp[r][c - 1];

—

    if (obstacleGrid[i][j] === 1) {
      dp[i][j] = 0;
    } else {
      dp[i][j] = dp[i-1][j] + dp[i][j-1];
    }

    dp[i][j] = Math.max(1, Math.min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]);

RETURN

return dp[m-1][n-1]

return dp[m - 1][n - 1];

let best = -Infinity; for (let j = 0; j < n; j++) best = Math.max(best, dp[m-1][j]); return best === -Infinity ? -1 : best;

return dp[m-1][n-1];

return best * best;

return dp[d][n] === Infinity ? -1 : dp[d][n];

return dp[m - 1][n - 1];

return dp[days][n] === Infinity ? -1 : dp[days][n];

return dp[m - 1][n - 1];

—

return dp[m - 1][n - 1];

return dp[0][0];