Dynamic Programming
DP State Tables
Watch tabulation fill one state at a time with dependencies, current result, and per-step time and space complexity.
O(n * m)
State -:-0
State -:A0
State -:C0
State -:B0
State -:D0
State A:-0
State A:A0
State A:C0
State A:B0
State A:D0
State B:-0
State B:A0
State B:C0
State B:B0
State B:D0
State C:-0
State C:A0
State C:C0
State C:B0
State C:D0
State D:-0
State D:A0
State D:C0
State D:B0
State D:D0
Result
-
Time
O(n * m)
Space
O(n * m)
Step Note
Find LCS length for "ABCD" and "ACBD".
function lcs(a: string, b: string) {
const dp = createTable(a.length + 1, b.length + 1)
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[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[a.length][b.length]
}