动态规划法（DP）
2017-03-26 本文已影响25人
X_Sation
参考资料 http://blog.csdn.net/baidu_28312631/article/details/47418773
http://www.360doc.com/content/13/0601/00/8076359_289597587.shtml
1. 问题：
现在有1,3,5元硬币若干枚，使用最少的数量凑够11元
-
贪心算法
先选择最大的，两枚5元的，再选择3元的，不行，那就选择1元的，正好，总共用了3枚硬币。但是如果把面值改成了2，3，5，那用贪心算法就永远凑不齐了。
-
动态规划法
假设凑够i元需要j枚硬币，那么就有d(i)=j这样的公式，i是小于11的
假如i=4，硬币最大值5，不能用，那就用一个3，可以用，所以可以得出d(4)=1+d(4-3),由于我们是按照i从小到大的顺序算的，所以d(4-3)已经计算出来了，所以。。
| i | j |
|---|---|
| 0 | d(0)=0 * (表示凑0元需要0个硬币) * |
| 1 | d(1)=1+d(1-1)=1+0=1 * 表示凑1元需要1个硬币 * |
| 2 | d(2)=1+d(2-1)=1+1=2 |
| 3 | d(3)=Min(1+d(3-3),1+d(3-1))=1 |
| 4 | d(4)=Min(1+d(4-3),1+d(4-1))=2 |
| 5 | d(5)=Min(1+d(5-5),1+d(5-3),1+d(5-1))=1 |
| 6 | d(6)=Min(1+d(6-5),1+d(6-3),1+d(6-1))=2 |
| 7 | d(7)=Min(1+d(7-5),1+d(7-3),1+d(7-1))=3 |
| 8 | d(8)=Min(1+d(8-5),1+d(8-3),1+d(8-1))=2 |
| 9 | d(9)=Min(1+d(9-5),1+d(9-3),1+d(9-1))=3 |
| 10 | d(10)=Min(1+d(10-5),1+d(10-3),1+d(10-1))=2 |
| 11 | d(11)=Min(1+d(11-5),1+d(11-3),1+d(11-1))=3 |
2. 问题：
求从顶端到底端路线，经过的点的之和最大的路径，只能往左下，右下走
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
-
递归法
-
普通递归法：从最上面一行开始，下面一行它左面的和他右边的分别加上它，求最大值，然后开始递归，直到下一行没有（当前这行就是最后一行）
这样的话就是无脑递归，第二行的3开始往下计算，会分别计算8、1这三个分支，从第二行的8开始往下计算，会计算1、0两个分支，那么1这个分支就重复计算了，所以。。。
-
改进递归法：上面那种方法中，有东西重复计算了，所以我们可以把它记录下来
这样的话就是无脑递归，第二行的3开始往下计算，会分别计算8、1这三个分支，从第二行的8开始往下计算，会计算1、0两个分支，那么1这个分支就重复计算了，所以。。。
-
-
动态规划法
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
- 从最下面开始，首先记录4 5 2 6 5
- 倒数第二行，2和最后一行的4、5中求出一个最大的和，7和最后一行的5、2，4和最后一行的2、6，4和最后一行的6、5，最后记录下7 12 10 10
- 倒数第三行，同理，最后记录下20 13 10
- 倒数第四行，同理，最后记录下23 21
- 最上面一行，同理，最后记录下30
- 如此，得到了最后的答案。
3. 问题：
解题思路:动态规划求解，通常把原问题分成子问题，前一个子问题解决之后，答案保存下来，供下一个子问题去使用，以上两个问题都是遮阳解的，所以每个问题只需要解一次
