题目描述：
1.一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
2.一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
3.目前市面上的纸币主要有1元，5元，10元，20元，50元、100元六种，如果要买一件商品x元，有多少种货币组成方式？
问法不一样，但是本质一样！
解析：
这些都属于动态规划解法
第一题用Fibonacci的F(n)=F(n-1) + F(n-2) ，比较简单。
第二题、F(n)=F(n-1) + F(n-2) +…+F(n-k)=2F(n-1)。
第三题，属于完全背包问题：
状态转移方程1：
定义F[i][sum] = 用前i种硬币构成sum的所有组合数。
F[i][sum]=F[i−1][sum−0∗Vm]+F[i−1][sum−1∗Vm]+F[i−1][sum−2∗Vm]+…+F[i−1][sum−K∗Vm]F[i][sum] = F[i-1][sum - 0*V_m] + F[i-1][sum - 1*V_m] + F[i-1][sum - 2*V_m] + … + F[i-1][sum - K*V_m]F[i][sum]=F[i−1][sum−0∗Vm]+F[i−1][sum−1∗Vm]+F[i−1][sum−2∗Vm]+…+F[i−1][sum−K∗Vm] ，其中m=i-1, k=sum/V_m。
如果我们用二位数组表示F[i][sum], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。
状态转移方程2：
和跳台阶一样，发现这种方式更简单容易理解
F[sum] = F[sum-1] + F[sum-5] + …+F[sum-100]
实现：
#include <vector>#include <iostream>using namespace std;class Solution {public:// 动态规划1：// F[i][sum] = 用前i种硬币构成sum的所有组合数。// 状态转移方程：// F[i][sum] = F[i-1][sum - 0*Vm] + F[i-1][sum - 1*Vm] + F[i-1][sum - 2*Vm] + … + F[i-1][sum - K*Vm]// 其中m=i-1, k=sum/Vmint solution1(vector<int> array, int sum) {int n = array.size();// F[i][j]表示用硬币的前i个可以凑成金额j的个数// 定义二维数组vector<vector<int> > F(n+1, vector<int>(sum+1,0));// 初始条件,如果sum=0，那么无论有前多少种来组合0，只有一种可能for(int i = 0; i <= n; i++){F[i][0] = 1;}for (int i = 1; i <= n; i++) {for (int j = 1; j <= sum; j++) {// j / coins[i-1]表示能取的该硬币的最大数量。for (int k = 0; k <= j / array[i-1]; k++){F[i][j] += F[i-1][j - k * array[i-1]];}}}return F[n][sum];}// 动态规划2：int solution1(vector<int> array, int sum) {int n = array.size();// F[x]表示凑成金额x的组合个数// 定义二维数组int F[sum];F[0]=1;for(int i = 0; i < n; i++){for(int x = array[i]; x < sum; x++){F(x) += F[x - array[i]];}}return F(sum-1);}// 暴力搜索int solution3(vector<int> array, int sum) {int num = 0;if (sum < 1) {return num;}for (int i = 0; i <= sum / array[0]; i++)for (int j = 0; j <= sum / array[1]; j++)for (int k = 0; k <= sum / array[2]; k++)for (int l = 0; l <= sum / array[3]; l++)for (int m = 0; m <= sum / array[4]; m++)for (int h = 0; h <= sum / array[5]; h++) {if (sum == i + 5 * j + 10 * k + 20 * l + 50 * m + 100 * h) {num++;}}return num;}};int main() {vector<int> array = {1, 5, 10, 20, 50, 100};Solution s;cout << s.solution1(array, 200) << endl;}
01背包问题
有NNN件物品和一个容量为VVV的背包，放入第iii件物品的费用是CiC_iCi，得到的价值是WiW_iWi。求解将哪些物品装入背包可使价值总和最大。
状态转移方程F[i,v]=maxF[i−1,v],Wi+F[i−1,v−Ci]F[i,v]=max{F[i-1,v],W_i+F[i-1,v-C_i]}F[i,v]=maxF[i−1,v],Wi+F[i−1,v−Ci]
Reference:
/p/a66d5ce49df5
