比赛中有一个问题。我已经用动态规划及其复杂度O(n^2)解决了这个问题。但我正在寻找解决方案与效率较低的方式。这种效率较低的方法有多复杂。谢谢你的帮助。
有一种通用的方法可以降低任何动态规划解决方案的效率。动态规划的本质是存储子问题的解决方案以供重用。
为了以某种合理的方式降低效率，可以去掉子问题结果存储。相反，在需要时重新计算每个子问题的解决方案。
使用相同算法的低效数据结构可以帮助获得O(n^3)。将城镇存储在链表中而不是数组中会使算法效率降低一级。
为了使其效率更低，更容易更改算法。例如，检查所有的前兆变化组合和使用最小值，这是在时间上的指数。