Dynamic Programming (Algorithm Design Techniques) MCQs

Dynamic Programming (Algorithm Design Techniques)

---

1. Let T(n) = T(n-1) + n with T(1)=1. The closed-form is:
   A) O(n)
   B) O(n log n)
   C) O(n²)
   D) O(2ⁿ)
   Answer: C
   Explanation: Sum 1+2+…+n = n(n+1)/2 → Θ(n²).
2. For 0/1 Knapsack with n=50 items and capacity W=2000, standard DP table complexity (time) is:
   A) O(nW) = 100k
   B) O(n log W)
   C) O(2ⁿ)
   D) O(W²)
   Answer: A
   Explanation: DP complexity is O(n·W).
3. Coin change (minimum coins) for amount A using unlimited coins {1,3,4}: DP recurrence dp[x]=min(dp[x - c])+1. Complexity to compute up to A=100 is:
   A) O(A·k) where k=number of coins
   B) O(A²)
   C) O(2^A)
   D) O(A log A)
   Answer: A
   Explanation: For each amount, try k coins → O(A·k).
4. LCS of strings of lengths m and n has time complexity:
   A) O(m + n)
   B) O(mn)
   C) O(2^n)
   D) O(m log n)
   Answer: B
   Explanation: Standard DP fills m×n table → O(mn).
5. Longest Increasing Subsequence (LIS) with patience sorting has time complexity:
   A) O(n²)
   B) O(n log n)
   C) O(n)
   D) O(log n)
   Answer: B
   Explanation: Using binary search for piles → O(n log n).
6. For Matrix Chain Multiplication with dimensions 30x35x15x5x10x20x25 (n=6 matrices), DP complexity is:
   A) O(n³)
   B) O(n²)
   C) O(2^n)
   D) O(n⁴)
   Answer: A
   Explanation: Standard MCM DP is O(n³) for n matrices.
7. Number of ways to climb n=10 stairs with steps {1,2} via DP is Fibonacci-like; dp[n] calculation uses O(n). So answer complexity:
   A) O(2^n)
   B) O(n)
   C) O(log n)
   D) O(n²)
   Answer: B
   Explanation: dp[i]=dp[i-1]+dp[i-2], computed linearly → O(n).
8. Weighted Interval Scheduling for n intervals uses DP+binary-search (p(i)) and runs in:
   A) O(n²)
   B) O(n log n)
   C) O(n)
   D) O(2^n)
   Answer: B
   Explanation: Sorting O(n log n) + DP with binary search O(n log n).
9. For Partition problem (subset sum) with total sum S=5000 and n=100, DP (bitset) time is:
   A) O(nS)
   B) O(n log S)
   C) O(S) using bitset shifts → O(n·(S/word_size))
   D) O(2^n)
   Answer: C
   Explanation: Bitset optimization shifts bits in O(S/word) per item.
10. Edit distance (Levenshtein) for strings length 200 and 300 takes:
    A) O(200·300) time and space
    B) O(200+300)
    C) O(2^(200+300))
    D) O(log n)
    Answer: A
    Explanation: DP table of size m×n → O(mn).
11. DP for Catalan numbers using C(n)=Σ C(i)C(n-1-i) naive takes:
    A) O(n²)
    B) O(n)
    C) O(2^n)
    D) O(n³)
    Answer: A
    Explanation: Fill n values with inner loop → O(n²).
12. For n=1000 and DP with states dp[i][j] where i,j ≤ n, memory is:
    A) O(n²)
    B) O(n)
    C) O(n log n)
    D) O(1)
    Answer: A
    Explanation: Storing full 2D DP table → O(n²).
13. Knuth optimization reduces DP from O(n³) to O(n²) when quadrangle inequality and monotonicity hold. Which DP benefits?
    A) Matrix chain in general always
    B) Some cost structures like optimal BST for monotone costs
    C) All DP problems
    D) None
    Answer: B
    Explanation: Knuth applies when opt indices monotone (e.g., optimal BST with suitable cost).
14. Bitmask DP for TSP over n=16 vertices has time roughly:
    A) O(n² 2^n)
    B) O(2^n)
    C) O(n 2^n)
    D) O(n!)
    Answer: A
    Explanation: Standard DP: O(n²·2ⁿ).
15. DP with convex hull trick optimizes DP of form dp[i]=min_j (dp[j]+a[j]*b[i]+c[i]) when slopes monotone. Complexity can become:
    A) O(n log n) or O(n) amortized
    B) O(n²) always
    C) O(2ⁿ)
    D) O(n³)
    Answer: A
    Explanation: Use CHT with deque or Li Chao tree → O(n) amortized or O(n log n).
16. For counting palindromic substrings in a string of length n via DP, time is:
    A) O(n²)
    B) O(n log n)
    C) O(n) via Manacher’s algorithm
    D) O(2^n)
    Answer: A (DP) but C is achievable
    Explanation: DP expanding centers is O(n²); Manacher gives O(n).
17. Number of binary trees with n nodes (Catalan) dynamic programming uses O(n²) time. For n=1000, this is expensive; using modular arithmetic still O(n²). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Catalan via DP is O(n²).
18. For DP on trees computing sizes dp[u] and combining children, complexity is:
    A) O(n) (one DFS)
    B) O(n²)
    C) O(log n)
    D) O(2^n)
    Answer: A
    Explanation: Single DFS visiting edges once → O(n).
19. LCS length can be recovered from DP table; memory optimized version that stores only two rows gives length but not sequence. To recover sequence you need:
    A) Full table O(mn) or parent pointers
    B) O(1) extra space
    C) O(n+m) always
    D) Impossible
    Answer: A
    Explanation: Recovering path requires traceback info.
20. Unbounded knapsack DP with W=10^5 and n=100 has time:
    A) O(nW)
    B) O(W) if optimized using coin-change-like loops? No general — so O(nW)
    C) O(n log W)
    D) O(2^n)
    Answer: A
    Explanation: Standard DP loops over weights per item.
21. For DP with states dp[i][j] where j up to 1000 and i up to 100, we can compress dimension i by rolling array reducing space to:
    A) O(j)
    B) O(ij)
    C) O(1)
    D) O(i)
    Answer: A
    Explanation: If current depends only on previous i-1 row, use rolling array.
22. Min-cost path in grid (n×m) with allowed moves right/down: DP complexity:
    A) O(nm) time and O(nm) space (or O(min(n,m)) with rolling)
    B) O(n+m)
    C) O(2^(n+m))
    D) O(n² m²)
    Answer: A
    Explanation: Simple grid DP.
23. For DP dp[i]=max(dp[i-1],dp[i-2]+a[i]) (house robber), space can be optimized from O(n) to O(1). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Only two previous states needed.
24. For partitioning array into k segments minimizing cost with dp[i][k]=min_{j<i} dp[j][k-1]+cost(j+1,i), if cost is quadrangle-inequality friendly, which optimization may apply?
    A) Divide and conquer DP optimization reduces to O(k n log n) or O(k n)
    B) No optimization
    C) Knuth only
    D) Greedy only
    Answer: A
    Explanation: Divide & conquer optimization reduces transitions when monotone.
25. Edit distance can be computed with O(min(m,n)) space to get distance; to get alignment need O(mn) space or Hirschberg’s algorithm uses divide & conquer to get sequence in:
    A) O(mn) time and O(min(m,n)) space (Hirschberg)
    B) O(m+n) time
    C) O(2^n) time
    D) O(1) space sequence recovery
    Answer: A
    Explanation: Hirschberg trades time for linear space to reconstruct solution.
26. For counting number of ways to tile 2×n board with dominos via DP, recurrence T(n)=T(n-1)+T(n-2) → similar to Fibonacci. Complexity to compute up to n is O(n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Linear DP.
27. For DP where transitions are of type dp[i]=sum_{j<i} dp[j] * w(j,i) naive O(n²); use prefix sums if w depends simply to get O(n). Example: count increasing subsequences with multiplicative weights? Possibly optimized. Which technique helps?
    A) Prefix sums or convolution / FFT if applicable
    B) Can’t optimize
    C) Use backtracking
    D) Use recursion only
    Answer: A
    Explanation: When weights allow cumulative reuse, prefix sums reduce complexity.
28. For dp[i][j] representing using i items to reach sum j, with n up to 100 and sum S up to 10^5, bitset DP reduces constant factor. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Bitset shifts make operations word-parallel speeding large-S DP.
29. Counting subsets whose sum equals S with n=40 — meet-in-the-middle is better than DP if S is huge. Complexity:
    A) O(2^{n/2}) ≈ 2^20 ~ 1e6 feasible
    B) DP O(nS) may be infeasible if S large
    C) Both A and B considerations matter
    D) None apply
    Answer: C
    Explanation: Meet-in-middle suits n up to ~40, DP suits moderate S.
30. For dp[i] edges shortest path on DAG, topological order relaxations yield O(V+E). This is DP because no cycles; true or false?
    A) True
    B) False
    Answer: A
    Explanation: DAG shortest paths via DP in topo order.
31. In bitmask DP for n=20, number of masks is 2^20=1,048,576; each transition over n gives O(n·2^n). Memory for dp array is:
    A) O(2^n) (~1M entries)
    B) O(n·2^n)
    C) O(n)
    D) O(1)
    Answer: A
    Explanation: DP per mask stores one value.
32. For counting LCS variants (number of distinct LCS), one augments DP with counts, careful with duplicates. Complexity remains O(mn). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Adding count dimension still O(mn) time.
33. Suffix automaton can help compute distinct substrings in linear time. Which is faster than naive DP over substrings?
    A) O(n) via suffix automaton
    B) O(n²) naive DP
    C) Both equal
    D) O(2^n)
    Answer: A
    Explanation: SAM builds in O(n); distinct substring count retrieved from states.
34. For dp[i] = min_{j<i} dp[j] + (i-j)^2 + a[i] where cost is convex in j, technique to get O(n) or O(n log n) is:
    A) Convex hull trick
    B) Bitset
    C) Knuth optimization
    D) Backtracking
    Answer: A
    Explanation: CHT applies for linear functions with convexity; yields fast queries.
35. For counting walks of length k in graph, adjacency matrix exponentiation uses matrix power O(n³ log k) — DP via repeated squaring. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Matrix exponentiation complexity as stated.
36. For DP dp[i]=min_{j<i} dp[j] + cost(j,i) with cost obeying monotone quadrangle inequality, which speedup?
    A) Knuth optimization (opt indices monotone) → O(n²)→O(n²) less; more precisely reduces from O(n³) to O(n²)
    B) None
    C) CHT
    D) Bitset
    Answer: A
    Explanation: Knuth reduces cubic to quadratic when applicable.
37. For counting number of ways to partition n into parts, partition function DP p(n) naive is O(n²). True or false?
    A) True
    B) False
    Answer: A
    Explanation: DP nested sums yield O(n²).
38. For DP on sequences where we want minimum cost with window k previous, transitions limit to k elements → complexity O(nk). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Sliding window reduces transitions.
39. In DP for weighted tree vertex cover (choose subset of nodes so every edge covered with minimal weight), standard tree DP uses O(n) time. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Two-state per node DP (take/not take) with DFS → O(n).
40. For counting number of BSTs with distinct keys (Catalan), recurrence uses DP with convolution; can be accelerated with FFT to O(n log n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Convolutions accelerate via FFT.
41. DP for max sum rectangle in 2D: Using Kadane over pairs of rows leads to time O(n² m) for n rows m columns. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Fix row pair and run 1D Kadane over columns → O(n² m).
42. For subset sum via DP using boolean array length S, space is O(S). Using meet-in-the-middle reduces space to O(2^{n/2}). Which is better depends on S vs 2^(n/2). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Choose method based on parameters.
43. For DP on DAG counting number of paths from s to t, topological DP sums counts over outgoing edges; complexity O(V+E). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Straightforward DP in topo order.
44. The “subset convolution” trick used to speed up certain DP over masks can be implemented with FWHT or zeta transforms in O(n·2^n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Subset convolution techniques achieve such bounds.
45. For optimizing knapsack where item weights small (W small), DP O(nW) is best. For n small and weights large, use meet-in-the-middle on items. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Choose approach based on constraints.
46. The DP for minimum edit script where substitution cost = 2, insertion/deletion = 1 leads to dynamic programming with same O(mn). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Costs don’t change table size complexity.
47. For betting DP where states large but many unreachable, sparse DP using hashmap over states can be faster than array DP. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Sparse reachable states justify hashmap DP.
48. For DP requiring backtracking to enumerate all solutions, time becomes proportional to number of solutions times cost per solution — possibly exponential. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Enumeration complexity grows with number of solutions.
49. For sequence DP with transition dp[i]=sum_{j<i} dp[j], we can maintain prefix sums to compute in O(1) per i → overall O(n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: dp[i]=pref[i-1] if that’s the recurrence.
50. For DP with multiple dimensions like dp[i][j][k] where each ranges up to 50, naive complexity O(125k) (50^3). For large memory constraints, one often compresses dimensions or uses meet-in-middle. True or False?
    A) True
    B) False
    Answer: A
    Explanation: High-dimensional DP needs alternative techniques.
51. For dp[i] counting ways to tile 3×n board, recurrence becomes more complex (uses state masks) and complexity is O(n·2^3). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Mask DP per column yields O(n·2^height).
52. DP with monotone queues optimizes sliding-window min/max DP to O(n). Example: dp[i]=min_{j in window} (dp[j]+cost[j]). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Monotonic deque keeps candidate minima.
53. The complexity of DP for counting palindromic partitions of string length n is exponential in worst case due to number of partitions, though finding min cuts DP is O(n²). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Counting all partitions grows exponentially.
54. For dp[i] where transitions depend on nearest k elements and k small, time O(nk) can be acceptable. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Local dependency yields linear times small factor.
55. For computing number of Hamiltonian paths via DP on masks for n up to 20, memory O(n·2^n) is the bottleneck. True or False?
    A) True
    B) False
    Answer: A
    Explanation: DP stores value per (mask,last) pair.
56. For DP requiring rational DP states, beware of floating-point precision; use integers with scaling or DP in log domain. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Numerical stability important.
57. Using memoized recursion vs bottom-up DP both yield same asymptotic complexity if all states visited, but constants differ. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Both perform same number of state computations.
58. For DP on grid with obstacles, we can use BFS-like DP to find shortest path with weights 1; dynamic programming equals BFS. True or False?
    A) True
    B) False
    Answer: A
    Explanation: For uniform weights, BFS yields shortest paths.
59. For sequence alignment with affine gap penalty, DP becomes more complex with extra states but still O(mn). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Add states for gap open/extend; same asymptotic.
60. For calculating Stirling numbers via DP, naive complexity O(n²) or more depending on recurrence. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Recurrence involves summation → quadratic.
61. For DP optimization using “small-to-large” merging on trees (DSU on tree), complexity often O(n log n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Each element moved O(log n) amortized.
62. In knapsack, if weights are divisible (each weight multiple of previous), greedy may succeed — it’s special case. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Special structure can make greedy optimal.
63. DP for minimum path with negative weights on general graphs needs Bellman-Ford (O(VE)). DAG shortest paths via topological DP is faster O(V+E). True or False?
    A) True
    B) False
    Answer: A
    Explanation: DAG allows linear-time DP.
64. The “reconstruction” step in DP (recovering solution) typically requires storing parent pointers, increasing memory by constant factor. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Parent per state needed.
65. For DP currency problem when coin types up to 100 with unlimited coins, using BFS on residues modulo smallest coin can sometimes give O(C) solution—special techniques exist. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Number theory and BFS on residues can optimize.
66. For maximum subarray sum in 1D, Kadane is DP with O(n) time, O(1) space. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Kadane maintains current best and global best.
67. For DP where transitions require min over disjoint intervals, segment tree can answer queries in O(log n) making overall O(n log n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Segment tree stores DP values for fast range minima.
68. For counting palindromic subsequences (distinct), DP is O(n²) time and O(n²) memory. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Two-dimensional DP over indices.
69. For mergeable heaps with DP states merging many times, amortized complexity matters; use union-by-rank style merges to reduce cost. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Amortized union costs help.
70. For DP where state size is exponential but n≤30, bitmask DP feasible. True or False?
    A) True
    B) False
    Answer: A
    Explanation: 2^30 ~ 1e9 too big; but n≤25 sometimes borderline; depends on memory/time.
71. For DP over sequences with alphabet size σ, transitions might multiply by σ; using automata (Aho-Corasick) can compress transitions. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Automata reduce per-character branching.
72. DP with memoization on recursion with many repeated states often yields big speedups vs naive recursion. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Caching avoids recomputation.
73. For DP solving linear recurrences with constant coefficients, use matrix exponentiation to compute nth term in O(k³ log n) where k is order. True or False?
    A) True
    B) False
    Answer: A
    Explanation: State vector size k, matrix power cost O(k³ log n).
74. In 0/1 knapsack, value-based DP (dp[v] = min weight achieving value v) can be better when total value V small → time O(nV). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Choose based on which parameter smaller: weight or value.
75. For minimum path cover in DAG, transform to maximum matching and use matching algorithms; DP alone isn’t enough. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Reduction to bipartite matching used.
76. DP for counting number of ways to parenthesize matrix product (Catalan-like) is O(n³). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Triple loops over i,j,k.
77. For dp[i]=min(dp[j]+cost(j,i)) where cost is arbitrary, no general optimization exists beyond O(n²). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Need problem-specific structure to optimize.
78. For dp[i][j] where each transition involves iterating over k up to n, total complexity can be O(n³). Example: 3D DP naive. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Triple nested loops produce cubic time.
79. For problem of partitioning into palindromic substrings minimum cuts, DP is O(n²) with palindrome precompute. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Precompute pal[i][j] O(n²), then min-cuts O(n²).
80. Minimizing convex cost ∑ f(length(segment)) for partitioning sequence often admits monotone queue or divide&conquer DP optimizations. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Convexity yields monotonicity enabling optimizations.
81. DP for maximum sum of non-adjacent nodes in tree uses tree DP two states per node; complexity O(n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Take/not-take recursion.
82. For counting number of paths with length constraint, DP with polynomial generating functions (via convolution) can speed up sums. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Use polynomial multiplication (FFT) to accelerate.
83. DP with memoization in languages with recursion limits must either increase recursion limit or convert to iterative stack to avoid overflow. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Recursion depth issues are practical concerns.
84. The All-Pairs Shortest Path via Floyd-Warshall is DP O(n³) and in-place on adjacency matrix. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Classic triple-loop DP updates same matrix.
85. For counting subsequences equal to pattern in text, DP dp[i][j] time O(nm) and space O(m) via rolling array possible. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Use one-dimensional array over pattern length.
86. For problems with huge state space but small transitions, online DP with pruning (A* like) may be effective heuristically. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Heuristics can prune DP search.
87. DP for “number of ways to paint a fence” under adjacency constraints can be done using matrix exponentiation for long n in O(k³ log n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Transition matrix exponentiation applies.
88. For DP involving probabilities and expected values (Markov chains), solve linear equations (system) or use value iteration (DP-like). Complexity depends on method. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Expected-value DP requires linear algebra or iterative DP.
89. For counting walks of length k in DAG, simple DP dp[v][t] for t up to k costs O(k(V+E)). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Each step process edges once.
90. For DP that enumerates all subsets per item (e.g., splitting into groups), complexity becomes O(3^n) sometimes. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Some partitioning DP leads to super-exponential enumerations.
91. In DP problems with large alphabet, compressing states via hashing may risk collisions; use perfect hashing or mapping to indices. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Collision risk affects correctness.
92. For dp[i]=max(dp[j])+score(j,i) where transitions are monotone and score increasing, segment tree can be used for range max to get O(log n) updates → O(n log n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Range query structures accelerate DP.
93. For DP that counts distinct subsequences modulo prime, take care of duplicates via last occurrence table to adjust counts; complexity O(n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Classic DP for counting distinct subsequences uses last[] array.
94. For bitmask DP enumerating subsets in increasing mask order, transitions can be optimized by iterating submasks using for(sub=mask; sub; sub=(sub-1)&mask). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Efficient submask iteration trick.
95. For DP that needs to minimize maximum over partitions (minimize max segment sum), binary search on answer + greedy check sometimes works better than DP. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Parametric search converts minimax to decision problem.
96. In DP for minimum path cover in DAG with vertex disjoint paths, convert to matching; DP alone not direct. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Reduction to bipartite matching standard.
97. For dp[i][j] with j up to 1e5 and sparse transitions, compress states to map indices encountered to array of size k to save memory. True or False?
    A) True
    B) False
    Answer: A
    Explanation: Coordinate compression reduces space.
98. DP for counting Hamiltonian cycles in special graphs (like grids) can use transfer-matrix DP with state compression (profile DP) running in O(n·states). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Profile DP standard technique.
99. For problems where transitions are min over previous states weighted by convex function, SMAWK algorithm (monge array) may speed up to O(n log n) or O(n). True or False?
    A) True
    B) False
    Answer: A
    Explanation: Monge/total monotone matrices admit faster row minima.
100. Finally, memoized recursion and bottom-up DP are equivalent in computed states and asymptotic complexity if all states reached; choose whichever fits implementation/space constraints. True or False?
     A) True
     B) False
     Answer: A
     Explanation: Both approaches compute same subproblems; difference is order and constants.