竞赛常考的知识点大总结(五)动态规划

news/2024/6/24 7:42:14/文章来源:https://blog.csdn.net/m0_74000148/article/details/137250182

DP问题的性质

动态规划(Dynamic Programming,DP)是指在解决动态规划问题时所依赖的一些基本特征和规律。动态规划是一种将复杂问题分解为更小子问题来解决的方法,它适用于具有重叠子问题和最优子结构性质的问题。动态规划问题通常具有以下特点:

特点:

1.最优子结构:问题的最优解包含其子问题的最优解。也就是说,一个问题的最优解可以从其子问题的最优解构造而来。

2.重叠子问题:在问题的求解过程中,相同的子问题会被多次计算。动态规划通过存储这些子问题的解来避免重复计算。

3.无后效性:一旦某个阶段的状态确定之后,它就不会再受之后阶段的决策影响。即一个阶段的状态一旦确定,就不会再改变。

4.状态转移方程:动态规划问题通常可以通过状态转移方程来描述问题的递推关系,即如何从一个或多个子问题的解来得到当前问题的解。

常见用法:

1.背包问题:如0/1背包问题、完全背包问题等。

2.最长公共子序列:如编辑距离、最长公共子序列等。

3.最短路径问题:如Floyd-Warshall算法、Dijkstra算法等。

4.计数问题:如硬币找零问题、计数问题等。

5.序列问题:如最长上升子序列、最长回文子序列等。

经典C语言例题:

题目: 使用动态规划解决0/1背包问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 定义背包问题的结构体
typedef struct {int capacity; // 背包容量int* weights; // 物品重量数组int* values; // 物品价值数组int n; // 物品种类数
} Knapsack;// 创建背包问题实例
Knapsack* createKnapsack(int capacity, int* weights, int* values, int n) {Knapsack* knapsack = (Knapsack*)malloc(sizeof(Knapsack));knapsack->capacity = capacity;knapsack->weights = weights;knapsack->values = values;knapsack->n = n;return knapsack;
}// 计算最大价值
int knapsack(Knapsack* knapsack) {int** dp = (int**)malloc((knapsack->n + 1) * sizeof(int*));for (int i = 0; i <= knapsack->n; i++) {dp[i] = (int*)malloc((knapsack->capacity + 1) * sizeof(int));memset(dp[i], 0, (knapsack->capacity + 1) * sizeof(int));}for (int i = 1; i <= knapsack->n; i++) {for (int w = 1; w <= knapsack->capacity; w++) {if (knapsack->weights[i - 1] <= w) {dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - knapsack->weights[i - 1]] + knapsack->values[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}int maxValue = dp[knapsack->n][knapsack->capacity];for (int i = 0; i <= knapsack->n; i++) {free(dp[i]);}free(dp);return maxValue;
}// 计算最大值
int max(int a, int b) {return (a > b) ? a : b;
}int main() {int capacity = 50;int weights[] = {10, 20, 30};int values[] = {60, 100, 120};int n = sizeof(weights) / sizeof(weights[0]);Knapsack* knapsack = createKnapsack(capacity, weights, values, n);printf("Maximum value in knapsack: %d\n", knapsack(knapsack));free(knapsack->weights);free(knapsack->values);free(knapsack);return 0;
}

例题分析:

1.创建背包问题实例createKnapsack函数创建一个背包问题实例,包括背包容量、物品重量数组、物品价值数组和物品种类数。

2.计算最大价值knapsack函数使用动态规划方法计算背包问题的最大价值。它首先创建一个二维数组dp来存储子问题的解,然后通过两层循环遍历所有物品和所有可能的重量,计算每个子问题的解,并更新dp数组。

3.主函数:在main函数中,定义了一个背包问题实例,并调用knapsack函数计算最大价值,最后打印结果。

这个例题展示了如何在C语言中使用动态规划解决0/1背包问题。通过这个例子,可以更好地理解动态规划在解决背包问题中的应用,以及如何使用动态规划来高效地解决具有重叠子问题和最优子结构性质的问题。动态规划通过存储子问题的解来避免重复计算,从而提高了算法的效率。

编码方法(记忆化递归、递推)

编码方法通常指的是在编程中用于解决问题的特定技巧或策略。在动态规划(DP)问题中,编码方法主要涉及记忆化递归和递推两种技术。

记忆化递归(Memoization)

记忆化递归是一种优化递归调用的技术,它通过存储已经计算过的子问题的解来避免重复计算,从而减少计算时间。记忆化通常使用一个数组或哈希表来存储子问题的解。

特点:

1.避免重复计算:通过存储子问题的解,避免了对相同子问题的重复计算。

2.提高效率:减少了不必要的计算,提高了算法的效率。

3.空间换时间:需要额外的空间来存储子问题的解。

常见用法:

1.动态规划问题:在解决具有重叠子问题的动态规划问题时,使用记忆化递归可以显著提高效率。

2.计算斐波那契数列:使用记忆化递归可以高效地计算斐波那契数列的值。

经典C语言例题:

题目: 使用记忆化递归计算斐波那契数列的第n项。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 计算斐波那契数列的第n项,使用记忆化递归
int fibonacci(int n, int* memo) {if (n <= 1) {return n;}// 检查是否已经计算过if (memo[n] != -1) {return memo[n];}// 计算并存储结果memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);return memo[n];
}int main() {int n = 10;int* memo = (int*)malloc((n + 1) * sizeof(int));memset(memo, -1, (n + 1) * sizeof(int));printf("Fibonacci number at position %d is %d\n", n, fibonacci(n, memo));free(memo);return 0;
}

例题分析:

1.记忆化递归函数fibonacci函数接受一个整数n和一个整数数组memo作为参数。memo数组用于存储已经计算过的斐波那契数列的值。

2.递归计算:函数首先检查n是否小于或等于1,如果是,则直接返回n。否则,函数检查memo[n]是否已经被计算过,如果是,则直接返回memo[n]

3.计算并存储结果:如果memo[n]没有被计算过,则递归地调用fibonacci函数计算n-1n-2的斐波那契数,并将结果存储在memo[n]中。

4.主函数:在main函数中,定义了一个整数n和一个整数数组memo。调用fibonacci函数计算斐波那契数列的第n项,并打印结果。

这个例题展示了如何在C语言中使用记忆化递归来计算斐波那契数列的第n项。通过这个例子,可以更好地理解记忆化递归在解决动态规划问题中的应用,以及如何使用记忆化技术来提高算法的效率。记忆化递归通过存储子问题的解,避免了对相同子问题的重复计算,从而减少了计算时间,提高了算法的效率。

递推(Tabulation)

递推是一种自底向上的动态规划技术,它从最基础的情况开始,逐步构建出整个问题的解。递推通常使用一个数组来存储子问题的解,并通过迭代的方式计算出最终的解。

特点:

1.自底向上:从最基础的情况开始,逐步构建出整个问题的解。

2.避免递归:不使用递归调用,而是通过迭代的方式计算出最终的解。

3.空间优化:通常只需要一个一维数组来存储子问题的解。

常见用法:

1.动态规划问题:在解决具有重叠子问题的动态规划问题时,使用递推可以避免递归调用带来的额外开销。

2.计算斐波那契数列:使用递推可以高效地计算斐波那契数列的值。

经典C语言例题:

题目: 使用递推计算斐波那契数列的第n项。

示例代码:

#include <stdio.h>// 计算斐波那契数列的第n项,使用递推
int fibonacci(int n) {int fib[n + 1];fib[0] = 0;fib[1] = 1;for (int i = 2; i <= n; i++) {fib[i] = fib[i - 1] + fib[i - 2];}return fib[n];
}int main() {int n = 10;printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));return 0;
}

例题分析:

1.递推函数fibonacci函数接受一个整数n作为参数,并计算斐波那契数列的第n项。

2.初始化数组:函数首先初始化一个数组fib,并设置fib[0]为0,fib[1]为1。

3.迭代计算:函数通过一个循环从i = 2开始,到i = n结束,计算fib[i]的值,并将其存储在数组中。

4.返回结果:函数最后返回fib[n]的值,即斐波那契数列的第n项。

这个例题展示了如何在C语言中使用递推技术来计算斐波那契数列的第n项。通过这个例子,可以更好地理解递推在解决动态规划问题中的应用,以及如何使用迭代的方式来计算问题的解。递推通过自底向上的方式,逐步构建出整个问题的解,避免了递归调用带来的额外开销,提高了算法的效率。

滚动数组

滚动数组(Rolling Array)是一种在动态规划问题中使用的优化技术,它用于减少存储空间的使用。滚动数组通过重用数组空间来存储不同阶段的子问题解,从而避免了为每个阶段都创建一个新数组。

特点:

1.空间优化:滚动数组通过重用数组空间来减少存储空间的使用,通常将数组大小减少到常数级别。

2.避免重复创建数组:在动态规划问题中,每个阶段的子问题解通常只依赖于前一个阶段的解,因此可以重用数组空间。

3.易于实现:滚动数组的实现通常很简单,只需要在计算下一个阶段的解时覆盖前一个阶段的解即可。

4.适用范围:滚动数组适用于那些子问题解只依赖于前一个阶段解的动态规划问题。

常见用法:

1.动态规划问题:在解决具有重叠子问题的动态规划问题时,使用滚动数组可以显著减少空间复杂度。

2.计算斐波那契数列:使用滚动数组可以高效地计算斐波那契数列的值。

经典C语言例题:

题目: 使用滚动数组计算斐波那契数列的第n项。

示例代码:

#include <stdio.h>// 计算斐波那契数列的第n项,使用滚动数组
int fibonacci(int n) {int a = 0, b = 1, c;if (n == 0) {return a;}for (int i = 2; i <= n; i++) {c = a + b;a = b;b = c;}return b;
}int main() {int n = 10;printf("Fibonacci number at position %d is %d\n", n, fibonacci(n));return 0;
}

例题分析:

1.滚动数组:在fibonacci函数中,我们只使用了三个变量abc来存储斐波那契数列的当前项、前一项和下一项的值。

2.计算斐波那契数列:函数首先初始化a为0,b为1。然后,通过一个循环从i = 2开始,到i = n结束,计算斐波那契数列的第n项。在每次循环中,我们计算下一项的值c,然后更新ab的值,使得a始终存储前一项的值,b始终存储当前项的值。

3.返回结果:函数最后返回b的值,即斐波那契数列的第n项。

这个例题展示了如何在C语言中使用滚动数组来计算斐波那契数列的第n项。通过这个例子,可以更好地理解滚动数组在解决动态规划问题中的应用,以及如何使用滚动数组来减少存储空间的使用。滚动数组通过重用数组空间来存储不同阶段的子问题解,从而避免了为每个阶段都创建一个新数组,提高了算法的空间效率。

常见线性DP问题

线性动态规划(Linear Dynamic Programming)问题是指那些状态转移只依赖于前一个或几个状态的动态规划问题。这类问题的特点是状态转移方程通常只涉及一维或二维的状态数组,因此它们的解决方案通常比多维状态的动态规划问题更简单、更直观。

特点:

1.状态转移简单:状态转移方程通常只涉及一维或二维的状态数组,使得状态转移过程简单明了。

2.空间复杂度低:由于状态转移的简单性,这类问题的空间复杂度通常较低,有时甚至可以优化到O(1)。

3.易于实现:线性动态规划问题的实现通常比较简单,容易编写和调试。

4.适用范围广:许多常见的动态规划问题都可以归类为线性动态规划问题,如最长公共子序列、最长上升子序列、最大子数组和等。

常见用法:

1.最长公共子序列:如经典的编辑距离问题。

2.最长上升子序列:如股票买卖问题。

3.最大子数组和:如最大子数组问题。

4.背包问题:如0/1背包问题和完全背包问题。

经典C语言例题:

题目: 使用线性动态规划解决最长上升子序列问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 计算最长上升子序列的长度
int lengthOfLIS(int* nums, int numsSize) {int* dp = (int*)malloc(numsSize * sizeof(int));int maxLen = 0;for (int i = 0; i < numsSize; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;}}maxLen = (dp[i] > maxLen) ? dp[i] : maxLen;}int result = maxLen;free(dp);return result;
}// 计算最大值
int max(int a, int b) {return (a > b) ? a : b;
}int main() {int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};int numsSize = sizeof(nums) / sizeof(nums[0]);printf("Length of longest increasing subsequence is: %d\n", lengthOfLIS(nums, numsSize));return 0;
}

例题分析:

1.计算最长上升子序列的长度lengthOfLIS函数接受一个整数数组nums和数组的大小numsSize作为参数,并计算最长上升子序列的长度。

2.初始化dp数组:函数首先创建一个与输入数组大小相同的dp数组,并初始化所有元素为1。

3.状态转移:函数通过两层循环遍历数组中的每个元素。对于每个元素nums[i],函数通过内层循环检查所有小于nums[i]的元素nums[j],并更新dp[i]的值,使其等于dp[j] + 1的最大值,前提是nums[i] > nums[j]

4.更新最大长度:在每次更新dp[i]后,函数检查dp[i]是否大于当前已知的最大长度maxLen,如果是,则更新maxLen

5.返回结果:函数最后返回maxLen的值,即最长上升子序列的长度。

这个例题展示了如何在C语言中使用线性动态规划解决最长上升子序列问题。通过这个例子,可以更好地理解线性动态规划在解决特定类型问题中的应用,以及如何使用线性动态规划来高效地解决问题。线性动态规划通过状态转移方程来计算问题的解,通常具有较低的空间复杂度,使得问题的解决方案更加高效和简洁。

背包问题

背包问题(Knapsack Problem)是计算机科学中的一个经典问题,属于组合优化问题。它描述的是这样一个场景:有一个背包,背包的承重有限,同时有一系列物品,每个物品都有自己的重量和价值。问题的目标是选择一些物品,使得这些物品的总重量不超过背包的承重,同时这些物品的总价值尽可能高。

特点:

1.组合优化:背包问题属于组合优化问题,它要求在有限的条件下选择最优的组合。

2.决策过程:问题的解决过程涉及到一系列的决策,即选择哪些物品放入背包。

3.重叠子问题:背包问题具有重叠子问题的特性,即在解决大问题的过程中会反复遇到相同的小问题。

4.最优子结构:背包问题具有最优子结构的特性,即问题的最优解包含其子问题的最优解。

常见用法:

1.资源分配:在资源有限的情况下,如何分配资源以最大化效益。

2.装载问题:如何装载货物以最大化运输效率。

3.时间管理:如何安排任务以最大化完成的工作量。

4.金融投资:如何分配投资以最大化收益。

经典C语言例题:

题目: 使用动态规划解决0/1背包问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 定义背包问题的结构体
typedef struct {int capacity; // 背包容量int* weights; // 物品重量数组int* values; // 物品价值数组int n; // 物品种类数
} Knapsack;// 创建背包问题实例
Knapsack* createKnapsack(int capacity, int* weights, int* values, int n) {Knapsack* knapsack = (Knapsack*)malloc(sizeof(Knapsack));knapsack->capacity = capacity;knapsack->weights = weights;knapsack->values = values;knapsack->n = n;return knapsack;
}// 计算最大价值
int knapsack(Knapsack* knapsack) {int** dp = (int**)malloc((knapsack->n + 1) * sizeof(int*));for (int i = 0; i <= knapsack->n; i++) {dp[i] = (int*)malloc((knapsack->capacity + 1) * sizeof(int));memset(dp[i], 0, (knapsack->capacity + 1) * sizeof(int));}for (int i = 1; i <= knapsack->n; i++) {for (int w = 1; w <= knapsack->capacity; w++) {if (knapsack->weights[i - 1] <= w) {dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - knapsack->weights[i - 1]] + knapsack->values[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}int maxValue = dp[knapsack->n][knapsack->capacity];for (int i = 0; i <= knapsack->n; i++) {free(dp[i]);}free(dp);return maxValue;
}// 计算最大值
int max(int a, int b) {return (a > b) ? a : b;
}int main() {int capacity = 50;int weights[] = {10, 20, 30};int values[] = {60, 100, 120};int n = sizeof(weights) / sizeof(weights[0]);Knapsack* knapsack = createKnapsack(capacity, weights, values, n);printf("Maximum value in knapsack: %d\n", knapsack(knapsack));free(knapsack->weights);free(knapsack->values);free(knapsack);return 0;
}

例题分析:

1.创建背包问题实例createKnapsack函数创建一个背包问题实例,包括背包容量、物品重量数组、物品价值数组和物品种类数。

2.计算最大价值knapsack函数使用动态规划方法计算背包问题的最大价值。它首先创建一个二维数组dp来存储子问题的解,然后通过两层循环遍历所有物品和所有可能的重量,计算每个子问题的解,并更新dp数组。

3.主函数:在main函数中,定义了一个背包问题实例,并调用knapsack函数计算最大价值,最后打印结果。

这个例题展示了如何在C语言中使用动态规划解决0/1背包问题。通过这个例子,可以更好地理解动态规划在解决背包问题中的应用,以及如何使用动态规划来高效地解决具有重叠子问题和最优子结构性质的问题。动态规划通过存储子问题的解来避免重复计算,从而提高了算法的效率。

最长公共子序列(LCS)

最长公共子序列(Longest Common Subsequence,LCS)问题是计算机科学中的一个经典问题,属于动态规划领域。它描述的是这样一个场景:有两个序列X和Y,找出一个最长的子序列,这个子序列在X和Y中都出现过,且在X和Y中的相对顺序与子序列中的相对顺序相同。

特点:

1.子序列:LCS问题寻找的是两个序列的子序列,而不是子串。子序列不要求连续,而子串要求连续。

2.相对顺序:子序列中的元素在原序列中的相对顺序必须保持不变。

3.最优子结构:LCS问题具有最优子结构的特性,即问题的最优解包含其子问题的最优解。

4.重叠子问题:LCS问题具有重叠子问题的特性,即在解决大问题的过程中会反复遇到相同的小问题。

常见用法:

1.生物信息学:在生物信息学中,LCS可以用于比较DNA序列或蛋白质序列。

2.版本控制系统:在版本控制系统中,LCS可以用来比较不同版本的文件。

3.文本编辑:在文本编辑器中,LCS可以用来实现自动完成和代码补全功能。

4.数据压缩:在数据压缩中,LCS可以用来找出重复的子序列,从而实现压缩。

经典C语言例题:

题目: 使用动态规划解决最长公共子序列问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 计算最长公共子序列的长度
int longestCommonSubsequence(char* text1, char* text2) {int len1 = strlen(text1);int len2 = strlen(text2);int** dp = (int**)malloc((len1 + 1) * sizeof(int*));for (int i = 0; i <= len1; i++) {dp[i] = (int*)malloc((len2 + 1) * sizeof(int));memset(dp[i], 0, (len2 + 1) * sizeof(int));}for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (text1[i - 1] == text2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}int result = dp[len1][len2];for (int i = 0; i <= len1; i++) {free(dp[i]);}free(dp);return result;
}// 计算最大值
int max(int a, int b) {return (a > b) ? a : b;
}int main() {char text1[] = "AGGTAB";char text2[] = "GXTXAYB";printf("Length of LCS is: %d\n", longestCommonSubsequence(text1, text2));return 0;
}

例题分析:

1.初始化dp数组longestCommonSubsequence函数首先创建一个二维数组dp,其大小为两个字符串长度加1,用于存储子问题的解。

2.状态转移:函数通过两层循环遍历两个字符串的每个字符。对于每个字符对text1[i - 1]text2[j - 1],如果它们相等,则dp[i][j]的值为dp[i - 1][j - 1] + 1;如果不相等,则dp[i][j]的值为max(dp[i - 1][j], dp[i][j - 1])

3.返回结果:函数最后返回dp[len1][len2]的值,即两个字符串的最长公共子序列的长度。

这个例题展示了如何在C语言中使用动态规划解决最长公共子序列问题。通过这个例子,可以更好地理解动态规划在解决LCS问题中的应用,以及如何使用动态规划来高效地解决问题。动态规划通过状态转移方程来计算问题的解,通常具有较低的空间复杂度,使得问题的解决方案更加高效和简洁。

最长递增子序列(LIS)

最长递增子序列(Longest Increasing Subsequence,LIS)问题是计算机科学中的一个经典问题,属于动态规划领域。它描述的是这样一个场景:给定一个序列,找出一个最长的子序列,这个子序列中的元素是严格递增的。

特点:

1.递增子序列:LIS问题寻找的是一个递增的子序列,即子序列中的每个元素都比前一个元素大。

2.最优子结构:LIS问题具有最优子结构的特性,即问题的最优解包含其子问题的最优解。

3.重叠子问题:LIS问题具有重叠子问题的特性,即在解决大问题的过程中会反复遇到相同的小问题。

4.动态规划解法:LIS问题通常使用动态规划来解决,通过维护一个数组来存储每个位置的最长递增子序列的长度。

常见用法:

1.生物信息学:在生物信息学中,LIS可以用于分析DNA序列或蛋白质序列中的递增模式。

2.金融分析:在金融分析中,LIS可以用于识别股票价格的递增趋势。

3.数据压缩:在数据压缩中,LIS可以用于找出重复的递增模式,从而实现压缩。

4.路径规划:在路径规划中,LIS可以用于找出最短的递增路径。

经典C语言例题:

题目: 使用动态规划解决最长递增子序列问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 计算最长递增子序列的长度
int lengthOfLIS(int* nums, int numsSize) {int* dp = (int*)malloc(numsSize * sizeof(int));int maxLen = 0;for (int i = 0; i < numsSize; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {dp[i] = dp[j] + 1;}}maxLen = (dp[i] > maxLen) ? dp[i] : maxLen;}int result = maxLen;free(dp);return result;
}// 计算最大值
int max(int a, int b) {return (a > b) ? a : b;
}int main() {int nums[] = {10, 9, 2, 5, 3, 7, 101, 18};int numsSize = sizeof(nums) / sizeof(nums[0]);printf("Length of longest increasing subsequence is: %d\n", lengthOfLIS(nums, numsSize));return 0;
}

例题分析:

1.初始化dp数组lengthOfLIS函数首先创建一个与输入数组大小相同的dp数组,并初始化所有元素为1。

2.状态转移:函数通过两层循环遍历数组中的每个元素。对于每个元素nums[i],函数通过内层循环检查所有小于nums[i]的元素nums[j],并更新dp[i]的值,使其等于dp[j] + 1的最大值,前提是nums[i] > nums[j]

3.更新最大长度:在每次更新dp[i]后,函数检查dp[i]是否大于当前已知的最大长度maxLen,如果是,则更新maxLen

4.返回结果:函数最后返回maxLen的值,即最长递增子序列的长度。

这个例题展示了如何在C语言中使用动态规划解决最长递增子序列问题。通过这个例子,可以更好地理解动态规划在解决LIS问题中的应用,以及如何使用动态规划来高效地解决问题。动态规划通过状态转移方程来计算问题的解,通常具有较低的空间复杂度,使得问题的解决方案更加高效和简洁。

状态压缩DP

状态压缩动态规划(State Compression Dynamic Programming)是一种动态规划的优化技术,它用于减少动态规划中状态表示的空间复杂度。在某些动态规划问题中,状态的表示可以非常紧凑,通过使用位运算或其他技巧来压缩状态空间,从而减少所需的存储空间。

特点:

1.空间优化:状态压缩动态规划通过压缩状态空间来减少存储空间的使用,通常可以将空间复杂度从多项式级别降低到对数级别。

2.位运算:状态压缩通常涉及位运算,如按位与(&)、按位或(|)、按位异或(^)和左移(<<)、右移(>>)等。

3.易于实现:状态压缩的实现通常比较简单,只需要对状态进行适当的编码和解码。

4.适用范围:状态压缩动态规划适用于那些状态可以被压缩的问题,如子集和问题、硬币找零问题等。

常见用法:

1.子集和问题:如0/1背包问题,其中每个物品可以选择放入或不放入背包。

2.硬币找零问题:如给定面额的硬币,求最少硬币数来组成特定金额。

3.图着色问题:如使用最少的颜色给图中的顶点着色,使得相邻的顶点颜色不同。

经典C语言例题:

题目: 使用状态压缩动态规划解决子集和问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 计算子集和问题的解
int subsetSum(int* nums, int numsSize, int sum) {int dp[1 << numsSize];memset(dp, 0, sizeof(dp));dp[0] = 1;for (int i = 0; i < (1 << numsSize); i++) {for (int j = 0; j < numsSize; j++) {if (i & (1 << j)) {dp[i] |= dp[i ^ (1 << j)];}}}return dp[(1 << numsSize) - 1] & (1 << sum);
}int main() {int nums[] = {1, 2, 3};int numsSize = sizeof(nums) / sizeof(nums[0]);int sum = 4;printf("Subset sum %d is %s\n", sum, subsetSum(nums, numsSize, sum) ? "possible" : "not possible");return 0;
}

例题分析:

1.初始化dp数组subsetSum函数首先创建一个大小为1 << numsSizedp数组,用于存储所有可能的子集的和。

2.状态转移:函数通过两层循环遍历所有子集。外层循环遍历所有可能的子集,内层循环检查当前子集中是否包含第j个元素。

3.状态压缩:在内层循环中,如果当前子集包含第j个元素,则使用按位异或运算符^来生成不包含第j个元素的子集,并将这两个子集的和进行按位或运算,以更新dp数组。

4.返回结果:函数最后检查dp[(1 << numsSize) - 1]是否包含sum,如果是,则返回1(表示可能),否则返回0(表示不可能)。

这个例题展示了如何在C语言中使用状态压缩动态规划解决子集和问题。通过这个例子,可以更好地理解状态压缩动态规划在解决特定类型问题中的应用,以及如何使用状态压缩技术来高效地解决问题。状态压缩动态规划通过压缩状态空间来减少存储空间的使用,使得问题的解决方案更加高效和简洁。

树形DP

树形动态规划(Tree Dynamic Programming)是一种动态规划的变体,它在树形结构上进行状态的定义和转移。树形动态规划通常用于解决树形结构上的优化问题,如树形背包问题、树形路径问题等。

特点:

1.树形结构:树形动态规划适用于树形结构的数据,如树形图、树形网络等。

2.状态定义:在树形动态规划中,状态的定义通常与树的节点相关,每个节点可以有一个或多个状态。

3.状态转移:状态转移依赖于树的结构,通常需要考虑父节点和子节点之间的关系。

4.递归实现:树形动态规划通常通过递归函数来实现,每个节点的状态转移依赖于其子节点的状态。

常见用法:

1.树形背包问题:在树形结构上进行背包问题的求解。

2.树形路径问题:在树形结构上求解最长路径、最小路径等问题。

3.树形决策问题:在树形结构上进行决策问题的求解,如树形博弈问题。

经典C语言例题:

题目: 使用树形动态规划解决树形背包问题。

示例代码:

#include <stdio.h>
#include <stdlib.h>// 定义树形背包问题的结构体
typedef struct TreeNode {int weight;int value;struct TreeNode* left;struct TreeNode* right;
} TreeNode;// 创建树形背包问题的节点
TreeNode* createTreeNode(int weight, int value) {TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));node->weight = weight;node->value = value;node->left = NULL;node->right = NULL;return node;
}// 计算树形背包问题的最大价值
int treeKnapsack(TreeNode* root, int capacity) {if (root == NULL) {return 0;}// 如果当前节点的重量大于背包容量,则不能选择当前节点if (root->weight > capacity) {return treeKnapsack(root->left, capacity) + treeKnapsack(root->right, capacity);} else {// 选择当前节点,计算剩余容量下的最大价值int include = root->value + treeKnapsack(root->left, capacity - root->weight) + treeKnapsack(root->right, capacity - root->weight);// 不选择当前节点,只计算左右子树的最大价值int exclude = treeKnapsack(root->left, capacity) + treeKnapsack(root->right, capacity);// 返回两者中的最大值return (include > exclude) ? include : exclude;}
}int main() {TreeNode* root = createTreeNode(10, 100);root->left = createTreeNode(20, 150);root->right = createTreeNode(30, 200);int capacity = 50;printf("Maximum value in knapsack: %d\n", treeKnapsack(root, capacity));free(root->left);free(root->right);free(root);return 0;
}

例题分析:

1.创建树形背包问题的节点createTreeNode函数创建树形背包问题的节点,并初始化节点的重量和价值。

2.计算树形背包问题的最大价值treeKnapsack函数使用递归方法计算树形背包问题的最大价值。函数首先检查当前节点是否为空,如果为空,则返回0。如果当前节点的重量大于背包容量,则不能选择当前节点,函数返回左右子树的最大价值之和。如果当前节点的重量小于或等于背包容量,则可以选择当前节点,函数计算包括当前节点在内的剩余容量下的最大价值,并与不选择当前节点的情况进行比较,返回两者中的最大值。

3.主函数:在main函数中,创建了一个树形背包问题的实例,并调用treeKnapsack函数计算最大价值,最后打印结果。

这个例题展示了如何在C语言中使用树形动态规划解决树形背包问题。通过这个例子,可以更好地理解树形动态规划在解决树形结构上的优化问题中的应用,以及如何使用递归方法来高效地解决问题。树形动态规划通过在树形结构上定义和转移状态,使得问题的解决方案更加高效和简洁。

数位DP

数位动态规划(Digit DP)是一种特殊的动态规划技术,它用于解决与数字相关的计数问题。数位动态规划通常用于计算在一定范围内满足特定条件的数字的数量,例如计算在一定范围内有多少个数字是回文数、有多少个数字满足特定的数位和条件等。

特点:

1.数位处理:数位动态规划涉及对数字的每一位进行单独处理,通常需要将数字转换为数位数组的形式。

2.状态定义:数位动态规划的状态通常与数字的数位有关,每个状态可能代表一个或多个数位的组合。

3.状态转移:状态转移依赖于数位之间的关系,如进位、借位等。

4.记忆化搜索:数位动态规划通常使用记忆化搜索技术来避免重复计算,提高效率。

常见用法:

1.计算回文数数量:在一定范围内计算有多少个回文数。

2.计算满足数位和的数字数量:在一定范围内计算有多少个数字的数位和满足特定条件。

3.计算满足特定数位模式的数字数量:在一定范围内计算有多少个数字符合特定的数位模式。

经典C语言例题:

题目: 使用数位动态规划计算在一定范围内有多少个回文数。

示例代码:

#include <stdio.h>
#include <string.h>// 计算回文数的数量
int countPalindromes(int L, int R) {int dp[10][10][10]; // dp[i][j][k]表示长度为i,最高位为j,最高位前一位为k的回文数数量memset(dp, 0, sizeof(dp));for (int i = 0; i < 10; i++) {dp[1][i][i] = 1; // 单位数的回文数数量}for (int len = 2; len <= R; len++) {for (int j = 0; j < 10; j++) {for (int k = 0; k < 10; k++) {for (int m = 0; m < 10; m++) {if (j == m) {dp[len][j][k] += dp[len - 1][k][m];} else {dp[len][j][k] += dp[len - 1][k][m] / 2;}}}}}int result = 0;for (int j = 0; j < 10; j++) {for (int k = 0; k < 10; k++) {result += dp[R - L + 1][j][k];}}return result;
}int main() {int L = 100, R = 999;printf("Number of palindromes between %d and %d is: %d\n", L, R, countPalindromes(L, R));return 0;
}

例题分析:

1.初始化dp数组countPalindromes函数首先创建一个三维数组dp,用于存储不同长度、最高位和最高位前一位的回文数数量。

2.状态转移:函数通过三层循环遍历所有可能的回文数长度、最高位和最高位前一位。对于每个状态,函数计算所有可能的前一位和当前位组合的数量,并更新dp数组。

3.计算结果:函数最后遍历所有可能的最高位和最高位前一位,将它们与长度R - L + 1组合,计算出在指定范围内的回文数数量,并返回结果。

这个例题展示了如何在C语言中使用数位动态规划计算在一定范围内有多少个回文数。通过这个例子,可以更好地理解数位动态规划在解决与数字相关的计数问题中的应用,以及如何使用数位动态规划来高效地解决问题。数位动态规划通过在数位层面上定义和转移状态,使得问题的解决方案更加高效和简洁。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_1033389.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

2024年MathorCup数学建模思路A题思路分享

文章目录 1 赛题思路2 比赛日期和时间3 组织机构4 建模常见问题类型4.1 分类问题4.2 优化问题4.3 预测问题4.4 评价问题 5 建模资料 1 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 2 比赛日期和时间 报名截止时间&#xff1a;2024…

KingbaseV8 数据库迁移

1、打开数据迁移工具 启动迁移系统路径&#xff1a;安装位置\KESRealPro\V008R006C006B0021\ClientTools\guitools\KDts\KDTS-WEB\bin 3、访问到KingbaseDTS 数据库迁移工具 http://localhost:8080 默认账号密码如下&#xff1a; 账号&#xff1a;admin 密码&#xff1a;123…

创建第一个Electron程序

前置准备 创建一个文件夹&#xff0c;如: electest进入文件夹&#xff0c;初始化npm npm init -y 安装electron依赖包 注&#xff0c;这里使用npm i -D electron会特别卡&#xff0c;哪怕换成淘宝源也不行。可以使用下面方式安装。 首先&#xff0c;安装yarn npm i -g yarn 随…

快速入门Linux,Linux岗位有哪些?(一)

文章目录 Linux与Linux运维操作系统&#xff1f;操作系统图解 认识LinuxLinux受欢迎的原因什么是Linux运维Linux运维岗位Linux运维岗位职责Linux运维架构师岗位职责Linux运维职业发展路线计算机硬件分类运维人员的三大核心职责 运维人员工作&#xff08;服务器&#xff09;什么…

注册接口和前置SQL及数据生成及封装

注册接口 演示注册接口的三步操作&#xff1a;【注册流程逻辑】 第一步&#xff1a;发送注册短信验证码接口请求 请求方法&#xff1a; put 请求地址&#xff1a;http://shop.lemonban.com:8107/user/sendRegisterSms 请求参数&#xff1a;{“mobile”:“13422337766”} 请求头…

蓝桥杯刷题day13——乘飞机【算法赛】

一、问题描述 等待登机的你看着眼前有老有小长长的队伍十分无聊&#xff0c;你突然想要知道&#xff0c;是否存在两个年龄相仿的乘客。每个乘客的年龄用一个 0 到 36500 的整数表示&#xff0c;两个乘客的年龄相差 365 以内就认为是相仿的。 具体来说&#xff0c;你有一个长度…

iOS - Runloop介绍

文章目录 iOS - Runloop介绍1. 简介1.1 顾名思义1.2. 应用范畴1.3. 如果没有runloop1.4. 如果有了runloop 2. Runloop对象3. Runloop与线程4. 获取Runloop对象4.1 Foundation4.2 Core Foundation4.3 示例 5. Runloop相关的类5.1 Core Foundation中关于RunLoop的5个类5.2 CFRunL…

Vue中的一些指令与计算方法

语法 插值语法 HTML的双标签内容中使用&#xff0c;在{{}}之内书写JS代码 属性语法 1.v-bind或: 2.:属性名"值"或v-bind"值" 事件语法 v-on或 v-on:事件名"方法名"或事件名"方法名" 选项 选项&#xff1a;可选的配置项——官方…

3D分割项目 | 基于Pytorch+3DUnet实现的3D体积语义分割算法

项目应用场景 用于 3D 体积语义分割场景&#xff0c;适用于各种物体的 3D 语义分割&#xff0c;比如大米、大豆的体积分割等 项目效果&#xff1a; 项目流程 > 具体参见项目内README.md (1) 安装 conda install -c conda-forge mamba mamba create -n pytorch-3dunet -c p…

OpenHarmony如何模拟搭建本地http静态服务

简介 本文是在基于OpenHarmony 4.0的基础上&#xff0c;介绍了一种编写一个前端http静态服务的思路. 方案设计 在OpenHarmony上&#xff0c;如果想要访问本地网页。有两种方案 u 方案一&#xff1a;使用file协议&#xff0c;将html放至entry/src/main/resource/rawfile下&#…

Vue 3中ref和reactive的区别

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

hcia datacom课程学习(5):MAC地址与arp协议

1.MAC地址 1.1 含义与作用 &#xff08;1&#xff09;含义&#xff1a; mac地址也称物理地址&#xff0c;是网卡设备在数据链路层的地址&#xff0c;全世界每一块网卡的mac地址都是唯一的&#xff0c;出厂时烧录在网卡上不可更改 &#xff08;2&#xff09;作用&#xff1a…

分布式部署LNMP,搭建discuz论坛

LNMP 是一种常见的服务器环境配置&#xff0c;用于运行 Web 应用程序。它由 Linux、Nginx、MySQL&#xff08;或 MariaDB&#xff09;、PHP 组成。 一、安装数据库 数据库主机(192.168.50.101)安装mysql服务 将安装mysql 所需软件包传到/opt目录下安装环境依赖包配置软件模块…

【数据结构】AVL 树

文章目录 1. AVL 树的概念2. AVL 树节点的定义3. AVL 树的插入4. AVL 树的旋转5. AVL 树的验证6. AVL 树的删除7. AVL 树的性能 前面对 map / multimap / set / multiset 进行了简单的介绍【C】map & set&#xff0c;在其文档介绍中发现&#xff0c;这几个容器有个共同点是…

非关系型数据库--------------Redis配置与优化

目录 一、关系型数据库与非关系型数据库 1.1关系型数据库 1.2非关系型数据库 1.2.1非关系型数据库产生背景 1.3关系型非关系型区别 二、Redis 2.1redis简介 2.2Redis命中机制和淘汰机制 2.3Redis 具有以下优点 2.3.1具有极高的数据读写速度 2.3.2redis支持丰富的数据…

2024年最受欢迎的 19 个 VS Code 主题排行榜

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

四川古力未来科技抖音小店:把握电商新风口,前景无限广阔

在数字化浪潮席卷全球的今天&#xff0c;电商行业以其独特的魅力和无限潜力&#xff0c;成为了众多创业者和投资者关注的焦点。四川古力未来科技抖音小店&#xff0c;正是站在这一风口浪尖上的新兴力量&#xff0c;其前景之广阔&#xff0c;令人瞩目。 抖音&#xff0c;作为一款…

[Python人工智能] 四十五.命名实体识别 (6)利用keras构建CNN-BiLSTM-ATT-CRF实体识别模型(注意力问题探讨)

从本专栏开始,作者正式研究Python深度学习、神经网络及人工智能相关知识。前文讲解融合Bert的实体识别研究,使用bert4keras和kears包来构建Bert+BiLSTM-CRF模型。这篇文章将详细结合如何利用keras和tensorflow构建基于注意力机制的CNN-BiLSTM-ATT-CRF模型,并实现中文实体识别…

RWKV_Pytorch:支持多硬件适配的开源大语言模型推理框架

亲爱的技术探索者们&#xff0c;今天我要向大家隆重推荐一个在开源社区中崭露头角的项目——RWKV_Pytorch。这是一个基于Pytorch的RWKV大语言模型推理框架&#xff0c;它不仅具备高效的原生Pytorch实现&#xff0c;而且还扩展了对多种硬件的适配支持&#xff0c;让模型的部署和…

Ubuntu joystick 测试手柄 xbox

Ubuntu joystick 测试手柄 xbox 测试使用Ubuntu20.04 测试环境在工控机 安装测试 实际测试使用的手柄是北通阿修罗2pro 兼容xbox Ubuntu20.04主机 连接手柄或者无线接收器后查看是否已经检测到&#xff1a; ls /dev/input找到输入中的 js0 即为手柄输入 需要安装joysti…