最优子结构
重叠子问题
无后效性
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T83
题目大意：
有一个箱子容量为 V（正整数，0 ＜＝ V ＜＝ 20000），同时有 n 个物品（0 ＜ n ＜＝ 30），每个物品有一个体积（正整数）。
要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
解题思路：
最经典的 $dp$ 问题，直接上手
题解：
#include
#include
using namespace std;
const int maxn = 20010;
//dp[j]：当体积为j时，最大填充为dp[j]
int dp[maxn], w[35];
int main(){
// freopen("input.txt", "r", stdin);
int v, n;
cin >> v >> n;
for(int i = 0;i < n;i++){
cin >> w[i];
}
//n个物品
for(int i = 0;i < n;i++){
//总体积为v
for(int j = v;j >= w[i];j--){
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
}
}
printf("%d\n", v - dp[v]);
return 0;
}
/*
24
6
8
3
12
7
9
7
0
*/
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T93
题目大意：
在不超过 $N$ 元（可以等于 $N$ 元）的前提 下，使每件物品的价格与重要度的乘积的总和最大。
解题思路：
约定，$dp[i][j]$ 表示判定了 $i$ 件物品，剩余钱数为 $j$ 时，每件物品的价格与重要度的乘积的总和最大。
典型的 $0/1$ 背包问题
$dp$ 方程：
$$
dp[i][j] = max( dp[i - 1][j], ,dp[i - 1][j - v] + v * p)
$$
其中，$v$ 表示物品的价格，$p$ 表示该物品的重要度。
题解：
#include
#include
using namespace std;
const int maxn = 30005;
//dp[i][j]表示判定了i件物品，剩余钱数为j时，每件物品的价格与重要度的乘积的总和最大
int dp[30][maxn] = {0};
int main(){
int n, m;
cin >> n >> m;
//物品件数
for(int i = 1;i <= m;i++){ int v, p; cin>> v >> p;
//总钱数
for(int j = 1;j <= n;j++){ if(j>= v){
dp[i][j] = max( dp[i - 1][j], dp[i - 1][j - v] + v * p);
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
printf("%d\n", dp[m][n]);
return 0;
}
/*
1000 5
800 2
400 5
300 5
400 3
200 2
3900
*/
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T84
题目大意：
将整数 n 分成 k 份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如：n = 7，k = 3，下面三种分法被认为是相同的。
1，1，5; 1，5，1; 5，1，1;
问有多少种不同的分法。
解题思路：
考虑四种情况：
题解：
#include
#include
using namespace std;
int dfs(int n, int k){
if(n == k || k == 1){
return 1;
}
if(n < k){
return 0;
}
//至少存在一个1的情况：总数 - 1， 个数 - 1
//一定不存在1的情况： k个数均≥2，则每个数都 - 1，总数 - k * 1，个数不变
return dfs(n - 1, k - 1) + dfs(n - k, k);
}
int main(){
int n, k;
cin >> n >> k;
printf("%d\n", dfs(n, k));
return 0;
}
/*
7 3
4
*/
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T44
题目大意：
如果一个序列满足下面的性质，我们就将它称为摆动序列：
- 序列中的所有数都是不大于k的正整数；
- 序列中至少有两个数；
- 序列中的数两两不相等；
- 如果第 i – 1 个数比第 i – 2 个数大，则第 i 个数比第 i – 2 个数小；如果第 i – 1 个数比第 i – 2 个数小，则第 i 个数比第 i – 2 个数大。
比如，当 k = 3 时，有下面几个这样的序列：
1 2 1 3 2 1 2 1 3 2 3 2 3 1 3 1 3 2一共有 8 种，给定 k ，请求出满足上面要求的序列的个数。
解题思路：
题解：
#include
#include
#include
using namespace std;
const int maxn = 30;
int arr[maxn], vis[maxn];
int ans = 0, n;
void dfs(int x){
if(x > 1){
if(x == 2){
ans++;
//公式满足条件3与条件4
}else if( (arr[x - 2] - arr[x - 3]) * (arr[x - 1] - arr[x - 3]) < 0){
ans++;
}else{
return;
}
}
for(int i = 1;i <= n;i++){ if(!vis[i]){ vis[i]="1;" arr[x]="i;" dfs(x + 1); } int main(){ memset(vis, 0, sizeof(vis)); cin>> n;
dfs(0);
printf("%d", ans);
return 0;
}
/*
3
8
*/
题目链接：http://lx.lanqiao.cn/problem.page?gpid=T97
题目大意：
有 $n$ 个同学围成一圈，小蛮传了 $m$ 次球后，球又回到自己手中，问有多少种传球方法？
解题思路：
约定，$dp[i][j]$ 表示传了 $i$ 次球，到第 $j$ 个人手上的传球方法。
题解：
#include
#include
using namespace std;
const int maxn = 40;
//dp[i][j]表示传了i次球，到第j个人的次数
int dp[maxn][maxn] = {0};
int main(){
int n, m;
cin >> n >> m;
//传了0次球，到第一个人的次数，自然为1
dp[0][1] = 1;
for(int i = 1;i <= 2 3 m;i++){ for(int j="1;j" <="n;j++){" int x="j" - 1, y="j" + 1; 考虑第1个人的情况 if(j="=" 1){ } 考虑第n个人的情况 n){ 当前的情况等于左右传了i 1次球的情况相加 dp[i][j]="dp[i" 1][x] dp[i 1][y]; printf("%d\n", dp[m][1]); return 0; * 题目链接：http://lx.lanqiao.cn/problem.page?gpid=T79
题目大意：
设有 N * N 的方格图(N <= 10)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 0。
某人从图的左上角的 A 点(1, 1)出发，可以向下行走，也可以向右走，直到到达右下角的 B 点(N, N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0 ）。
此人从 A 点到 B 点共走两次，试找出 2 条这样的路径，使得取得的数之和为最大。
解题思路：
$$
dp[x1][y1 - 1][x2][y2 - 1],
$$
$$
dp[x1 - 1][y1][x2][y2 - 1],
$$
$$
dp[x1][y1 - 1][x2 - 1][y2])
$$
题解：
/*
模拟两个人同时从(1,1)走到(N,N)，
转移方程:dp[x1][x2][y1][y2] = max(dp[x1 - 1][y1][x2 - 1][y2],
dp[x1][y1 - 1][x2][y2 - 1],
dp[x1 - 1][y1][x2][y2 - 1],
dp[x1][y1 - 1][x2 - 1][y2])
考虑两人走到同一点的特殊情况，只能加一次权值。
*/
#include
#include
using namespace std;
const int maxn = 20;
int g[maxn][maxn] = {0}, dp[maxn][maxn][maxn][maxn] = {0};
int main() {
// freopen("input.txt", "r", stdin);
int n;
cin >> n;
while(true){
int x, y, value;
cin >> x >> y >> value;
if(x == 0 && y == 0 && value == 0){
break;
}
g[x][y] = value;
}
for(int x1 = 1;x1 <= 0 2 3 4 5 6 7 8 13 14 15 21 67 n;x1++){ for(int y1="1;y1" <="n;y1++){" x2="1;x2" y2="1;y2" int temp="max(dp[x1" - 1][y1][x2 1][y2], dp[x1][y1 1][x2][y2 1]); dp[x1 1][y1][x2][y2 1][x2 1][y2]); if(x1="=" && y2){ dp[x1][y1][x2][y2]="temp" + g[x1][y1]; }else{ g[x1][y1] g[x2][y2]; } printf("%d\n", dp[n][n][n][n]); return 0; * 题目链接：http://lx.lanqiao.cn/problem.page?gpid=T13
题目大意：
$K$ 好数定义：一个自然数 $N$ 的 $K$进制表示中任意的相邻的两位都不是相邻的数字。求 $L$ 位 $K$ 进制数中 $K$ 好数的数目。输出它对 $1000000007$ 取模后的值。
解题思路：
我们约定，$dp[i][j]$ 表示长度为 $i$ ，以 $j$ 开头的 $K$ 好数个数。
$K$ 好数中除开头外，每位数的取值为：$0 \sim K-1$；
以 $K=3，L=3$ 为例：
$$ans = dp[3][0]+dp[3][1]+dp[3][2]$$
其中 $dp[3][0]=dp[2][0]+dp[2][2]$
$dp[3][1]=dp[2][1]$
$dp[3][2]=dp[2][2]+dp[2][0]$
以此类推长度为 $2$ ，长度为 $1$ 的情况；
因此可推出 $dp$ 方程：
$$dp[i][j]=dp[i][j]+dp[i-1][x]$$
其中 $x$ 取值为 $0 \sim K-1$
另外要注意，$K$ 好数开头不能为 $0$ ；
题解：
#include
#include
using namespace std;
#define MOD 1000000007
const int maxn = 105;
//dp[i][j]表示长度为i，以j开头的K好数个数
int dp[maxn][maxn];
int main(){
int k, l;
cin >> k >> l;
//dp[1][i]表示长度为1，以i开头的K好数个数，此时个数均为 1
for(int i = 0;i < k;i++){
dp[1][i] = 1;
}
//长度由2 → l
for(int i = 2;i <= 1 2 4 7 l;i++){ 表示以j开头的个数，因为是k进制，所以k的范围为0 ~ k - for(int j="0;j" < k;j++){ 枚举以j为开头时的所有情况 x="0;x" k;x++){ 符号k好数要求的数 if(x !="j" + && 1){ dp方程 dp[i][j] 1][x]; 注意取模 %="MOD;" } int ans="0;" 开头不能为o,所以开头i的范围为1 i="1;i" k;i++){ printf("%d\n", ans); return 0; *