What do you mean by "the DP state"? Also, I think my previous formula is wrong. ... | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		marcodiego on Nov 14, 2021 \| parent \| context \| favorite \| on: Project Euler 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 on Nov 14, 2021 [–]

By 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 on Nov 14, 2021 | [–]

Sure! Dynamic programming, right?

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact