比赛中有个问题。我已经用动态编程解决了这个问题，它的复杂性O(n^2)。但我正在寻找一种效率较低的解决方法。这种不太有效的方式将会是什么样的复杂性。谢谢你的帮助。
最佳答案
有一种通用的方法可以降低任何动态规划解决方案的效率。动态编程的本质是存储子问题的解决方案以供重用。
为了使其效率降低一些合理的方式，摆脱子问题的结果存储。相反，只要需要，就重新计算每个子问题的解决方案。
比赛中有个问题。我已经用动态编程解决了这个问题，它的复杂性O(n^2)。但我正在寻找一种效率较低的解决方法。这种不太有效的方式将会是什么样的复杂性。谢谢你的帮助。
最佳答案
有一种通用的方法可以降低任何动态规划解决方案的效率。动态编程的本质是存储子问题的解决方案以供重用。
为了使其效率降低一些合理的方式，摆脱子问题的结果存储。相反，只要需要，就重新计算每个子问题的解决方案。