動態規劃（DP）

# python
# IDEA: dp[i] = best sum of a subarray that ENDS at i: extend the previous run or restart at i
# time = O(n), space = O(n)
# LC 53 - Maximum Subarray
def maxSubArray(nums):
    n = len(nums)
    if n == 0:
        return 0

    # State: dp[i] = max sum of a subarray ending exactly at index i
    dp = [0] * n
    dp[0] = nums[0]

    for i in range(1, n):
        # Transition: extend the run ending at i-1, or start a new run at i
        dp[i] = max(nums[i], dp[i - 1] + nums[i])

    # The answer can end anywhere, so it is the best dp[i], not dp[n-1]
    return max(dp)

// java
// LC 53 - Maximum Subarray
// IDEA: dp[i] = best sum of a subarray that ENDS at i: extend the previous run or restart at i
// time = O(n), space = O(n)
public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0] = nums[0];
    int best = dp[0];

    for (int i = 1; i < n; i++) {
        // extend the run ending at i-1, or start a new run at i
        dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
        best = Math.max(best, dp[i]);   // the answer can end at any index
    }
    return best;
}

nums = [-2, 1, -3, 4, -1, 2]
i=0  dp=-2                       best=-2
i=1  max(1, -2+1=-1)  -> 1       best=1
i=2  max(-3, 1-3=-2)  -> -2      best=1
i=3  max(4, -2+4=2)   -> 4       restart at 4
i=4  max(-1, 4-1=3)   -> 3
i=5  max(2, 3+2=5)    -> 5       best=5   ([4, -1, 2])

# python
# LC 70 - Climbing Stairs
# IDEA: dp[i] = ways to reach step i; i is a COUNT of steps, so the table has n + 1 slots
# time = O(n), space = O(n)
def climbStairs(n):
    dp = [0] * (n + 1)      # dp[0] .. dp[n]: step n is the goal, so it needs a slot
    dp[0] = 1               # one way to be at the bottom: take no step
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # last move was 1 step or 2 steps
    return dp[n]

// java
// LC 70 - Climbing Stairs
// IDEA: dp[i] = ways to reach step i; i is a COUNT of steps, so the table has n + 1 slots
// time = O(n), space = O(n)
public int climbStairs(int n) {
    int[] dp = new int[n + 1];
    dp[0] = 1;              // one way to be at the bottom: take no step
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

# python
# LC 198 - House Robber, sized both ways
# IDEA: index view (dp[i] = best using house i) vs length view (dp[i] = best over the first i houses)
# time = O(n), space = O(n)
# Approach 1: Array size = n (index-based)
def rob_v1(nums):
    n = len(nums)
    if n == 0: return 0
    if n == 1: return nums[0]

    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, n):  # Loop to n
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[n-1]  # Answer at last index

# Approach 2: Array size = n+1 (count-based)
def rob_v2(nums):
    n = len(nums)
    dp = [0] * (n + 1)  # Extra space for "0 houses"
    dp[0] = 0  # Robbing 0 houses = 0
    dp[1] = nums[0] if n > 0 else 0

    for i in range(2, n + 1):  # Loop to n+1
        dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])  # Note: nums[i-1]

    return dp[n]  # Answer at position n

dp[i]  = a claim about the FIRST i CHARACTERS  ->  i is a LENGTH (0 .. n)
s[j]   = the character sitting AT position j   ->  j is an INDEX  (0 .. n-1)

a prefix of length i ends at index i-1
        -> s[i-1] is the newest character inside dp[i]  ->  the CURRENT one

s        =        0     1     0          (n = 3)
index    =        0     1     2          <- s is indexed 0..n-1
                  ^     ^     ^
dp slot  =  0     1     2     3          <- dp has n+1 slots
            |     |     |     |
           ""    "0"   "01"  "010"       <- the prefix dp[i] talks about

# python
# LC 926 - Flip String to Monotone Increasing
# IDEA: dp[i] = min flips over the PREFIX OF LENGTH i, so the char decided at step i is s[i-1]
# time = O(n), space = O(n)
def minFlipsMonoIncr(s):
    n = len(s)
    dp = [0] * (n + 1)          # n+1 slots: dp[0] = empty prefix = 0 flips
    one_so_far = 0              # '1's seen so far in s[:i-1]

    for i in range(1, n + 1):   # i = prefix LENGTH, not a position
        val = s[i - 1]          # the character being decided right now

        if val == '0':
            # flip every earlier '1' -> one_so_far
            # flip this '0' to '1'   -> 1 more than dp[i-1]
            dp[i] = min(one_so_far, dp[i - 1] + 1)
        else:
            dp[i] = dp[i - 1]   # a '1' at the end is always safe, costs nothing
            one_so_far += 1

    return dp[n]                # dp[n], NOT dp[n-1]

i=1  val=s[0]='0'  dp[1]=min(one_so_far=0, dp[0]+1=1) = 0
i=2  val=s[1]='1'  dp[2]=dp[1]=0                 one_so_far -> 1
i=3  val=s[2]='0'  dp[3]=min(one_so_far=1, dp[2]+1=1) = 1
answer = dp[3] = 1     ("010" -> "011" or "000")

# python
# LC 322 - Coin Change
# IDEA: dp[a] = fewest coins for amount a; dp[0] = 0 is the "empty" amount, so amount + 1 slots
# time = O(amount * len(coins)), space = O(amount)
def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)  # Need amount+1
    dp[0] = 0  # Base case: 0 coins needed for amount 0

    for i in range(1, amount + 1):  # Loop to amount+1
        for coin in coins:
            if i >= coin:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

        j                 i
s:  [ ---- dp[j] ---- ][ s[j:i] ]
      already solved     one word?

# python
# IDEA: PREFIX PARTITION DP — dp[i] = can s[:i] be cut into dictionary words
# LC 139 - Word Break
# time = O(n^2) cuts * O(L) slice+hash, space = O(n + dictionary)
class Solution(object):
    def wordBreak(self, s, wordDict):
        n = len(s)
        words = set(wordDict)          # set, not list — see the trap below

        dp = [False] * (n + 1)         # n+1 slots, indexed by prefix LENGTH
        dp[0] = True                   # the empty prefix is always segmentable

        for i in range(1, n + 1):      # i = end boundary of the prefix
            for j in range(i):         # j = start of the candidate last word
                if dp[j] and s[j:i] in words:
                    dp[i] = True
                    break              # one valid cut is enough — it is an OR
        return dp[n]

// java
// IDEA: PREFIX PARTITION DP — dp[i] = can s[:i] be cut into dictionary words
// LC 139 - Word Break
// time = O(n^2) cuts * O(L) substring+hash, space = O(n + dictionary)
public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    Set<String> words = new HashSet<>(wordDict);

    boolean[] dp = new boolean[n + 1];   // n+1 slots, indexed by prefix LENGTH
    dp[0] = true;                        // the empty prefix is always segmentable

    for (int i = 1; i <= n; i++) {       // i = end boundary of the prefix
        for (int j = 0; j < i; j++) {    // j = start of the candidate last word
            if (dp[j] && words.contains(s.substring(j, i))) {
                dp[i] = true;
                break;                   // one valid cut is enough — it is an OR
            }
        }
    }
    return dp[n];
}

# python
# IDEA: same DP, inner loop capped by the longest word — O(n * L^2), effectively linear in n
# time = O(n * L^2), space = O(n)
L = max(map(len, words))
for i in range(1, n + 1):
    for j in range(max(0, i - L), i):
        if dp[j] and s[j:i] in words:
            dp[i] = True
            break

# python
# IDEA: BFS over boundaries — from boundary i, every dictionary word s[i:j] reaches boundary j
# time = O(n * L) cuts * O(L) slice+hash = O(n * L^2), L = longest word; space = O(n)
from collections import deque

def wordBreak(s, wordDict):
    words = set(wordDict)
    longest = max(len(w) for w in words)
    n = len(s)
    seen = [False] * (n + 1)           # boundary already queued
    seen[0] = True
    queue = deque([0])
    while queue:
        i = queue.popleft()
        if i == n:                     # the whole string is cut into words
            return True
        for j in range(i + 1, min(n, i + longest) + 1):   # no word is longer: never slice past it
            if not seen[j] and s[i:j] in words:
                seen[j] = True
                queue.append(j)
    return False

s = "leetcode", dict = {"leet", "code"}

i=0                     dp[0] = True   (base: empty prefix)
i=1..3   no j works     dp[1..3] = False
i=4      j=0: dp[0] AND "leet" in dict  -> dp[4] = True
i=5..7   no j works     dp[5..7] = False
i=8      j=4: dp[4] AND "code" in dict  -> dp[8] = True
                                           ^ answer = dp[n] = dp[8]

# python
# LC 64 - Minimum Path Sum
# IDEA: a cell is reached from above or from the left, so take the cheaper and add the cell
# time = O(m * n), space = O(m * n)
def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0] * n for _ in range(m)]
    dp[0][0] = grid[0][0]

    for i in range(1, m):                 # first column: only from above
        dp[i][0] = dp[i - 1][0] + grid[i][0]
    for j in range(1, n):                 # first row: only from the left
        dp[0][j] = dp[0][j - 1] + grid[0][j]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

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

// java
// LC 64 - Minimum Path Sum
// IDEA: a cell is reached from above or from the left, so take the cheaper and add the cell
// time = O(m * n), space = O(m * n)
public int minPathSum(int[][] grid) {
    int m = grid.length;
    int n = grid[0].length;
    int[][] dp = new int[m][n];

    dp[0][0] = grid[0][0];                       // base: starting cell
    for (int i = 1; i < m; i++) {                // first column — only from above
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }
    for (int j = 1; j < n; j++) {                // first row — only from the left
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    for (int i = 1; i < m; i++) {                // the rest: min of above vs left
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m - 1][n - 1];
}

grid          dp
1 3 1         1  4  5
1 5 1    ->   2  7  6
4 2 1         6  8  7     answer dp[2][2] = 7   (1 → 3 → 1 → 1 → 1)

# python
# LC 516 - Longest Palindromic Subsequence
# IDEA: i descends so row i+1 is already done; j ascends so column j-1 is already done
# time = O(n^2), space = O(n^2)
def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n - 1, -1, -1):         # bottom row first
        dp[i][i] = 1                       # base: one character
        for j in range(i + 1, n):          # left to right, above the diagonal
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

// java
// LC 516 - Longest Palindromic Subsequence
// IDEA: i descends so row i+1 is already done; j ascends so column j-1 is already done
// time = O(n^2), space = O(n^2)
public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

    for (int i = n - 1; i >= 0; i--) {         // bottom row first
        dp[i][i] = 1;                          // base: one character
        for (int j = i + 1; j < n; j++) {      // left to right, above the diagonal
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

What do i and j MEAN in dp[i][j]?

├── ONE sequence; i and j are the two ENDS of a sub-range s[i..j]
│      → Shape A — n × n, only the upper triangle is real,
│        base on the diagonal, answer at the TOP-RIGHT dp[0][n-1]
│        LC 516, 5, 647, 1312, 312, 877
│
├── TWO sequences; i and j are PREFIX LENGTHS (first i of s1, first j of s2)
│      → Shape B — (m+1) × (n+1), row 0 / column 0 are the empty prefixes,
│        answer at the BOTTOM-RIGHT dp[m][n]
│        LC 72, 1143, 115, 97, 10
│
└── a real grid handed to you; i and j are COORDINATES
       → Template 2 above — m × n, answer at dp[m-1][n-1]
         LC 62, 64, 221

# python
# LC 647 - Palindromic Substrings
# IDEA: dp[i][j] = s[i..j] is a palindrome. i and j are REAL indexes, so n x n, not n+1.
# time = O(n^2), space = O(n^2)
def countSubstrings(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]   # n slots: every index is a character of s
    count = 0

    for length in range(1, n + 1):         # short ranges first: dp[i+1][j-1] is shorter
        for i in range(n - length + 1):
            j = i + length - 1             # j is a position too, so it stays <= n-1
            if s[i] == s[j] and (length <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                count += 1

    return count

            j = 0      1        2      ...    n-1
  i = 0   [ base ] [   ?  ] [   ?  ]  ...  [ 🎯 dp[0][n-1] ]   ← the answer
      1   [ dead ] [ base ] [   ?  ]  ...  [      ?        ]
      2   [ dead ] [ dead ] [ base ]  ...  [      ?        ]
      :
    n-1   [ dead ] [ dead ] [ dead ]  ...  [    base       ]

  diagonal  i == j : the length-1 base case  (dp[i][i] = 1, or True)
  below it  i >  j : an empty range — never written, never read
  corner   (0, n-1): the whole sequence — this is what you return

   the 2 x 2 window, drawn the same way up as the table above:

                        j-1              j
                  ┌──────────────┬──────────────┐
        row i     │  dp[i][j-1]  │   dp[i][j]   │  ← 🎯 being filled
                  ├──────────────┼──────────────┤
        row i+1   │ dp[i+1][j-1] │  dp[i+1][j]  │
                  └──────────────┴──────────────┘

   dp[i][j]  ⟵  dp[i][j-1]     →  from the LEFT      — drop the right end s[j]
   dp[i][j]  ⟵  dp[i+1][j]     ↑  from BELOW         — drop the left end  s[i]
   dp[i][j]  ⟵  dp[i+1][j-1]   ↗  from BELOW-LEFT    — drop BOTH ends

   Every arrow travels UP and to the RIGHT. Nothing arrives from above or from
   the right, so the table fills from the diagonal OUTWARD, toward the
   top-right corner.

# python
# LC 516 - Longest Palindromic Subsequence
# IDEA: i descends so row i+1 is already done; j ascends so column j-1 is already done
# time = O(n^2), space = O(n^2)
def longestPalindromeSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    for i in range(n):                 # base: one character is a palindrome of length 1
        dp[i][i] = 1

    for i in range(n - 1, -1, -1):     # ↑ bottom row first
        for j in range(i + 1, n):      # → left to right, staying above the diagonal
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    return dp[0][n - 1]

# python
# IDEA: same table, one diagonal at a time. The only order that works when the transition
#       needs a split point k (dp[i][k] and dp[k][j]) instead of the two ends.
# time = O(n^2) for a two-end transition, O(n^3) once a k-loop is nested inside
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
    dp[i][i] = 1                        # base: the length-1 diagonal
for length in range(2, n + 1):          # sub-range length: short → long
    for i in range(n - length + 1):     # left end
        j = i + length - 1              # right end is derived, never looped
        if s[i] == s[j]:                # same transition as Order A (LC 516)
            dp[i][j] = dp[i + 1][j - 1] + 2
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

   Order A  (i: n-1→0, j: i+1→n-1)        Order B  (length: 2→n, i: 0→n-length)
          j0   j1   j2   j3   j4                  j0   j1   j2   j3   j4
    i0     ·    7    8    9   10            i0     ·    1    5    8   10
    i1          ·    4    5    6            i1          ·    2    6    9
    i2               ·    2    3            i2               ·    3    7
    i3                    ·    1            i3                    ·    4
    i4                         ·            i4                         ·

    row by row, bottom → top                diagonal by diagonal, ↗

  Check the corner cell dp[0][4] — step 10 in both orders.
  It reads dp[1][3], dp[1][4], dp[0][3]:
    Order A → steps 5, 6, 9   ✅ all filled before step 10
    Order B → steps 6, 9, 8   ✅ all filled before step 10

   s =       b    b    b    a    b
             j0   j1   j2   j3   j4
   b   i0  [ 1 ][ 2 ][ 3 ][ 3 ][ 4 ]  ← 🎯 answer = 4
   b   i1    ·  [ 1 ][ 2 ][ 2 ][ 3 ]
   b   i2    ·    ·  [ 1 ][ 1 ][ 3 ]
   a   i3    ·    ·    ·  [ 1 ][ 1 ]
   b   i4    ·    ·    ·    ·  [ 1 ]

   dp[2][3] = 1 : 'b' != 'a'      → max(dp[3][3]=1, dp[2][2]=1) = 1
   dp[0][2] = 3 : s[0]=='b'==s[2] → dp[1][1] + 2 = 3          ("bbb")
   dp[1][3] = 2 : 'b' != 'a'      → max(dp[2][3]=1, dp[1][2]=2) = 2
   dp[0][4] = 4 : s[0]=='b'==s[4] → dp[1][3] + 2 = 4          ("bbbb")

   at (0,4)  s[0]=='b'==s[4]           → matched pair: take both, jump ↘ to (1,3)
   at (1,3)  'b' != 'a', and
             dp[1][2]=2 > dp[2][3]=1   → the max came from the LEFT: drop s[3], move to (1,2)
   at (1,2)  s[1]=='b'==s[2]           → matched pair: take both, jump ↘ to (2,1)
   at (2,1)  i > j                     → empty range: stop

   pairs collected, outer → inner:  (s0, s4) then (s1, s2)
   answer string:   b [ b  b ] b   =  "bbbb"   ✓ length 4 = dp[0][4]

                  ""     s2[0]  s2[1]   ...   s2[n-1]
             j =   0       1      2     ...      n
   ""    i =  0  [base] [base] [base]  ...  [ base ]   ← s1 is empty
  s1[0]       1  [base] [  ?  ][  ?  ] ...  [  ?   ]
  s1[1]       2  [base] [  ?  ][  ?  ] ...  [  ?   ]
    :
  s1[m-1]     m  [base] [  ?  ][  ?  ] ...  [ 🎯 dp[m][n] ]  ← the answer

  row 0 / column 0 : one string is empty, so the answer is FORCED, not computed
  every other cell : three neighbours, one decision

   the same 2 x 2 window, one row higher:

                        j-1              j
                  ┌──────────────┬──────────────┐
        row i-1   │ dp[i-1][j-1] │  dp[i-1][j]  │
                  ├──────────────┼──────────────┤
        row i     │  dp[i][j-1]  │   dp[i][j]   │  ← 🎯 being filled
                  └──────────────┴──────────────┘

   dp[i][j]  ⟵  dp[i-1][j-1]   ↘  from ABOVE-LEFT   — consume from BOTH strings
   dp[i][j]  ⟵  dp[i-1][j]     ↓  from ABOVE        — consume from s1 only
   dp[i][j]  ⟵  dp[i][j-1]     →  from the LEFT     — consume from s2 only

   Nothing arrives from below or from the right, so plain row-major
   (i: 1 → m, inner j: 1 → n) is legal — and it is the only order anyone writes.

# python
# LC 72 - Edit Distance
# IDEA: Shape B — base row/col are the forced answers, then row-major over three neighbours
# time = O(m * n), space = O(m * n)  → O(min(m, n)) once rolled
def minDistance(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i          # s2 empty → delete every character of s1
    for j in range(n + 1):
        dp[0][j] = j          # s1 empty → insert every character of s2

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]          # ↘ free
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],                    # ↓ delete
                    dp[i][j - 1],                    # → insert
                    dp[i - 1][j - 1],                # ↘ replace
                )

    return dp[m][n]

              ""    r     o     s
        ""  [ 0*]   1     2     3
        h   [ 1 ] [ 1*]   2     3
        o   [ 2 ]   2   [ 1*]   2
        r   [ 3 ]   2   [ 2*]   2
        s   [ 4 ]   3     3   [ 2*]
        e   [ 5 ]   4     4   [ 3*]   ← 🎯 dp[5][3] = 3

   * = the cells on the chosen path, recovered by walking backwards from dp[5][3]:

   (5,3) 'e' vs 's' ✗   1 + min(↓ dp[4][3]=2, → dp[5][2]=4, ↘ dp[4][2]=3)
                        the min came from ↓   ⇒ DELETE 'e'
   (4,3) 's' == 's' ✓   free ↘                ⇒ KEEP 's'
   (3,2) 'r' vs 'o' ✗   1 + min(↓ dp[2][2]=1, → dp[3][1]=2, ↘ dp[2][1]=2)
                        the min came from ↓   ⇒ DELETE 'r'
   (2,2) 'o' == 'o' ✓   free ↘                ⇒ KEEP 'o'
   (1,1) 'h' vs 'r' ✗   1 + min(↓ dp[0][1]=1, → dp[1][0]=1, ↘ dp[0][0]=0)
                        the min came from ↘   ⇒ REPLACE 'h' → 'r'
   (0,0) both prefixes empty                  ⇒ stop

   replayed forwards:   replace h→r   "horse" → "rorse"
                        keep    o
                        delete  r     "rorse" → "rose"
                        keep    s
                        delete  e     "rose"  → "ros"    ✓ 3 ops = dp[5][3]

# python
# IDEA: rolling row — prev is row i-1, cur is row i. s2 is the inner axis, so pass the
#       SHORTER string as s2.
# time = O(m * n), space = O(min(m, n))
def minDistance_rolled(s1, s2):
    m, n = len(s1), len(s2)
    prev = list(range(n + 1))
    for i in range(1, m + 1):
        cur = [i] + [0] * n
        for j in range(1, n + 1):
            cur[j] = prev[j - 1] if s1[i - 1] == s2[j - 1] else 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[n]

# python
# LC 312 - Burst Balloons
# IDEA: interval DP — pick k as the LAST balloon burst in (left, right); its neighbours are then fixed
# time = O(n^3), space = O(n^2)
def maxCoins(nums):
    n = len(nums)
    balloons = [1] + nums + [1]                 # boundary balloons with value 1
    dp = [[0] * (n + 2) for _ in range(n + 2)]  # dp[i][j]: open interval (i, j)

    for length in range(2, n + 2):              # short intervals first
        for left in range(n + 2 - length):
            right = left + length
            for k in range(left + 1, right):    # k = the LAST balloon burst in (left, right)
                coins = balloons[left] * balloons[k] * balloons[right]
                total = coins + dp[left][k] + dp[k][right]
                dp[left][right] = max(dp[left][right], total)

    return dp[0][n + 1]

// java
// LC 312 - Burst Balloons
// IDEA: interval DP — pick k as the LAST balloon burst in (i, j); its neighbours are then fixed
// time = O(n^3), space = O(n^2)
public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] balloons = new int[n + 2];          // boundaries: [1, ...nums..., 1]
    balloons[0] = 1;
    balloons[n + 1] = 1;
    for (int i = 0; i < n; i++) {
        balloons[i + 1] = nums[i];
    }

    int[][] dp = new int[n + 2][n + 2];       // dp[i][j]: open interval (i, j)
    for (int len = 2; len <= n + 1; len++) {  // short intervals first
        for (int i = 0; i <= n + 1 - len; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) { // k = the LAST balloon burst in (i, j)
                int total = balloons[i] * balloons[k] * balloons[j] + dp[i][k] + dp[k][j];
                dp[i][j] = Math.max(dp[i][j], total);
            }
        }
    }
    return dp[0][n + 1];
}

nums = [3, 1, 5]   ->  balloons = [1, 3, 1, 5, 1]   (indexes 0..4)

length 2: every (i, i+2) has one balloon inside
  dp[0][2] = 1*3*1 = 3     dp[1][3] = 3*1*5 = 15     dp[2][4] = 1*5*1 = 5
length 3:
  dp[0][3] = max(k=1: 1*3*5 + 0 + dp[1][3]=15 -> 30,  k=2: 1*1*5 + dp[0][2]=3 + 0 -> 8)  = 30
  dp[1][4] = max(k=2: 3*1*1 + 0 + dp[2][4]=5 -> 8,    k=3: 3*5*1 + dp[1][3]=15 + 0 -> 30) = 30
length 4:
  dp[0][4] = max(k=1: 3 + 0 + 30 = 33,  k=2: 1 + 3 + 5 = 9,  k=3: 5 + 30 + 0 = 35) = 35

# python
# IDEA: 0/1 knapsack, max value — dp[w] = best value within capacity w; the backward loop uses each item once
# time = O(n * W), space = O(W)
def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)                 # dp[w] = best value with total weight <= w
    for i in range(len(weights)):
        for w in range(capacity, weights[i] - 1, -1):   # backward: dp[w - weight] is still "without i"
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[capacity]

// java
// IDEA: 0/1 knapsack, max value — dp[w] = best value within capacity w; the backward loop uses each item once
// time = O(n * W), space = O(W)
public int knapsack01(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];             // dp[w] = best value with total weight <= w
    for (int i = 0; i < weights.length; i++) {
        for (int w = capacity; w >= weights[i]; w--) {   // backward: dp[w - weight] is still "without i"
            dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

dp = [0, 0, 0, 0, 0, 0, 0]
      0  1  2  3  4  5  6

Forward (WRONG):   w=3: dp[3] = dp[0] + 5 = 5
                   w=6: dp[6] = dp[3] + 5 = 10   <- dp[3] already holds this item: taken twice ❌
Backward (RIGHT):  w=6: dp[6] = dp[3] + 5 = 5    <- dp[3] is still 0, "without the item"
                   w=3: dp[3] = dp[0] + 5 = 5
                   result dp[6] = 5 ✓

# python
# LC 309 - Best Time to Buy and Sell Stock with Cooldown
# IDEA: three states per day; each reads yesterday's values, so snapshot before updating
# time = O(n), space = O(1)
def maxProfit(prices):
    if not prices:
        return 0
    hold = -prices[0]      # bought on day 0
    sold = 0               # cannot have sold on day 0; 0 is the neutral value
    rest = 0               # no share, not in cooldown

    for i in range(1, len(prices)):
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - prices[i])   # keep holding, or buy (only from rest)
        sold = prev_hold + prices[i]                   # sell what you held
        rest = max(prev_rest, prev_sold)               # stay idle, or finish the cooldown

    return max(sold, rest)

// java
// LC 309 - Best Time to Buy and Sell Stock with Cooldown
// IDEA: three states per day; each reads yesterday's values, so snapshot before updating
// time = O(n), space = O(1)
public int maxProfit(int[] prices) {
    if (prices.length == 0) {
        return 0;
    }
    int hold = -prices[0];
    int sold = 0;
    int rest = 0;

    for (int i = 1; i < prices.length; i++) {
        int prevHold = hold, prevSold = sold, prevRest = rest;
        hold = Math.max(prevHold, prevRest - prices[i]);  // keep holding, or buy (only from rest)
        sold = prevHold + prices[i];                      // sell what you held
        rest = Math.max(prevRest, prevSold);              // stay idle, or finish the cooldown
    }
    return Math.max(sold, rest);
}

prices = [1, 2, 3, 0, 2]
day 0  p=1  hold=-1  sold=0   rest=0
day 1  p=2  hold=-1  sold=1   rest=0
day 2  p=3  hold=-1  sold=2   rest=1
day 3  p=0  hold= 1  sold=-1  rest=2     buy at 0, from rest (the day-1 sale has cooled down)
day 4  p=2  hold= 1  sold=3   rest=2     answer max(3, 2) = 3

# python
# LC 198 - House Robber
# IDEA: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) -> only 2 vars needed
# time = O(n), space = O(1)
def rob(nums):
    if not nums:
        return 0
    n = len(nums)
    if n == 1:
        return nums[0]          # p2's seed reads nums[1], so n == 1 must leave early

    # invariant at the top of iteration i:  p1 = dp[i-2],  p2 = dp[i-1]
    p1 = nums[0]                        # dp[0]
    p2 = max(nums[0], nums[1])          # dp[1]

    for i in range(2, n):
        cur = max(p1 + nums[i], p2)     # dp[i]
        p1 = p2                         # oldest -> newest
        p2 = cur

    return p2                           # NOT `cur`

// java
// LC 198 - House Robber
// IDEA: same 2-variable rolling window; return the rolling var, not the temp
// time = O(n), space = O(1)
public int rob(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int n = nums.length;
    if (n == 1) return nums[0];

    int p1 = nums[0];                       // dp[0]
    int p2 = Math.max(nums[0], nums[1]);    // dp[1]

    for (int i = 2; i < n; i++) {
        int cur = Math.max(p1 + nums[i], p2);
        p1 = p2;
        p2 = cur;
    }
    return p2;   // hoisting `cur` out of the loop just to return it would need `int cur = 0;`
                 // -> returns 0 for n == 2 instead of the real answer
}

n = 2, nums = [2, 7]

  p1 = 2                  <- dp[0]
  p2 = max(2, 7) = 7      <- dp[1]
  for i in range(2, 2):   <- zero iterations, `cur` never assigned

  return p2  -> 7         ✅
  return cur -> UnboundLocalError  ❌

# python
# LC 198 - House Robber, top-down
# IDEA: dp(i) = best over houses 0..i; cache each i so the two-way recursion is linear
# time = O(n), space = O(n)
def top_down_dp(nums):
    """Top-down DP with memoization"""
    memo = {}

    def dp(i):
        # Base case
        if i < 0:
            return 0
        if i == 0:
            return nums[0]

        # Check memo
        if i in memo:
            return memo[i]

        # Recurrence relation
        result = max(dp(i-1), dp(i-2) + nums[i])
        memo[i] = result
        return result

    return dp(len(nums) - 1)

# python
# IDEA: a recurrence that reads two cells back needs two variables, prev2 and prev1
# time = O(n), space = O(1)
def fibonacci_variants():
    """Common Fibonacci-like patterns"""

    # 1. Classic Fibonacci
    def fibonacci(n):
        if n <= 1:
            return n
        prev2, prev1 = 0, 1
        for _ in range(2, n + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        return prev1

    # 2. Climbing Stairs
    def climbStairs(n):
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            current = prev1 + prev2
            prev2, prev1 = prev1, current
        return prev1

# python
# LC 300 - Longest Increasing Subsequence
# IDEA: dp[i] = LIS ending at i; extend every earlier j whose value is strictly smaller
# time = O(n^2), space = O(n)
def lengthOfLIS(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n                         # each element alone has length 1

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:        # strictly smaller: only then can nums[i] extend it
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

// java
// LC 300 - Longest Increasing Subsequence
// IDEA: dp[i] = LIS ending at i; extend every earlier j whose value is strictly smaller
// time = O(n^2), space = O(n)
public int lengthOfLIS(int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);                  // each element alone has length 1

    int best = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {     // strictly smaller: only then can nums[i] extend it
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        best = Math.max(best, dp[i]);    // the chain can end at any index
    }
    return best;
}

nums = [10, 9, 2, 5, 3, 7, 101, 18]
dp    = [1,  1, 1, 2, 2, 3,   4,  4]
         i=3: 2 < 5          -> dp[2]+1 = 2
         i=5: 2, 5, 3 < 7    -> max(dp[2], dp[3], dp[4]) + 1 = 3
         i=6, i=7: extend dp[5]  -> 4
answer = max(dp) = 4         ([2, 3, 7, 101] or [2, 5, 7, 18])

# python
# LC 1218 - Longest Arithmetic Subsequence of Given Difference
# IDEA: dp keyed by value — the only legal predecessor of x is x - difference
# time = O(n), space = O(n)
def longestSubsequence(arr, difference):
    dp = {}            # value -> longest chain ending with that value
    max_len = 0
    for x in arr:
        prev = x - difference
        # read the predecessor BEFORE writing dp[x] (matters when difference == 0)
        dp[x] = dp.get(prev, 0) + 1
        max_len = max(max_len, dp[x])
    return max_len

// java
// LC 1218 - Longest Arithmetic Subsequence of Given Difference
// IDEA: dp keyed by value — the only legal predecessor of x is x - difference
// time = O(n), space = O(n)
public int longestSubsequence(int[] arr, int difference) {
    Map<Integer, Integer> dp = new HashMap<>();   // value -> longest chain ending with it
    int maxLen = 0;
    for (int x : arr) {
        int len = dp.getOrDefault(x - difference, 0) + 1;
        dp.put(x, len);
        maxLen = Math.max(maxLen, len);
    }
    return maxLen;
}

arr = [1,5,7,8,5,3,4,2,1], difference = -2      (predecessor of x is x + 2)

x=1  dp[3]? no  -> dp[1]=1
x=5  dp[7]? no  -> dp[5]=1
x=7  dp[9]? no  -> dp[7]=1
x=8  dp[10]? no -> dp[8]=1
x=5  dp[7]=1    -> dp[5]=2        (overwrites the first 5's entry)
x=3  dp[5]=2    -> dp[3]=3
x=4  dp[6]? no  -> dp[4]=1
x=2  dp[4]=1    -> dp[2]=2
x=1  dp[3]=3    -> dp[1]=4        7 -> 5 -> 3 -> 1

answer = 4

# python
# LC 72 - Edit Distance
# IDEA: Shape B grid over prefix lengths; equal last chars are free, else 1 + min of three moves
# time = O(m * n), space = O(m * n)
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):
        dp[i][0] = i                 # word2 empty: delete all i characters
    for j in range(n + 1):
        dp[0][j] = j                 # word1 empty: insert all j characters

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]          # no operation
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],                    # delete word1[i-1]
                    dp[i][j - 1],                    # insert word2[j-1]
                    dp[i - 1][j - 1],                # replace
                )

    return dp[m][n]

# Same recurrence, rolling row: row i reads only row i-1 (prev) and the cell to its left
# time = O(m * n), space = O(n)
def minDistance_rolling(word1, word2):
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))              # row 0: j inserts
    for i in range(1, m + 1):
        prev = dp[:]                     # row i-1
        dp[0] = i                        # column 0: i deletes
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[j] = prev[j - 1]
            else:
                dp[j] = 1 + min(prev[j], dp[j - 1], prev[j - 1])
    return dp[n]

// java
// LC 72 - Edit Distance
// IDEA: Shape B grid over prefix lengths; equal last chars are free, else 1 + min of three moves
// time = O(m * n), space = O(m * n)
public int minDistance(String word1, String word2) {
    int m = word1.length();
    int n = word2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;                // delete all characters
    }
    for (int j = 0; j <= n; j++) {
        dp[0][j] = j;                // insert all characters
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                int delete = dp[i - 1][j];
                int insert = dp[i][j - 1];
                int replace = dp[i - 1][j - 1];
                dp[i][j] = 1 + Math.min(delete, Math.min(insert, replace));
            }
        }
    }
    return dp[m][n];
}

# python
# LC 1143 - Longest Common Subsequence
# IDEA: Shape B grid; matching last chars extend the diagonal, otherwise drop one side
# time = O(m * n), space = O(m * n)
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]   # row 0 / column 0 = empty prefix = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]

# Same recurrence, rolling row: keep only the previous row
# time = O(m * n), space = O(n)
def longestCommonSubsequence_rolling(text1, text2):
    n = len(text2)
    dp = [0] * (n + 1)
    for c in text1:
        prev, dp = dp, [0] * (n + 1)     # prev = row i-1, dp = row i
        for j in range(n):
            if c == text2[j]:
                dp[j + 1] = prev[j] + 1
            else:
                dp[j + 1] = max(prev[j + 1], dp[j])
    return dp[n]

// java
// LC 1143 - Longest Common Subsequence
// IDEA: Shape B grid; matching last chars extend the diagonal, otherwise drop one side
// time = O(m * n), space = O(m * n)
public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length();
    int n = text2.length();
    int[][] dp = new int[m + 1][n + 1];          // row 0 / column 0 = empty prefix = 0

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

text1 = "abcde", text2 = "ace"
          ""  a  c  e
      ""   0  0  0  0
      a    0  1  1  1
      b    0  1  1  1
      c    0  1  2  2
      d    0  1  2  2
      e    0  1  2  3     answer dp[5][3] = 3  ("ace")

# python
# LC 5 - Longest Palindromic Substring
# IDEA: dp[i][j] = s[i..j] is a palindrome; i descends so dp[i+1][j-1] is already filled
# time = O(n^2), space = O(n^2)
def longestPalindrome(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1 if n else 0

    for i in range(n - 1, -1, -1):          # i backward: row i+1 is ready
        for j in range(i, n):               # j forward:  column j-1 is ready
            if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                dp[i][j] = True
                if j - i + 1 > best_len:
                    best_start, best_len = i, j - i + 1

    return s[best_start:best_start + best_len]

// java
// LC 5 - Longest Palindromic Substring
// IDEA: dp[i][j] = s[i..j] is a palindrome; i descends so dp[i+1][j-1] is already filled
// time = O(n^2), space = O(n^2)
public String longestPalindrome(String s) {
    int n = s.length();
    boolean[][] dp = new boolean[n][n];
    int bestStart = 0, bestLen = n == 0 ? 0 : 1;

    for (int i = n - 1; i >= 0; i--) {          // i backward: row i+1 is ready
        for (int j = i; j < n; j++) {           // j forward:  column j-1 is ready
            if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                dp[i][j] = true;
                if (j - i + 1 > bestLen) {
                    bestStart = i;
                    bestLen = j - i + 1;
                }
            }
        }
    }
    return s.substring(bestStart, bestStart + bestLen);
}

s = "cbbd"   (T = s[i..j] is a palindrome)
          j=0  j=1  j=2  j=3
   i=3                    T      "d"
   i=2               T    F      "b", "bd"
   i=1          T    T    F      "b", "bb" (s[1] == s[2], j - i = 1 <= 2), "bbd"
   i=0     T    F    F    F      "c", "cb", "cbb", "cbbd"
longest True range = dp[1][2]  ->  "bb"

# IDEA: loop i backward so dp[i+1][...] is always ready when computing dp[i][...]
def countSubstrings_dp_backward(s):
    # time = O(n^2), space = O(n^2)
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0

    for i in range(n - 1, -1, -1):   # i backward: ensures dp[i+1][j-1] is computed
        for j in range(i, n):         # j forward:  ensures dp[i][j-1] is computed
            if s[i] == s[j] and (j - i <= 2 or dp[i+1][j-1]):
                dp[i][j] = True
                count += 1

    return count

# IDEA: expand around center — O(1) space, no dp table needed
def countSubstrings_two_pointers(s):
    # time = O(n^2), space = O(1)
    count = 0
    n = len(s)

    def expand(l, r):
        cnt = 0
        while l >= 0 and r < n and s[l] == s[r]:
            cnt += 1
            l -= 1
            r += 1
        return cnt

    for i in range(n):
        count += expand(i, i)      # odd-length  (center at i)
        count += expand(i, i + 1)  # even-length (center between i and i+1)

    return count

Center i=0:
  odd  (0,0): "a"          → count +1
  even (0,1): "aa"         → count +1

Center i=1:
  odd  (1,1): "a"→(0,2)"aaa" → count +2  (expands to full string)
  even (1,2): "aa"         → count +1

Center i=2:
  odd  (2,2): "a"          → count +1
  even (2,3): out of bounds → count +0

Total = 6  ✓

Need the full dp[i][j] table? (e.g., for partitioning / further DP)
  YES → Use 2D DP (Approach 1)
  NO  → Use Two Pointers (Approach 2) — simpler + O(1) space

# python
# LC 1879 - Minimum XOR Sum of Two Arrays
# IDEA: dp[mask] = best cost having paired nums1[:popcount(mask)] with the nums2 items in mask
# time = O(2^n * n), space = O(2^n)
def minimumXORSum(nums1, nums2):
    n = len(nums1)
    full = (1 << n) - 1
    INF = float('inf')
    dp = [INF] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == INF:
            continue
        k = bin(mask).count('1')           # next nums1 index to pair
        if k == n:
            continue
        for j in range(n):
            if not mask & (1 << j):        # nums2[j] still free
                nxt = mask | (1 << j)
                dp[nxt] = min(dp[nxt], dp[mask] + (nums1[k] ^ nums2[j]))

    return dp[full]

// java
// LC 1879 - Minimum XOR Sum of Two Arrays
// IDEA: dp[mask] = best cost having paired nums1[:popcount(mask)] with the nums2 items in mask
// time = O(2^n * n), space = O(2^n)
public int minimumXORSum(int[] nums1, int[] nums2) {
    int n = nums1.length;
    int[] dp = new int[1 << n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;

    for (int mask = 0; mask < (1 << n); mask++) {
        if (dp[mask] == Integer.MAX_VALUE) {
            continue;
        }
        int k = Integer.bitCount(mask);          // next nums1 index to pair
        if (k == n) {
            continue;
        }
        for (int j = 0; j < n; j++) {
            if ((mask & (1 << j)) == 0) {        // nums2[j] still free
                int nxt = mask | (1 << j);
                dp[nxt] = Math.min(dp[nxt], dp[mask] + (nums1[k] ^ nums2[j]));
            }
        }
    }
    return dp[(1 << n) - 1];
}

# python
# LC 233 - Number of Digit One
# IDEA: digit DP over (pos, ones so far, tight); only tight states depend on n's digits
# time = O(D^2 * 10), space = O(D^2)   D = number of digits in n
from functools import lru_cache

def countDigitOne(n):
    digits = list(map(int, str(n)))
    D = len(digits)

    @lru_cache(maxsize=None)
    def count(pos, ones, tight):
        if pos == D:
            return ones                       # one finished number: its count of 1s
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(limit + 1):
            total += count(pos + 1, ones + (d == 1), tight and d == limit)
        return total

    return count(0, 0, True)

// java
// LC 233 - Number of Digit One
// IDEA: digit DP over (pos, ones so far, tight); only non-tight states are cached
// time = O(D^2 * 10), space = O(D^2)   D = number of digits in n
private int[] digits;
private Integer[][] memo;                         // memo[pos][ones], non-tight states only

public int countDigitOne(int n) {
    String s = Integer.toString(n);
    digits = new int[s.length()];
    for (int i = 0; i < s.length(); i++) {
        digits[i] = s.charAt(i) - '0';
    }
    memo = new Integer[digits.length][digits.length + 1];
    return count(0, 0, true);
}

private int count(int pos, int ones, boolean tight) {
    if (pos == digits.length) {
        return ones;                              // one finished number: its count of 1s
    }
    if (!tight && memo[pos][ones] != null) {
        return memo[pos][ones];
    }
    int limit = tight ? digits[pos] : 9;
    int total = 0;
    for (int d = 0; d <= limit; d++) {
        total += count(pos + 1, ones + (d == 1 ? 1 : 0), tight && d == limit);
    }
    if (!tight) {
        memo[pos][ones] = total;
    }
    return total;
}

n = 13  ->  digits [1, 3]
pos 0, tight: d = 0 (free) or d = 1 (stays tight)
  d=0: numbers 00..09 -> pos 1 free, ones=0 -> d=1 adds one        -> 1
  d=1: numbers 10..13 -> pos 1 tight (limit 3), ones=1 -> 4 numbers carry 1 each,
       and d=1 at pos 1 (the 11) adds one more                     -> 5
answer = 1 + 5 = 6     (1, 10, 11, 11, 12, 13)

DP Problem Identification Flowchart:

1. Can the problem be broken into subproblems?
   ├── NO → Not a DP problem
   └── YES → Continue to 2

2. Do subproblems overlap?
   ├── NO → Use Divide & Conquer
   └── YES → Continue to 3

3. Does it have optimal substructure?
   ├── NO → Not a DP problem
   └── YES → Use DP, continue to 4

4. What type of DP pattern?
   ├── Single sequence → Linear DP (Template 1)
   ├── 2D grid/matrix → Grid DP (Template 2)
   ├── Interval/substring → Interval DP (Template 3)
   ├── Selection with limit → Knapsack (Template 4)
   └── Multiple states → State Machine (Template 5)

5. Implementation approach?
   ├── Recursive structure clear → Top-down memoization
   └── Iterative structure clear → Bottom-up tabulation

# 1D: Position/index based
dp[i] = "optimal value considering first i elements"

# 2D: Two dimensions
dp[i][j] = "optimal value for subproblem (i, j)"

# Interval: Range based  
dp[i][j] = "optimal value for interval [i, j]"

# Boolean: Decision problems
dp[i] = "whether target i is achievable"