Last updated on 2019-10-11…
动态规划求解的一般思路：
- 判断问题的子结构，当具有最优子结构时，动态规划可能适用。
- 求解重叠子问题。一个递归算法不断地调用同一问题，递归可以转化为查表从而利用子问题的解。（分治法则不同，每次递归都产生新的问题。）
- 重新构造一个最优解。
01背包问题
有 n 个重量个价值分别为 w<sub>i</sub>, v<sub>i</sub>的物品。
从这些物品中选出总重量不超过 W 的物品，使其总价值最大。
示例
1 // 用例数T
5 10 // 物品数N 背包容量V
1 2 3 4 5 // 价值v[i]
5 4 3 2 1 // 重量w[i]
14 // 输出最大的总价值
二维 DP（无优化）
定义：dp[i][j] = 从前 i 个物品中选取总重量不超过 j 的物品时总价值的最大值（i 从 1 开始计，包括第 i 个物品）。
int solve(int N, int V, vector<int>& v, vector<int>& w) {
vector<vector<int> > dp(N + 1, vector<int>(V + 1, 0)); // 不要求装满，初始化为 0 即可
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) { // 可能存在重量为 0，但有价值的物品
if (w[i] > j) // 如果当前物品的重量大于剩余容量
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); //不拿第 i 个物品和要拿第 i 个物品取max
}
}
return dp[N][V];
}
二维 DP（滚动数组）
在上述递推式中，dp[i+1] 的计算实际只用到了 dp[i+1] 和 dp[i]；因此可以结合奇偶，通过两个数组滚动使用来实现重复利用。
int solve(int N, int V, vector<int>& v, vector<int>& w) {
vector<vector<int> > dp(2, vector<int>(V + 1, 0)); // N+1 -> 2
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) { // 可能存在重量为 0，但有价值的物品
if (w[i] > j) // 如果当前物品的重量大于剩余容量
dp[i & 1][j] = dp[(i - 1) & 1][j];
else
dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[(i - 1) & 1][j - w[i]] + v[i]); //不拿第 i 个物品和要拿第 i 个物品取max
}
}
return dp[N & 1][V]; // 这里别忘了 N & 1
}
一维 DP
定义：dp[j] := 重量不超过 j 公斤的最大价值。
int solve(int N, int V, vector<int>& v, vector<int>& w) {
vector<int> dp(V + 1, 0);
for (int i = 1; i <= N; i++) {
for (int j = V; j >= w[i]; j--) { // 递推方向发生了改变
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
return dp[V];
}
完全背包
01 背包中每个物品只有一个，所以只存在选或不选；完全背包中每个物品可以选取任意件。
注意：本题要求是背包恰好装满背包时，求出最大价值总和是多少。如果不能恰好装满背包，输出 NO。
二维 DP（无优化）
直观思路：在 01 背包的基础上在加一层循环。
void solve() {
const int inf = 0x80000000;
int T;
scanf("%d", &T);
while (T--) {
int N, V; // N 表示物品种类的数目，V 表示背包的总容量
scanf("%d%d", &N, &V);
vector<int> w(N + 1), v(N + 1); // w 表示重量，v 表示价值
for (int i = 1; i <= N; i++)
scanf("%d%d", &w[i], &v[i]);
vector<vector<int> > dp(N + 1, vector<int>(V + 1, inf));
for (int i = 0; i <= N; i++)
dp[i][0] = 0;
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j < w[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i]);
}
}
if (dp[N][V] > 0)
printf("%d\n", dp[N][V]);
else
puts("NO");
}
}
二维 DP（滚动数组）
void solve() {
const int MAX_V = 50000 + 10;
const int inf = 0x3f3f3f3f;
int T;
scanf("%d", &T);
while (T--) {
int N, V; // M 表示物品种类的数目，V 表示背包的总容量
scanf("%d%d", &N, &V);
int dp[2][MAX_V];
for (int i = 0; i < 2; i++) {
fill(dp[i], dp[i] + MAX_V, -inf);
dp[i][0] = 0;
}
for (int i = 1; i <= N; i++) {
int w, v;
scanf("%d%d", &w, &v);
for (int j = 0; j <= V; j++) {
if (j < w)
dp[i & 1][j] = dp[(i - 1) & 1][j];
else
dp[i & 1][j] = max(dp[(i - 1) & 1][j], dp[i & 1][j - w] + v);
}
}
if (dp[N][V] > 0)
printf("%d\n", dp[N & 1][V]);
else
puts("NO");
}
}
一维 DP
核心代码与 01 背包一致，只有第二层循环的递推方向不同。
void solve() {
const int MAX_V = 50000 + 10;
const int inf = 0x80000000;
int T;
scanf("%d", &T);
while (T--) {
int N, V; // M 表示物品种类的数目，V 表示背包的总容量
scanf("%d%d", &N, &V);
int dp[MAX_V];
fill(dp, dp + MAX_V, inf);
dp[0] = 0;
for (int i = 1; i <= N; i++) {
int w, v;
scanf("%d%d", &w, &v); // 避免开辟新的内存
for (int j = w; j <= V; j++) {
dp[j] = max(dp[j], dp[j - w] + v);
}
}
if (dp[V] > 0)
printf("%d\n", dp[V]);
else
puts("NO");
}
}
买卖股票的最佳时机
买卖股票 I
题目：假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
样例：给出一个数组样例 [3,2,3,1,2], 返回 1
思路：用cur存最小，tmp存差值最大
int maxProfit(vector<int> &prices) {
if(prices.size() == 0) //时刻注意数组越界
return 0;
int max = 0;
int cur = prices[0];
for(int i = 0; i < prices.size(); ++i){
if(prices[i] < cur){ //卖掉会亏
cur = prices[i];
}else{ //卖掉能挣
int tmp = prices[i] - cur;
if(tmp > max)
max = tmp;
}
}
return max;
}
买卖股票 II
题目：假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
样例：给出一个数组样例[2,1,2,0,1], 返回 2
思路：由于买卖次数无限，所以只要能获利就进行买卖，这样能保证所有利润都吃到自然利润最大。
int maxProfit(vector<int> &prices) {
int i, d;
int max = 0;
for(i = 1; i < prices.size(); ++i){ //只要有钱赚就买卖
d = prices[i] - prices[i - 1];
if(d > 0){
max += d;
}
}
return max;
}
买卖股票 III、IV
未完待续…
