理解动态编程的好例子，文章和书籍 [英] Good examples, articles, books for understanding dynamic programming
问题描述
我无法弄清楚动态编程的原理，而我确实很想要它. DP非常强大，可以解决如下问题:
I can't figure out the principles of dynamic programming and I really do want it. DP is very powerful, it can solve problems like this:
那么，您能为我推荐好书或文章(最好是带有真实代码的示例)，这将解释我什么是动态编程吗?首先，我真的很想要简单的示例，然后继续.
So, can you suggest me good books or articles (preferably with examples with real code) which would explain me what is dynamic programming? I really want simple examples first of all, then I'll move on.
推荐答案
动态编程是有用的算法类型，可用于通过将较小的子问题分解为较小的子问题来优化这些问题.通过存储和重用部分解决方案，它可以避免使用贪婪算法带来的陷阱.动态编程有两种，自底向上和自顶向下.
Dynamic programming is a useful type of algorithm that can be used to optimize hard problems by breaking them up into smaller subproblems. By storing and re-using partial solutions, it manages to avoid the pitfalls of using a greedy algorithm. There are two kinds of dynamic programming, bottom-up and top-down.
为了使用动态编程可解决问题，该问题必须具有所谓的最佳子结构.这意味着，如果将问题分解为一系列子问题，并且找到了每个子问题的最佳解决方案，那么将通过对这些子问题的解决方案来实现最终的解决方案.动态编程无法解决没有这种结构的问题.
In order for a problem to be solvable using dynamic programming, the problem must possess the property of what is called an optimal substructure. This means that, if the problem was broken up into a series of subproblems and the optimal solution for each subproblem was found, then the resulting solution would be realized through the solution to these subproblems. A problem that does not have this structure cannot be solved with dynamic programming.
自上而下的俗称为记忆力.这是为了存储过去的计算以避免每次都重新计算它们的想法.
Top-down is better known as memoization. It is the idea of storing past calculations in order to avoid re-calculating them each time.
给出一个递归函数，说:
Given a recursive function, say:
fib(n) = 0 if n = 0
1 if n = 1
fib(n - 1) + fib(n - 2) if n >= 2
我们可以很容易地以其数学形式将其写为:
We can easily write this recursively from its mathematic form as:
function fib(n)
if(n == 0 || n == 1)
n
else
fib(n-1) + fib(n-2)
现在，任何已经进行了一段时间编程或对算法效率了解一两件事的人都会告诉你，这是一个糟糕的主意.原因是，在每个步骤中，您都必须重新计算fib(i)的值，其中i为2..n-2.
Now, anyone that has been programming for awhile or knows a thing or two about algorithmic efficiency will tell you that this is a terrible idea. The reason is that, at each step, you must to re-calculate the value of fib(i), where i is 2..n-2.
一个更有效的示例是存储这些值，创建自顶向下的动态编程算法.
A more efficient example of this is storing these values, creating a top-down dynamic programming algorithm.
m = map(int, int)
m[0] = 0
m[1] = 1
function fib(n)
if(m[n] does not exist)
m[n] = fib(n-1) + fib(n-2)
这样做，我们最多只能计算一次fib(i).
By doing this, we calculate fib(i) at most once.
自下而上使用与自上而下相同的记忆技术.但是，不同之处在于，自下而上使用了比较子问题，即重复问题，以优化最终结果.
Bottom-up uses the same technique of memoization that is used in top-down. The difference, however, is that bottom-up uses comparative sub-problems known as recurrences to optimize your final result.
在大多数自下而上的动态编程问题中，您经常尝试最小化或最大化决策.在任何给定的点上，您都有两个(或更多)选项，您必须确定哪种方法最适合您要解决的问题.但是，这些决定是基于您之前做出的选择.
In most bottom-up dynamic programming problems, you are often trying to either minimize or maximize a decision. You are given two (or more) options at any given point and you have to decide which is more optimal for the problem you're trying to solve. These decisions, however, are based on previous choices you made.
通过在每个点(每个子问题)上做出最佳决策，可以确保总体结果是最佳的.
By making the most optimal decision at each point (each subproblem), you are making sure that your overall result is the most optimal.
这些问题中最困难的部分是找到重复关系以解决您的问题.
The most difficult part of these problems is finding the recurrence relationships for solving your problem.
要支付一堆算法教科书的费用，您打算抢劫一家有 n 个商品的商店.问题是您的小背包最多只能容纳 W 千克.知道了每件商品的重量(w [i])和价值(v [i])后，您想使被盗商品的总价值最大为W的商品价值最大化.对于每件商品，您都必须做出二元选择-接受或离开它.
To pay for a bunch of algorithm textbooks, you plan to rob a store that has n items. The problem is that your tiny knapsack can only hold at most W kg. Knowing the weight (w[i]) and value (v[i]) of each item, you want to maximize the value of your stolen goods that all together weight at most W. For each item, you must make a binary choice - take it or leave it.
现在，您需要找到子问题.作为一个非常聪明的小偷，您意识到给定项目i的最大值，即最大权重w，可以表示为m [i，w].另外，m [0，w](最多0个重量w项)和m [i，0](最大i重量0个项)将始终等于0值.
Now, you need to find what the subproblem is. Being a very bright thief, you realize that the maximum value of a given item, i, with a maximum weight, w, can be represented m[i, w]. In addition, m[0, w] (0 items at most weight w) and m[i, 0] (i items with 0 max weight) will always be equal to 0 value.
所以
m[i, w] = 0 if i = 0 or w = 0
戴上思考型全面罩，您会发现，如果您已尽可轻便地将行李装满包，除非重量小于或等于您与您之间的差值，否则将不考虑新商品最大重量和当前袋子的重量.您可能要考虑的另一种情况是，它的重量是否小于或等于袋子中某个物品的重量，但价值更高.
With your thinking full-face mask on, you notice that if you have filled your bag with as much weight as you can, a new item can't be considered unless its weight is less than or equal to the difference between your max weight and the current weight of the bag. Another case where you might want to consider an item is if it has less than or equal weight of an item in the bag but more value.
m[i, w] = 0 if i = 0 or w = 0
m[i - 1, w] if w[i] > w
max(m[i - 1, w], m[i - 1, w - w[i]] + v[i]) if w[i] <= w
这些是上述重复关系.一旦有了这些关系，编写算法就非常容易(而且很短！).
These are the recurrence relations described above. Once you have these relations, writing the algorithm is very easy (and short!).
v = values from item1..itemn
w = weights from item1..itemn
n = number of items
W = maximum weight of knapsack
m[n, n] = array(int, int)
function knapsack
for w=0..W
m[0, w] = 0
for i=1 to n
m[i, 0] = 0
for w=1..W
if w[i] <= w
if v[i] + m[i-1, w - w[i]] > m[i-1, w]
m[i, w] = v[i] + m[i-1, w - w[i]]
else
m[i, w] = m[i-1, w]
else
m[i, w] = c[i-1, w]
return m[n, n]
其他资源
- Introduction to Algorithms
- Programming Challenges
- Algorithm Design Manual
示例问题
幸运的是，当涉及到竞争性编程时，动态编程已真正成为了 .查看基于UVAJudge的动态编程这些问题将测试您对动态编程问题的实现和发现重复发生的能力.
Example Problems
Luckily, dynamic programming has become really in when it comes to competitive programming. Check out Dynamic Programming on UVAJudge for some practice problems that will test your ability to implement and find recurrences for dynamic programming problems.
这篇关于理解动态编程的好例子，文章和书籍的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
