3 ms·
What do you mean by "the DP state"? Also, I think my previous formula is wrong. Maybe it is the sum of: (m - i + 1)*(n - j + 1)*U(i, j) With i, j in [1..m]
by marcodiego 5y ago
What do you mean by "the DP state"?
Also, I think my previous formula is wrong. Maybe it is the sum of:
(m - i + 1)*(n - j + 1)*U(i, j)
With i, j in [1..m].
But maybe it is still wrong because U(i, j) will re-count combinations from U(i - 1, j) and U(i, j - 1)...
Argh! This is complicated! I think I'll have to revisit it if I ever have a good idea.
- tylerhou 5y agoBy DP state, I mean the arguments to the recursive function (for U, the state is the tuple (i, j)). For example, if you wanted to use DP to compute all-pairs-shortest-paths (Floyd-Warshall), you add a third parameter to the DP state ((f(u, v, k)).
- marcodiego 5y agoSure! Dynamic programming, right?