algorithm - 没有动态规划的算法，求解效率低

Question

比赛中问了一个问题。我已经用动态编程及其复杂性解决了这个问题O(n^2)。但我正在寻找效率较低的解决方案。这种效率较低的方法的复杂性是什么。感谢您的帮助。

Answer 1

有一种通用方法可以降低任何动态编程解决方案的效率。动态规划的本质是存储子问题的解决方案以供重用。

为了以某种合理的方式降低效率，请摆脱子问题结果存储。相反，在需要时重新计算每个子问题的解决方案。

Answer 2

使用具有相同算法的低效数据结构有助于实现O(n^3). 将城镇存储在链表而不是数组中会使算法效率降低一级。

为了使其效率更低，更改算法更容易。例如检查所有预兆变化的组合并使用最小的，它是时间指数的。