3 ms·
> If we can find X Almost certainly we need to add terms into the DP state to compute X; unfortunately adding just the number of vertices doesn’t work as some
by tylerhou 5y ago
> If we can find X
Almost certainly we need to add terms into the DP state to compute X; unfortunately adding just the number of vertices doesn’t work as some triangles have two edges in which a point can be inserted to create a quadrilateral, while others only have one.
The difficulty is finding those terms, though…
- marcodiego 5y agoWhat 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?