动态规划经典例题：最长单调递增子序列、完全背包、二维背包、数字三角形硬币找零

一.最长单调递增子序列

设计一个O(n^2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

实验原理

状态转移方程（递推公式）：
对于每个 i，遍历之前的元素 j，如果 nums[j] < nums[i]，说明 nums[i] 可以接在 nums[j] 后面形成递增子序列，那么：
dp[i]=max(dp[i],dp[j]+1),0<=j<i

1. 动态规划数组 dp 初始化：
   数组 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。初始化每个 dp[i] 为 1，因为每个元素至少可以作为一个长度为 1 的子序列。
2. 动态规划填充 dp 数组：
   对于每一个 i，我们遍历所有比 i 小的元素 j（j < i），如果 nums[i] > nums[j]，说明可以将 nums[i] 加入到以 nums[j] 为结尾的递增子序列中，因此更新 dp[i] 为 dp[j] + 1。逐步更新每个 dp[i]，得到以每个元素结尾的最长递增子序列长度。
3. 找出最大值：
   最后遍历 dp 数组，找到最大值，即为整个序列的最长递增子序列的长度。

//longest increasing subsequence,设计一个O(n^2)时间的算法，找出由n个数组成的序列的最长单调递增子序列
//思路：定义一个等长数组dp，dp[i]：以nums[i]结尾的递增子序列长度
//dp[i]=max(dp[k])+1, k满足:0<=k<i && nums[k]<nums[i]
//例如    nums 10 9 2 5 3 7   dp   1 1 1 2 2 3
//dp[5]为例，nums[5]=7, 7前面有3个数字小于7:2,5,3。 对应dp为1，2，2，最大dp是2，则dp[5]=2+1=3
//遍历自己前面的节点，找小于自己的数字，从中找dp最大的，加一
#include <stdio.h>
#define MAX_N 1000
int nums[MAX_N]; //输入序列
int dp[MAX_N];   //存储每个位置的LIS长度
int main() {int n;printf("请输入数组长度：\n");scanf("%d", &n);printf("请输入数组元素：\n");for (int i = 0; i < n; i++) { scanf("%d", &nums[i]);}for (int i = 0; i < n; i++) {    // 初始化 dp 数组，每个位置的 LIS 长度至少为 1dp[i] = 1;}for (int i = 1; i < n; i++) {    // 动态规划计算 LISfor (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = (dp[i] > dp[j] + 1) ? dp[i] : dp[j] + 1;}}}int max_length = 0;    // 查找最长的 LIS 长度for (int i = 0; i < n; i++) {if (dp[i] > max_length) {max_length = dp[i];}}printf("%d\n", max_length);    // 输出结果return 0;
}

二.完全背包问题

实验原理

1. 定义状态
   定义 dp[j] 为背包容量为 j 时，能够获得的最大价值。j 的范围从 0 到 b。
2. 状态转移方程
   对于每个物品 i，选择放入个数 x[i]，重量 a[i]，价值 c[i]。对于每一个容量 j，可以选择放入物品 i 的不同数量，直到当前背包容量无法放入更多的物品 i。
   状态转移方程为：
   dp[j] = max(dp[j], dp[j - a[i]] + c[i]) (当 j >= a[i])
   • dp[j] 表示背包容量为 j 时能获得的最大价值。
   • dp[j - a[i]] + c[i] 表示如果选择物品 i 放入背包，则剩余容量为 j - a[i]，加上物品 i 的价值 c[i]。
3. 最终解
   最终找出 dp[b]，它表示背包容量为 b 时的最大价值。
4. 记录最优解
   需要一个额外的数组 x[i] 来存储每种物品的数量。通过回溯的方法来从 dp[b] 反向推导出每个物品的数量。通过比较 dp[j] 和 dp[j - a[i]] + c[i]，我们可以确定是否选择了物品 i 以及选择了多少个。
   时间复杂度为 O(n * b)，其中 n 是物品的数量，b 是背包容量
   空间复杂度为 O(b)，主要是 dp 和 record 数组的空间
   t *dp = (int *)calloc(b + 1, sizeof(int));
   为什么使用 calloc 而不是 malloc？
   malloc：malloc 仅分配内存，并不会初始化内存的值。它可能会留有“垃圾值”，这可能会影响程序的结果。
   calloc：calloc 不仅分配内存，还将内存初始化为 0。对于动态规划问题，初始化为 0 是非常重要的，因为在没有物品放入背包时，背包的价值应当是 0。
   用 record 数组来记录选中了哪些物品:
   假设有以下动态规划过程：
   dp[4] = 5（背包容量为 4 时，选择了物品 2，最大价值为 5）。
   dp[5] = 7（背包容量为 5 时，选择了物品 2 和物品 1，最大价值为 7）。
   在计算 dp[4] 时，如果物品 2 被选中，record[4] = 2。
   当 dp[5] 达到最大价值时，record[5] = 2 和 record[4] = 1，表示物品 2 和物品 1 被选中了。

//整数线性规划问题，即完全背包，n种物品，每种重量a[i]，价值c[i]，数量x[i]
//求ci乘xi从i=1到n的和的max值
//其中xi为非负整数（1<=i<=n），ai乘xi从i=1到n的和（容量总和）<=b
//设计一个解此问题的动态规划算法，并分析算法的计算复杂性
//状态迁移方程（递推公式）：dp[j] = max(dp[j], dp[j - a[i]] + c[i])(j >= a[i])
//求出最优值（ max 最大值，也是放进背包的物品的最大价值）
//给出最优解（ xi 值， i =1~ n ，也是每种物品装几个）#include<stdio.h>
#include<stdlib.h>
void knapsack(int n,int b,int *a,int *c){//重量a[i]，价值c[i]，数量x[i]，dp[j]容量j时的最大价值int *dp = (int *)calloc(b + 1, sizeof(int));//record记录物品选择情况int *record = (int *)calloc(b + 1, sizeof(int));//计算最大价值for (int i = 0; i < n;i++){for (int j = a[i]; j <= b;j++){if (dp[j] < dp[j - a[i]] + c[i]) {dp[j] = dp[j - a[i]] + c[i];record[j] = i; //当背包容量为 j 时，选择了物品 i}}}printf("最大价值：%d\n", dp[b]);//回溯找出每种物品的选择数量int *x = (int *)calloc(n, sizeof(int));int j = b;while(j>0){int i = record[j];//找最后放入包的物品x[i]++;j -= a[i];//更新背包容量}//输出每种物品的选择printf("每种物品选择的数量：\n");for (int i = 0; i < n;i++){printf("物品%d:%d个\n",i + 1,x[i]);}free(dp);free(record);free(x);
}
int main(){int n, b;printf("请输入物品的种类数n :");scanf("%d", &n);printf("请输入背包容量b:");scanf("%d", &b);int *a = (int *)malloc(n * sizeof(int));int *c = (int *)malloc(n * sizeof(int));printf("请输入每种物品的重量:\n");for (int i = 0; i < n;i++){scanf("%d", &a[i]);}printf("请输入每种物品的价值:\n");for (int i = 0; i < n;i++){scanf("%d", &c[i]);}knapsack(n, b, a, c);free(a);free(c);return 0;
}

三.数字三角形问题

实验原理

每一步只能移动到下一行中相邻的节点上，即与上一层节点下标相同或下标+1。
算法设计： 采用从底部开始向上计算的动态规划方法。每个位置的最大路径和是当前元素值加上其下方相邻元素的最大路径和。我们从底部开始计算每一行的最大路径和，最终得到从顶部到底部的最大路径和。
计算路径和的方式：
从倒数第二行开始，计算每个位置的最大路径和，即：
dp[i][j]=triangle[i][j]+max(dp[i+1][j],dp[i+1][j+1])
计算完成后，最终的最大路径和会存储在 dp[0][0]

//由n行数字组成的三角形,计算从顶至底的一条路径，使该路经过的总和最大
//共包含 n(n+1)/2个元素
#include <stdio.h>
#define MAX_N 100
int triangle[MAX_N][MAX_N];//三角形数据
int dp[MAX_N][MAX_N]; //存储每个位置到达底部的最大路径和
int main() {FILE *input = fopen("input.txt", "r");FILE *output = fopen("output.txt", "w");int n;fscanf(input, "%d", &n);for (int i = 0; i < n; i++) {    // 读取输入的数字三角形for (int j = 0; j <= i; j++) {fscanf(input, "%d", &triangle[i][j]);}}// 初始化 dp 的最后一行，直接赋值为 triangle 的最后一行//由于从底部开始计算，所以最后一行的最大路径和就是它本身的值for (int j = 0; j < n; j++) {dp[n - 1][j] = triangle[n - 1][j];}// 从倒数第二行开始进行动态规划计算for (int i = n - 2; i >= 0; i--) {for (int j = 0; j <= i; j++) {// dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])dp[i][j] = triangle[i][j] + (dp[i + 1][j] > dp[i + 1][j + 1] ? dp[i + 1][j] : dp[i + 1][j + 1]);}}// dp[0][0] 就是从顶端到底端的最大路径和fprintf(output, "%d\n", dp[0][0]);fclose(input);fclose(output);return 0;
}

四.二维背包问题

实验原理

定义 DP 状态：
dp[i][j][k]：表示前 i 个物品中，背包重量不超过 j，体积不超过 k 时的最大价值。
状态转移：对于每个物品 i，我们有两种选择：
不放入背包：此时最大价值为 dp[i-1][j][k]。
放入背包：此时最大价值为 dp[i-1][j-w_i][k-b_i] + v_i，前提是当前背包的重量和体积不超过限制。
状态转移公式为：
dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-w_i][k-b_i] + v_i)

1. void inputItems(Item items[], int *n, int *c, int *d)这里用 int *n, int *c, int *d，代表传递给函数的指针。
   传递指针后，inputItems 可以直接通过指针访问并修改这些值，从而改变原始的 n、c 和 d，并在函数外部生效。
2. memset(dp, 0, sizeof(dp));这个语句是什么意思？
   memset 是一个标准库函数，用来设置一块内存区域的内容。语法如下：
   void *memset(void *ptr, int value, size_t num);
   • ptr：指向要设置的内存区域的指针。
   • value：要设置的值（每个字节将被设置为 value）。
   • num：要设置的字节数。
   作用是将 dp 数组的所有元素初始化为 0。

//二维背包问题,给定n种物品和一个背包
//物品i的重量wᵢ，体积bᵢ,价值vᵢ，背包容量c，容积 d
//应如何选择装入背包中的物品，使得装入背包中物品的总价值最大
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_n 100
#define MAX_c 100
#define MAX_d 100
typedef struct{int weight;int volume;int value;
} Item;
int dp[MAX_n + 1][MAX_c + 1][MAX_d + 1];
void inputItems(Item items[], int *n, int *c, int *d){printf("请输入物品的种数、背包最大重量和容积：\n");scanf("%d %d %d", n, c, d);printf("请输入每个物品的重量、体积和价值：\n");for (int i = 0; i < *n;i++){scanf("%d %d %d", &items[i].weight, &items[i].volume, &items[i].value);}
}
int knapsack(Item items[], int n, int c, int d){memset(dp, 0, sizeof(dp)); //用来设置一块内存区域的内容。语法void *memset(void *ptr, int value, size_t num);/*ptr：指向要设置的内存区域的指针。value：要设置的值（每个字节将被设置为 value）。num：要设置的字节数。*/for (int i = 0; i <= n; i++){ //n个物品for (int j = c; j >= items[i - 1].weight; j--){ //容量递减for (int k = d; k >= items[i - 1].volume;k--){  //容积递减dp[i][j][k] = (dp[i-1][j][k] > dp[i-1][j-items[i-1].weight][k-items[i-1].volume] + items[i-1].value)? dp[i-1][j][k]: dp[i-1][j-items[i-1].weight][k-items[i-1].volume] + items[i-1].value;}}}return dp[n][c][d]; //最大价值
}
int main() {Item items[MAX_n];int n, c, d;inputItems(items, &n, &c, &d);int maxValue = knapsack(items, n, c, d);printf("背包能够获得的最大价值是: %d\n", maxValue);return 0;
}

五.最少钱币问题

实验原理

n 种硬币的面值存储在数组 T[1:n] 中。
Coins[1:n] 存储每种面值的硬币数量。
给定一个目标金额 m，找到最少的硬币数来支付 m。

1. 状态定义：定义 dp[i] 为金额 i 时所需的最少硬币数。
   初始化：dp[0] = 0，即零金额需要零个硬币，其他金额初始化为一个较大的值（如 INF）。
2. 状态转移：
   对于每种硬币面值 T[j] 和它的可用数量 Coins[j]，我们更新 dp 数组。
   我们需要通过从 1 到 Coins[j] 个 T[j] 面值的硬币来更新 dp。
3. 最终结果：
   最终的结果为 dp[m]，如果它仍然是初始值（即无法支付），则返回 -1。
   时间复杂度：O(n * m)，其中 n 是硬币种类数，m 是目标金额。
   空间复杂度：需要一个 dp 数组来存储每个金额所需的最小硬币数。空间复杂度为 O(m)。
4. 外层循环（遍历每种硬币）:
5. 中层循环（遍历当前硬币的使用数量）:
6. 内层循环（递减遍历金额）:目标金额 m 开始，逐渐递减直到面值 T[j]。确保在更新 dp[k] 时不覆盖前面计算得到的值。k 是当前要处理的金额。k - T[j] 表示如果使用了一个面值为 T[j] 的硬币，那么之前的金额是 k - T[j]。
7. 条件判断与更新:
   if (dp[k - T[j]] != INF): 检查 dp[k - T[j]] 是否已经有解。如果 dp[k - T[j]] != INF，表示用之前的硬币组合已经可以得到金额 k - T[j]，那么可以用当前的硬币面值 T[j] 来更新金额 k。
   dp[k] = (dp[k] < dp[k - T[j]] + 1) ? dp[k] : dp[k - T[j]] + 1;:如果原来 dp[k] 更小（已经找到了一个较小的解），就保持原来的 dp[k]；否则，更新为 dp[k - T[j]] + 1，即在用完 k - T[j] 这个金额的基础上，再加一个当前硬币 T[j]。

//设有n种不同面值的硬币，各硬币的面值存在于数组T[1:n]中
//现要用这些面值的硬币来找钱，对任意钱数0<=m<=20001，设计一个最少硬币找钱m的方法
//给定硬币种数n(1<=n<=10)，硬币面值数组T和可用的各面值的硬币数组Coins，以及钱数m
//由input.txt输入数据，第1行n，第2行起每行两个数T[j]和Coins[j],最后一行找钱数m
//将计算出的最少硬币数输出到output.txt, 问题无解时输出-1
#include <stdio.h>
#include <limits.h>
#define MAX_M 20001  // 最大金额
#define INF INT_MAX  // 无解的标记值
int T[10], Coins[10];
int dp[MAX_M];
int minCoins(int n,int m){//初始化dp数组，dp[i]表示金额i所需的最少硬币数for (int i = 0; i <= m; i++){dp[i] = INF;//默认无法达成}dp[0] = 0;for (int j = 0; j < n;j++){ //遍历各种硬币for (int count = 1; count <= Coins[j];count++){ //对每个金额，尝试不同数量该币for (int k = m; k >= T[j]; k--){ //金额递减if (dp[k - T[j] != INF]){ //表示之前的硬币组合已经可以得到金额 k - T[j]，可用当前的硬币面值 T[j] 来更新金额 kdp[k] = (dp[k] < dp[k - T[j]] + 1) ? dp[k] : dp[k - T[j]] + 1;}}}}return dp[m] == INF ? -1 : dp[m];
}
int main(){FILE *input = fopen("input.txt","r");FILE *output = fopen("output.txt", "w");int n, m;fscanf(input, "%d", &n);for (int i = 0; i < n; i++){fscanf(input, "%d %d", &T[i], &Coins[i]); //读取硬币的面值和数量}fscanf(input, "%d", &m);int result = minCoins(n, m);fprintf(output, "%d\n", result);fclose(input);fclose(output);return 0;
}