题目描述：
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
]
[
s
u
m
]
=
F
[
i
−
1
]
[
s
u
m
−
0
∗
V
m
]
+
F
[
i
−
1
]
[
s
u
m
−
1
∗
V
m
]
+
F
[
i
−
1
]
[
s
u
m
−
2
∗
V
m
]
+
…
+
F
[
i
−
1
]
[
s
u
m
−
K
∗
V
m
]
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
]
[
s
u
m
]
=
F
[
i
−
1
]
[
s
u
m
−
0
∗
V
m
]
+
F
[
i
−
1
]
[
s
u
m
−
1
∗
V
m
]
+
F
[
i
−
1
]
[
s
u
m
−
2
∗
V
m
]
+
…
+
F
[
i
−
1
]
[
s
u
m
−
K
∗
V
m
]
，其中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/Vm
int 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背包问题
有
N
N
N
件物品和一个容量为
V
V
V
的背包，放入第
i
i
i
件物品的费用是
C
i
C_i
C
i
，得到的价值是
W
i
W_i
W
i
。求解将哪些物品装入背包可使价值总和最大。
状态转移方程
F
[
i
,
v
]
=
m
a
x
F
[
i
−
1
,
v
]
,
W
i
+
F
[
i
−
1
,
v
−
C
i
]
F[i,v]=max{F[i-1,v],W_i+F[i-1,v-C_i]}
F
[
i
,
v
]
=
m
a
x
F
[
i
−
1
,
v
]
,
W
i
+
F
[
i
−
1
,
v
−
C
i
]
Reference:
https://www.jianshu.com/p/a66d5ce49df5