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

> 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…



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.


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)).


Sure! Dynamic programming, right?




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

Search: