参考资料 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

1. 从最下面开始，首先记录4 5 2 6 5
2. 倒数第二行，2和最后一行的4、5中求出一个最大的和，7和最后一行的5、2，4和最后一行的2、6，4和最后一行的6、5，最后记录下7 12 10 10
3. 倒数第三行，同理，最后记录下20 13 10
4. 倒数第四行，同理，最后记录下23 21
5. 最上面一行，同理，最后记录下30
6. 如此，得到了最后的答案。

3. 问题：

解题思路:动态规划求解，通常把原问题分成子问题，前一个子问题解决之后，答案保存下来，供下一个子问题去使用，以上两个问题都是遮阳解的，所以每个问题只需要解一次