Patterns

dp[i] depends on a small fixed number of previous values

When to useClimbing stairs, fibonacci, house robber, decode ways

Memoization

memoization_intro

Number of Ways to Partition a String into a Palindromes | Dynamic Programming

palindrome_partitioning_2

Split String Into Unique Primes

amazon_oa_num_ways_to_split_into_primes

Number of Ways to Decode a Message

decode_ways

Divisor Game

divisor_game

DP with Dynamic Subproblems

dp_dynamic_subproblems_intro

What is Dynamic Programming?

dynamic_programming_intro

House Robber

house_robber

Largest Divisible Subset

largest_divisible_subset

Longest Increasing Subsequence

longest_increasing_subsequence

Longest String Made Up Of Only Vowels

longest_string_made_up_of_only_vowels · no slots

fibonacci_number · no slots

House Robber IImedium

house_robber_ii · no slots

Longest Valid Parentheseshard

longest_valid_parentheses · no slots

Maximum Subarraymedium

maximum_subarray · no slots

Word Break IIhard

word_break_ii · no slots

N-th Tribonacci Numbereasy

nth_tribonacci

Min Cost Climbing Stairseasy

min_cost_climbing_stairs

Minimum Cost For Tickets

minimum_cost_for_tickets

Partition Array for Maximum Summedium

partition_array_max_sum

Longest String Chain

longest_string_chain

DECLARE

dp = new Array(n+1).fill(0)

—

const n = s.length;
const isPal = Array.from({ length: n }, () => new Array(n).fill(false));
const dp = new Array(n + 1).fill(0);

const n = s.length;
const dp = new Array(n + 1).fill(0);

const n = s.length;
const dp = new Array(n + 1).fill(0);

const dp = new Array(n + 1).fill(false);

const dp = new Array(nums.length).fill(1);

const dp = new Array(n + 1).fill(0);

const dp = new Array(n).fill(0);
dp[0] = houses[0];
// guard: if (n === 1) return houses[0];

nums.sort((a, b) => a - b);
const n = nums.length;
const dp = new Array(n).fill(1);
let best = 1;

const n = nums.length;
const dp = new Array(n).fill(1);
let best = 1;

—

const dp = new Array(n + 1).fill(Number.MAX_VALUE);

const n = triangle.length;
const dp = [...triangle[n - 1]];

const dp = new Array(n + 1).fill(0);
let i2 = 1, i3 = 1, i5 = 1;

const n = target.length;
const wordSet = new Set(words);
const dp = new Array(n + 1).fill(false);

if (n <= 1) return 1;
const dp = new Array(n + 1).fill(0);

—

if (n === 0) return 0;
if (n <= 2) return 1;
const dp = new Array(n + 1).fill(0);

const n = cost.length;
const dp = new Array(n + 1).fill(0);

const travelDays = new Set(days);
const lastDay = days[days.length - 1];
const dp = new Array(lastDay + 1).fill(0);

const n = arr.length;
const dp = new Array(n + 1).fill(0);

words.sort((a, b) => a.length - b.length);
const dp = new Map();
let best = 1;

BASE CASES

set dp[0], dp[1] (or whichever indices are base)

—

dp[0] = 1;

dp[0] = 1;

dp[0] = 1;
dp[1] = s[0] !== '0' ? 1 : 0;

dp[1] = false; // player with N=1 loses (no valid move)

// dp[i] = 1 for all i (each element is a subsequence of length 1)

dp[0] = 0; dp[1] = 1;

dp[0] = houses[0];
dp[1] = Math.max(houses[0], houses[1]);

// dp[i] = 1 for all i (each element alone is a valid chain)

// dp[i] = 1 for all i (each element alone is length-1 LIS)

—

dp[0] = 0;

// dp initialized from last row — each position costs itself

dp[1] = 1;

dp[0] = true;

dp[0] = 1;
dp[1] = 1;

—

dp[0] = 0;
dp[1] = 1;
dp[2] = 1;

dp[0] = 0;
dp[1] = 0;

dp[0] = 0; // implicit from fill(0)

dp[0] = 0;

// dp.set(w, 1) before inner loop — each word alone is a chain of length 1

BUILD

for i from base+1 to n

—

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

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

for (let i = 2; i <= n; i++) {

for (let i = 2; i <= n; i++) {

for (let i = 1; i < nums.length; i++) {

for (let i = 2; i <= n; i++) {

for (let i = 2; i < n; i++) {

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

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

—

for (let i = 1; i * i <= n; i++) {
  const cur = i * i;
  for (let j = cur; j <= n; j++) {

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

for (let i = 2; i <= n; i++) {

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

for (let i = 2; i <= n; i++) {

—

for (let i = 3; i <= n; i++) {

for (let i = 2; i <= n; i++) {

for (let d = 1; d <= lastDay; d++) {

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

for (const w of words) {

[RECURRENCE]

dp[i] = f(dp[i-1], dp[i-2], ...)

  const result = helper(k - 1) + helper(k - 2);
  memo.set(k, result);
  return result;

  for (let j = 0; j < i; j++) {
    if (isPal[j][i - 1]) dp[i] += dp[j];
  }

  for (let len = 1; len <= 3 && len <= i; len++) {
    const sub = s.slice(i - len, i);
    if (sub[0] !== '0' && isPrime(Number(sub))) dp[i] += dp[i - len];
  }

  if (s[i - 1] !== '0') dp[i] += dp[i - 1];
  const two = Number(s.slice(i - 2, i));
  if (two >= 10 && two <= 26) dp[i] += dp[i - 2];

  for (let x = 1; x < i; x++) {
    if (i % x === 0 && !dp[i - x]) { dp[i] = true; break; }
  }

  for (let j = 0; j < i; j++) {
    if (nums[j] < nums[i]) dp[i] = Math.max(dp[i], dp[j] + 1);
  }

  dp[i] = dp[i - 1] + dp[i - 2];

  dp[i] = Math.max(dp[i - 1], dp[i - 2] + houses[i]);

  for (let j = 0; j < i; j++) {
    if (nums[i] % nums[j] === 0) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  best = Math.max(best, dp[i]);

  for (let j = 0; j < i; j++) {
    if (nums[j] < nums[i]) {
      dp[i] = Math.max(dp[i], dp[j] + 1);
    }
  }
  best = Math.max(best, dp[i]);

—

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

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

  const next2 = dp[i2] * 2, next3 = dp[i3] * 3, next5 = dp[i5] * 5;
  dp[i] = Math.min(next2, next3, next5);
  if (dp[i] === next2) i2++;
  if (dp[i] === next3) i3++;
  if (dp[i] === next5) i5++;

  for (let j = 0; j < i; j++) {
    if (dp[j] && wordSet.has(target.slice(j, i))) { dp[i] = true; break; }
  }

  dp[i] = dp[i - 1] + dp[i - 2];

—

  dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];

  dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

  if (!travelDays.has(d)) {
    dp[d] = dp[d - 1];
  } else {
    dp[d] = Math.min(
      dp[d - 1] + costs[0],
      dp[Math.max(0, d - 7)] + costs[1],
      dp[Math.max(0, d - 30)] + costs[2]
    );
  }

    dp[i] = Math.max(dp[i], dp[i - j] + j * runningMax);

  dp.set(w, 1);
  for (let i = 0; i < w.length; i++) {
    const prev = w.slice(0, i) + w.slice(i + 1);
    if (dp.has(prev)) {
      dp.set(w, Math.max(dp.get(w), dp.get(prev) + 1));
    }
  }
  best = Math.max(best, dp.get(w));

RETURN

return dp[n]

return helper(n);

return dp[n];

return dp[n];

return dp[n];

return dp[n];

return Math.max(...dp);

return dp[n];

return dp[n - 1];

return best;

return best;

—

return dp[n];

return dp[0];

return dp[n];

return dp[n];

return dp[n];

—

return dp[n];

return dp[n];

return dp[lastDay];

return dp[n];

return best;