Each of the recurrences below appears somewhere in this week's material. In a bottom-up implementation, which one can be evaluated using only a constant amount of extra space — keeping a fixed number of previously computed values rather than the whole table?

Question

Each of the recurrences below appears somewhere in this week's material. In a  bottom-up  implementation, which one can be evaluated using only a  constant  amount of extra space — keeping a fixed number of previously computed values rather than the whole table?

Accepted Answer

DP[j] = max(DP[j - 1] + a[j], a[j]) — the maximum-sum subarray recurrence.

Answer

DP[i, j] = DP[i - 1, j] + DP[i, j - 1] — the grid path-counting recurrence.

Answer

DP[i] = 1 + the maximum of DP[j] over all j before i with a[j] smaller than a[i] — the longest increasing subsequence recurrence.

Answer

MinCoins[v] = 1 + the minimum of MinCoins[v - c[i]] over all coins with c[i] ≤ v — the coin change recurrence.

Crowdly

Each of the recurrences below appears somewhere in this week's material. In a b...

Want instant access to all verified answers on learning.monash.edu?