Parenthesization
Optimal evaluation of associative expression $A[0] · A[1] · · · A[n−1]$ — e.g., multiplying rectangular matrices
- Guessing = outermost multiplication ${…(k-1)}{…(k)}$
- choices = O(n)
- subproblem = cost of substring A[i:j]
- subproblem = $\Theta (n^2)$
- recurrence:
- DP[i,j] = min(DP[i,k]+DP[k,j]+cost of multiplying (A[i]…A[k-1]) b (A[k]…A[j-1]) for k in range(i+1,j))
- DP[i,i+1] = 0: cost per subproblem = O(j-i) = O(n)
- topological order: increasing substring size. Total time = $O(n^3)$
- original problem = DP[0,n]
Edit Distance
Snapsack
###