Algorithmic Mutterings

Can You Solve Dynamic Programming Problems Faster? Part 1, One-Dimensional LWS

We prove you can solve dynamic programming problems polynomially faster if you have a simple cost function for kD LWS problems.

22 min read   ·   January 9, 2024

2024   ·   comments     ·   explain-paper   dynamic-programming   cs-theory   algorithms   complexity