DP 迴圈順序與相依性

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

  dp[0]   dp[1] ... dp[4] ............ dp[8]
    │                ▲                   ▲
    └──── "leet" ────┘                   │
                     └────── "code" ─────┘

  every arrow points RIGHT  (i - len(word) < i, because len(word) >= 1)
      → any order that fills dp[] left to right is legal
      → an order that finishes "all of word w, then all of word w'" is NOT a
        left-to-right order at all — it is an order over WORDS, and the arrows
        do not care about words

Step 1.  Write the transition. Underline every dp[...] on the RIGHT-hand side.
Step 2.  For each one, name the index it reads relative to the one being written.
             -> this fixes the DIRECTION of the state loop              (§1-2)
Step 3.  Does the transition also range over a set of ITEMS
         (coins, words, squares, intermediate vertices)?
             no  -> you are done, one loop
             yes -> may that item loop sit OUTSIDE the state loop?      (§1-4)

# python
# IDEA: the two nestings of one transition -- dp[i] <- dp[i - size(item)]

# (A) STATE-outer: "to reach state i, which item was placed LAST?"
for i in range(1, n + 1):          # state
    for item in items:             # item
        if i >= size(item):
            dp[i] = combine(dp[i], dp[i - size(item)])

# (B) ITEM-outer: "introduce item 1 everywhere, then item 2 everywhere, ..."
for item in items:                 # item
    for i in range(size(item), n + 1):   # state
        dp[i] = combine(dp[i], dp[i - size(item)])

Q1. How do the chosen items compose into the answer?
Q2. Is that composition free to be re-ordered?

    coins / squares:  they are ADDED        3 + 1 + 3 == 1 + 3 + 3     ✅ commutes
    words:            they are CONCATENATED "apple"+"pen" != "pen"+"apple"  ❌ does not

s = "codeleet", dict order ["code", "leet"]  -> item-outer returns True   ✅ (correct)
s = "codeleet", dict order ["leet", "code"]  -> item-outer returns False  ❌ (same input!)

# python
# LC 139 - Word Break
# IDEA: state-outer -- "to end a segmentation at i, which dictionary word was placed LAST?"
# time = O(n * k * L), space = O(n)    n = len(s), k = len(wordDict), L = max word length
class Solution(object):
    def wordBreak(self, s, wordDict):
        n = len(s)
        d_set = set(wordDict)

        dp = [False] * (n + 1)
        dp[0] = True

        # NOTE !!! index OUTSIDE, dictionary INSIDE
        #   -> dp[i - w] is a strictly smaller index, so it is already final
        for i in range(1, n + 1):
            for word in d_set:
                w = len(word)
                if i >= w and dp[i - w] and s[i - w:i] == word:
                    dp[i] = True
                    break          # it is an OR -- one witness is enough
        return dp[n]

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

i=1..3   no word ends here                          dp[1..3] = False
i=4      "leet": dp[0]=True and s[0:4]=="leet"   ->  dp[4] = True
i=5..7   "leet"/"code" do not match ending here      dp[5..7] = False
i=8      "code": dp[4]=True and s[4:8]=="code"   ->  dp[8] = True   ← answer

# python
# LC 139 - Word Break
# IDEA: state-outer, driven by CUT POINTS instead of by words -- "where did the last word start?"
# time = O(n^2) cuts * O(L) slice+hash, space = O(n)
for i in range(1, n + 1):
    for j in range(i):                 # j = start of the candidate last word
        if dp[j] and s[j:i] in d_set:
            dp[i] = True
            break

# python
# LC 139 - Word Break -- ❌ WRONG, do not write this
# IDEA: item-outer, copied from the coin-change shape. One pass per word.
for word in wordDict:                  # ❌ dictionary OUTSIDE
    w = len(word)
    for i in range(w, n + 1):
        if dp[i - w] and s[i - w:i] == word:
            dp[i] = True

s = "applepenapple"  (n = 13),  dict = ["apple", "pen"]

pass 1 — word = "apple" (len 5)
    i=5   dp[0]=True,  s[0:5]  == "apple"   -> dp[5]  = True
    i=10  dp[5]=True,  s[5:10] == "penap"   ✗
    i=13  dp[8]=False                       ✗   ← dp[8] does not exist YET
    state: dp true at {0, 5}

pass 2 — word = "pen" (len 3)
    i=8   dp[5]=True,  s[5:8]  == "pen"     -> dp[8]  = True   ← too late for pass 1
    i=13  dp[10]=False                      ✗
    state: dp true at {0, 5, 8}

    dp[13] = False   ❌   (correct answer: True)

# python
# LC 139 - Word Break -- item-outer made correct by iterating to a fixpoint
# IDEA: each round can only add True cells; stop when a round adds none
# time = O(rounds * n * k * L), rounds <= n / min_word_len + 1, space = O(n)
changed = True
while changed:
    changed = False
    for word in wordDict:
        w = len(word)
        for i in range(w, n + 1):
            if not dp[i] and dp[i - w] and s[i - w:i] == word:
                dp[i] = True
                changed = True

# python
# LC 139 - Word Break
# IDEA: same DAG, but the topological order is discovered at run time instead of hard-coded
# time = O(n^2) (or O(n * k * L) scanning words), space = O(n)
from collections import deque

q = deque([0])
visited = {0}
while q:
    idx = q.popleft()
    if idx == n:
        return True
    for word in wordDict:
        end = idx + len(word)
        if end <= n and s[idx:end] == word and end not in visited:
            visited.add(end)
            q.append(end)
return False

# python
# LC 139 - Word Break
# IDEA: recursion discovers the dependency order itself; memo makes it O(n^2)
# time = O(n^2 * L), space = O(n) memo + O(n) stack
from functools import lru_cache

@lru_cache(None)
def can(start):
    if start == n:
        return True
    return any(s.startswith(word, start) and can(start + len(word)) for word in wordDict)

return can(0)

# python
# LC 279 - Perfect Squares
# IDEA: unbounded knapsack (min). Squares are summed, so they re-order freely -> both nestings work
# time = O(n * sqrt(n)), space = O(n)
sq = [k * k for k in range(1, int(n ** 0.5) + 1)]
dp = [0] + [float("inf")] * n

for val in sq:                       # item-outer -- legal here, illegal in LC 139
    for j in range(val, n + 1):
        dp[j] = min(dp[j], dp[j - val] + 1)
return dp[n]

LC 279   12 = 4 + 4 + 4   -- the multiset can be walked in ANY order,      so a single pass per square suffices
LC 139   "applepenapple"  -- the words must appear in the order s says,    so a single pass per word does not

# python
# LC 518 - Coin Change II -- COMBINATIONS: coins outer
for coin in coins:
    for i in range(coin, amount + 1):
        dp[i] += dp[i - coin]

# python
# LC 377 - Combination Sum IV -- PERMUTATIONS: amount outer
for i in range(1, target + 1):
    for num in nums:
        if i >= num:
            dp[i] += dp[i - num]

coins = [1, 2], amount = 3

coin-outer   -> 2 : {1,1,1}, {1,2}            each multiset counted ONCE
amount-outer -> 3 : {1,1,1}, {1,2}, {2,1}     every ORDERING counted

# python
# LC 416 - Partition Equal Subset Sum
# IDEA: 0/1 knapsack -- each number once, so the capacity loop must NOT see its own writes
# time = O(n * target), space = O(target)
for num in nums:
    for s_ in range(target, num - 1, -1):    # ❗ descending
        dp[s_] = dp[s_] or dp[s_ - num]

# python
# IDEA: k = "may paths route through vertex k?" -- an ITEM loop, and it belongs outside
# time = O(V^3), space = O(V^2)
for k in range(V):                 # ❗ intermediate vertex -- OUTERMOST
    for i in range(V):
        for j in range(V):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

1.  Shuffle the item list, re-run.            answer moved  -> item loop is wrongly outside (§1-5)
2.  Write the memoised version (§0-4).        they disagree -> the LOOP is wrong, not the recurrence
3.  Print dp[] after every outer iteration.   a cell flips True LATE -> something read it too early
4.  Re-run the item-outer loop to a fixpoint. answer changes -> one pass was not a closure (§2-6)
5.  Ask §1-4 out loud: "can a solution's items be re-ordered into my loop's order?"