青岛制作网站哪家公司好,永久免费域名空间注册,一级建造师考试科目,官网制作一般费用多少DP问题的性质
动态规划#xff08;Dynamic Programming#xff0c;DP#xff09;是指在解决动态规划问题时所依赖的一些基本特征和规律。动态规划是一种将复杂问题分解为更小子问题来解决的方法#xff0c;它适用于具有重叠子问题和最优子结构性质的问题。动态规划问题通常…DP问题的性质
动态规划Dynamic ProgrammingDP是指在解决动态规划问题时所依赖的一些基本特征和规律。动态规划是一种将复杂问题分解为更小子问题来解决的方法它适用于具有重叠子问题和最优子结构性质的问题。动态规划问题通常具有以下特点
特点
1.最优子结构问题的最优解包含其子问题的最优解。也就是说一个问题的最优解可以从其子问题的最优解构造而来。
2.重叠子问题在问题的求解过程中相同的子问题会被多次计算。动态规划通过存储这些子问题的解来避免重复计算。
3.无后效性一旦某个阶段的状态确定之后它就不会再受之后阶段的决策影响。即一个阶段的状态一旦确定就不会再改变。
4.状态转移方程动态规划问题通常可以通过状态转移方程来描述问题的递推关系即如何从一个或多个子问题的解来得到当前问题的解。
常见用法
1.背包问题如0/1背包问题、完全背包问题等。
2.最长公共子序列如编辑距离、最长公共子序列等。
3.最短路径问题如Floyd-Warshall算法、Dijkstra算法等。
4.计数问题如硬币找零问题、计数问题等。
5.序列问题如最长上升子序列、最长回文子序列等。
经典C语言例题
题目 使用动态规划解决0/1背包问题。
示例代码
#include stdio.h
#include stdlib.h
#includestring.h// 计算最大值
int max(int a, int b) {return (a b) ? a : b;
}
// 定义背包问题的结构体
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 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
#includestring.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-1和n-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]为0fib[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函数中我们只使用了三个变量a、b和c来存储斐波那契数列的当前项、前一项和下一项的值。
2.计算斐波那契数列函数首先初始化a为0b为1。然后通过一个循环从i 2开始到i n结束计算斐波那契数列的第n项。在每次循环中我们计算下一项的值c然后更新a和b的值使得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
#includestring.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 max(int a, int b) {return (a b) ? a : b;
}// 计算最大价值
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 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 SubsequenceLCS问题是计算机科学中的一个经典问题属于动态规划领域。它描述的是这样一个场景有两个序列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
#includestring.h
// 计算最大值
int max(int a, int b) {return (a b) ? a : b;
}
// 计算最长公共子序列的长度
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 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 SubsequenceLIS问题是计算机科学中的一个经典问题属于动态规划领域。它描述的是这样一个场景给定一个序列找出一个最长的子序列这个子序列中的元素是严格递增的。
特点
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 numsSize的dp数组用于存储所有可能的子集的和。
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语言中使用数位动态规划计算在一定范围内有多少个回文数。通过这个例子可以更好地理解数位动态规划在解决与数字相关的计数问题中的应用以及如何使用数位动态规划来高效地解决问题。数位动态规划通过在数位层面上定义和转移状态使得问题的解决方案更加高效和简洁。
