如何判断动态规划的答案是否是最优答案？
除了确定动态规划的问题答案是否是最优答案之外，我还应该使用什么样的算法？ 你能推荐一些论文来帮助我找出答案吗？
what sort of algorithm should I use beside to find out whether dynamic programming's answer to the problem is the optimal answer or not?
could you suggest some papers to help me find out that?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
解决问题的动态规划方法通常会得到正确的答案 - 即找到真正的最小成本答案 - 但通常不能保证是使用最少的 CPU 或内存来解决问题的方法。
在很多情况下，我们不知道解决问题的方法是否使用尽可能少的 cpu。一个例子是 http://en.wikipedia.org/wiki/Knapsack_problem。
The dynamic programming approach to a problem will usually get the correct answer - i.e. find the true minimum cost answer - but it is not usually guaranteed to be the way of solving the problem that uses the minimum amount of cpu or memory.
There are many cases where we do not know if our method of solving a problem uses the minimum possible amount of cpu. One example, where dynamic program is one of the more efficient methods known, but is not proved to be the most efficient possible method is http://en.wikipedia.org/wiki/Knapsack_problem.
没有算法可以告诉您给定的动态规划解决方案是否是最优的。
有关密切相关问题的研究，请参阅停止问题。
There is no algorithm that tells you whether a given dynamic programming solution is optimal.
See the Halting Problem for research on a closely related question.
如果您的问题的意思是：“我如何确定我的动态编程是否正确实现？”您也可以通过回溯来解决问题，回溯很容易实现，并且总是给出最佳解决方案。您可以对相同的小数据输入尝试回溯和动态编程，如果输出相同，那么您可以强烈怀疑动态编程实现是正确的。
否则，动态规划总是给出最优答案，但并不是所有问题都可以通过 DP 解决，当然也不是所有 DP 程序都可以使用相同的状态和/或递归来解决。
If by your question you are meaning: "How do I find if my Dynamic programming is correctly implemented?" You can solve the problem also by backtracking wich is simple to implement and always gives the best solution. You can try both backtracking and dynamic programming for the same small data inputs and if the outputs are identical then you can strongly suspect that you dynamic programming implementation is correct.
Otherwise dynamic programming always gives the optimal answer, but not all problems ca be solved by DP and of course not all DP progrems can be solved using the same state and/or recurence.