什么是动态规划？ [英] What is dynamic programming?

问题描述

什么是动态规划？

如何是从递归，memoization的，等有什么不同？

How's it different from recursion, memoization, etc?

我读过就可以了维基百科文章，但我还是不真正了解它。

I've read the wikipedia article on it, but I still don't really understand it.

推荐答案

当你用过去的知识，使解决未来的问题，更容易动态编程。

Dynamic programming is when you use past knowledge to make solving a future problem easier.

一个很好的例子是解决斐波那契序列N = 1000002。

A good example is solving the fibonacci sequence for n=1,000,002.

这将是一个非常漫长的过程，但如果我给你的结果N = 1,000,000，N = 1,000,0001？突然，问题只是变得更易于管理。

This will be a very long process, but what if I give you the results for n=1,000,000 and n=1,000,0001? Suddenly the problem just became more manageable.

动态编程中使用的很多串问题，如串编辑问题。你解决问题的一个子集（多个），然后使用该信息来解决更加困难原问题

Dynamic programming is used a lot in string problems, such as the string edit problem. You solve a subset(s) of the problem and then use that information to solve the more difficult original problem.

使用动态编程，存储您的结果某种表一般。当你需要回答一个问题，你参考下表，看看你已经知道它是什么。如果没有，你可以使用表中的数据，给自己对答案的敲门砖。

With dynamic programming, you store your results in some sort of table generally. When you need the answer to a problem, you reference the table and see if you already know what it is. If not, you use the data in your table to give yourself a stepping stone towards the answer.

在Cormen算法书中有关于动态规划一个伟大的篇章。而且它是免费的谷歌图书！检查出来<一个href="http://books.google.com/books?id=NLngYyWFl_YC&dq=cormen+algorithms&printsec=frontcover&source=bn&hl=en&ei=K2xKSrCbGIbyMYqO_LMC&sa=X&oi=book_result&ct=result&resnum=4">here.

The Cormen Algorithms book has a great chapter about dynamic programming. AND it's free on Google Books! Check it out here.

这篇关于什么是动态规划？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！