1.动态规划

1.1 思路：

先看经典例题01背包

（1）问题描述：

给定 n 件物品，物品的重量为 w[i]，物品的价值为 v[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 V，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？
​
物品编号：1 2 3 4 5
​
w[i]         ：2 3 5 6 8
​
v[i]         ：4 5 8 3 6

 

假设现有背包重量14，如何装才能得到最大价值？

（2）动态规划的思路：

把从0到14的每一个重量能装到的最大价值（最优解）存在一个数组dp[ ]中，这样求dp[8]，就可以从前面的dp中找到再相加即可，直到找到14。这样做避免了会找到不是最优解的数。

I	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
dp	0	0	4	5	8	9	12	13	16	17	20	...
	0	0	本	本	2+2	2+3	2+4	2+5	4+4	4+5	2+8

经典例题2

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
​
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

1.2 思路框架

1. 定义一个存储最优解的dp[]数组。

2. for循环1：从0到n 求最优解。

3. for循环2：从0到size()求0到n的每个解。

4. 更新每个最优解。

5. 返回dp[amount]。

1.3 代码框架

  //初始化dp数组
    // int* dp = (int*)malloc(sizeof(int)*(amount+1))
    int dp[amount+1];
    for(int i=0;i<amount+1;i++)
      dp[i]=-1;
    dp[0] = 0;
    for(int i=1;i<=amount;i++){
        for(int j=0;j<coins.size();j++){
            //如果当前面值coins[j]比i小，并且i-coins[j]有最优解
            if(coins[j]<i&&dp[i-coins[j]]!=-1){
                //如果dp[i]还未算最优解，或者dp[i]当前最优解比正在算的大，则更新
                if(dp[i]==-1 || dp[i]>dp[i-coins[j]]+1){
                    dp[i] = dp[i-coins[j]]+1;
                }
            }
        }
    }
    return dp[amount];