A second dimension records another independent choice
For longest common subsequence, dp[i][j] is the best length using prefixes of lengths i and j. Matching final characters extend the diagonal state; otherwise discard one final character and choose the better predecessor.
fun lcs(a: String, b: String): Int {
val dp = Array(a.length + 1) { IntArray(b.length + 1) }
for (i in 1..a.length) for (j in 1..b.length) {
dp[i][j] = if (a[i - 1] == b[j - 1]) dp[i - 1][j - 1] + 1
else maxOf(dp[i - 1][j], dp[i][j - 1])
}
return dp[a.length][b.length]
}
Time and table space are O(mn). This operates on Kotlin Char units, not grapheme clusters. For 0/1 knapsack, dimensions instead represent item prefix and capacity. For subset sum, they can represent item prefix and reachable total.
Exercise
Test LCS of "abcde" and "ace" as three, plus empty and disjoint strings. Implement 0/1 subset sum, updating a compressed one-dimensional table in descending order.
Check: ascending updates can reuse an item within the same iteration and accidentally solve an unbounded variant.