做电影平台网站怎么赚钱的中国十大企业培训公司

做电影平台网站怎么赚钱的,中国十大企业培训公司,北京好网站制作公司哪家好,php建设网站所用开发软件一、动态规划的基本概念1.1 什么是动态规划动态规划是一种算法设计范式#xff0c;由美国数学家理查德贝尔曼在20世纪50年代提出。它主要应用于具有重叠子问题和最优子结构性质的问题。动态规划方法通常用来求解最优化问题#xff0c;这类问题可以有多个可行解#xff0c;每…一、动态规划的基本概念1.1 什么是动态规划动态规划是一种算法设计范式由美国数学家理查德·贝尔曼在20世纪50年代提出。它主要应用于具有重叠子问题和最优子结构性质的问题。动态规划方法通常用来求解最优化问题这类问题可以有多个可行解每个解都对应一个值我们希望找到具有最优值最大值或最小值的解。动态规划的核心思想是将待求解的问题分解为若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。与分治法不同的是动态规划的子问题往往不是相互独立的因此需要保存已解决的子问题的答案避免重复计算。1.2 动态规划适用的条件一个问题适合用动态规划求解必须满足以下两个关键特性最优子结构一个问题的最优解包含其子问题的最优解。也就是说可以通过子问题的最优解构造出原问题的最优解。重叠子问题在递归求解过程中会反复遇到相同的子问题而不是生成全新的子问题。1.3 动态规划与分治法的比较特性动态规划分治法子问题重叠子问题独立子问题求解方式自底向上或带记忆的自顶向下通常自顶向下存储需求需要存储子问题的解通常不需要存储子问题的解时间复杂度通常多项式时间可能是指数时间二、动态规划的基本步骤动态规划算法的设计通常遵循以下步骤定义状态确定问题的状态并用状态变量表示建立状态转移方程确定状态之间的转移关系确定初始条件和边界条件确定计算顺序自底向上或自顶向下计算并输出结果三、经典问题解析与C语言实现3.1 斐波那契数列斐波那契数列是动态规划最经典的入门例子它完美展示了重叠子问题和如何通过存储中间结果避免重复计算。3.1.1 问题描述斐波那契数列的定义如下F(0) 0F(1) 1F(n) F(n-1) F(n-2) (n ≥ 2)3.1.2 递归解法低效#include stdio.h // 递归解法 - 时间复杂度O(2^n)非常低效 int fibonacci_recursive(int n) { if (n 1) { return n; } return fibonacci_recursive(n - 1) fibonacci_recursive(n - 2); }递归的重复计算问题计算F(5)时F(3)被计算了2次计算F(4)时F(2)被计算了3次总计算量呈指数级增长3.1.3 动态规划解法#include stdio.h #include stdlib.h // 动态规划解法 - 时间复杂度O(n)空间复杂度O(n) int fibonacci_dp(int n) { if (n 1) { return n; } int *dp (int *)malloc((n 1) * sizeof(int)); if (dp NULL) { printf(内存分配失败\n); return -1; } // 初始条件 dp[0] 0; dp[1] 1; // 状态转移 for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } int result dp[n]; free(dp); return result; } // 优化空间复杂度为O(1)的动态规划解法 int fibonacci_dp_optimized(int n) { if (n 1) { return n; } int prev2 0; // F(i-2) int prev1 1; // F(i-1) int current; // F(i) for (int i 2; i n; i) { current prev1 prev2; prev2 prev1; prev1 current; } return current; } int main() { int n 10; printf(计算斐波那契数列 F(%d):\n, n); printf(递归解法: %d\n, fibonacci_recursive(n)); printf(动态规划解法: %d\n, fibonacci_dp(n)); printf(优化空间的动态规划解法: %d\n, fibonacci_dp_optimized(n)); return 0; }时间复杂度O(n)空间复杂度从O(n)优化到O(1)3.2 爬楼梯问题3.2.1 问题描述假设你正在爬楼梯。需要 n 阶你才能到。你有达楼顶。每次你可以爬 1 或 2 个台阶多少种不同的方法可以爬到楼顶状态定义设 dp[i] 表示爬到第 i 阶楼梯的不同方法数。状态转移方程要到达第 i 阶楼梯有两种方式从第 i-1 阶爬 1 阶上来从第 i-2 阶爬 2 阶上来因此状态转移方程为dp[i] dp[i-1] dp[i-2] (i ≥ 3)边界条件dp[1] 1 // 爬到第1阶有1种方法 dp[2] 2 // 爬到第2阶有2种方法完整实现#include stdio.h #include stdlib.h // 动态规划解法 int climbStairs(int n) { if (n 2) { return n; } // 创建DP数组 int *dp (int *)malloc((n 1) * sizeof(int)); if (dp NULL) { printf(内存分配失败\n); return -1; } // 初始化边界条件 dp[1] 1; // 爬到第1阶只有1种方法爬1阶 dp[2] 2; // 爬到第2阶有2种方法(1,1) 或 (2) // 状态转移 for (int i 3; i n; i) { // 到达第i阶的方法数 到达第i-1阶的方法数 到达第i-2阶的方法数 dp[i] dp[i - 1] dp[i - 2]; // 详细解释 // 1. 从第i-1阶爬1阶上来有dp[i-1]种方法 // 2. 从第i-2阶爬2阶上来有dp[i-2]种方法 // 总方法数就是这两者之和 } int result dp[n]; // 打印中间过程调试用 printf(DP数组: ); for (int i 1; i n; i) { printf(%d , dp[i]); } printf(\n); free(dp); return result; }时间复杂度分析时间复杂度O(n)只需一次遍历空间复杂度O(n)需要长度为n1的数组3.3 背包问题背包问题是动态规划的经典应用分为0-1背包和完全背包两种主要类型。3.3.1 0-1背包问题问题描述有一个容量为C的背包和N件物品每件物品有重量w[i]和价值v[i]。求解将哪些物品装入背包可使这些物品的总重量不超过背包容量且总价值最大。动态规划解法#include stdio.h #include stdlib.h // 0-1背包问题的动态规划解法 int knapsack_01(int C, int N, int w[], int v[]) { // 创建二维DP数组 int **dp (int **)malloc((N 1) * sizeof(int *)); for (int i 0; i N; i) { dp[i] (int *)malloc((C 1) * sizeof(int)); } // 初始化没有物品或背包容量为0时最大价值为0 for (int i 0; i N; i) { dp[i][0] 0; } for (int j 0; j C; j) { dp[0][j] 0; } // 动态规划填表 for (int i 1; i N; i) { for (int j 1; j C; j) { if (j w[i - 1]) { // 当前物品重量大于背包剩余容量不能放入 dp[i][j] dp[i - 1][j]; } else { // 可以选择放入或不放入当前物品取最大值 int not_put dp[i - 1][j]; int put dp[i - 1][j - w[i - 1]] v[i - 1]; dp[i][j] (not_put put) ? not_put : put; } } } int result dp[N][C]; // 输出具体选择了哪些物品 printf(选择的物品: ); int j C; for (int i N; i 0; i--) { if (dp[i][j] ! dp[i - 1][j]) { printf(%d , i); j - w[i - 1]; } } printf(\n); // 释放内存 for (int i 0; i N; i) { free(dp[i]); } free(dp); return result; } // 空间优化版本一维数组 int knapsack_01_optimized(int C, int N, int w[], int v[]) { int *dp (int *)malloc((C 1) * sizeof(int)); // 初始化 for (int j 0; j C; j) { dp[j] 0; } // 动态规划 for (int i 1; i N; i) { // 注意这里需要从后向前遍历确保每个物品只被考虑一次 for (int j C; j w[i - 1]; j--) { int not_put dp[j]; int put dp[j - w[i - 1]] v[i - 1]; dp[j] (not_put put) ? not_put : put; } } int result dp[C]; free(dp); return result; } int main() { int C 10; // 背包容量 int N 5; // 物品数量 int w[] {2, 3, 4, 5, 9}; // 物品重量 int v[] {3, 4, 5, 8, 10}; // 物品价值 printf(0-1背包问题容量%d物品数%d\n, C, N); printf(物品重量: ); for (int i 0; i N; i) { printf(%d , w[i]); } printf(\n); printf(物品价值: ); for (int i 0; i N; i) { printf(%d , v[i]); } printf(\n); int max_value knapsack_01(C, N, w, v); printf(最大价值二维DP: %d\n, max_value); max_value knapsack_01_optimized(C, N, w, v); printf(最大价值一维DP优化: %d\n, max_value); return 0; }3.3.2 完全背包问题问题描述与0-1背包问题类似但每种物品都有无限件可用。关键区别0-1背包每种物品只有1件选或不选完全背包每种物品有无限件可选0件、1件、2件...问题分析1. 与0-1背包的本质区别为了深入理解完全背包我们先对比两种背包问题的区别0-1背包的状态转移方程dp[i][j] max(dp[i-1][j], // 不选第i件物品 dp[i-1][j-w[i]] v[i]) // 选第i件物品只能选一次完全背包的状态转移方程dp[i][j] max(dp[i-1][j], // 不选第i件物品 dp[i][j-w[i]] v[i]) // 选第i件物品可以选多次关键区别第二个状态转移项中从dp[i][j-w[i]]转移而不是dp[i-1][j-w[i]]。这意味着在考虑是否选择第i件物品时已经考虑了可能已经选择了多个该物品的情况。算法实现详解1. 二维DP解法#include stdio.h #include stdlib.h // 完全背包问题的朴素二维DP解法 int knapsack_complete_2d(int C, int N, int w[], int v[]) { // 创建二维DP数组 // dp[i][j]表示考虑前i种物品背包容量为j时的最大价值 int **dp (int **)malloc((N 1) * sizeof(int *)); for (int i 0; i N; i) { dp[i] (int *)malloc((C 1) * sizeof(int)); } // 初始化没有物品时价值为0 for (int j 0; j C; j) { dp[0][j] 0; } printf(完全背包问题容量%d物品种类%d\n, C, N); printf(物品重量); for (int i 0; i N; i) printf(%d , w[i]); printf(\n物品价值); for (int i 0; i N; i) printf(%d , v[i]); printf(\n\n); // 动态规划填表 for (int i 1; i N; i) { for (int j 0; j C; j) { // 不选择第i种物品 dp[i][j] dp[i - 1][j]; // 选择第i种物品如果可以的话 // 注意这里是完全背包的关键与0-1背包的区别 if (j w[i - 1]) { // 这里使用dp[i][j-w[i-1]]而不是dp[i-1][j-w[i-1]] // 这允许同一物品被选择多次 int take dp[i][j - w[i - 1]] v[i - 1]; if (take dp[i][j]) { dp[i][j] take; } } } } // 打印DP表帮助理解 printf(二维DP表\n); printf(容量\\物品 ); for (int i 0; i N; i) { if (i 0) printf(无物品 ); else printf(物品%-2d , i); } printf(\n); for (int j 0; j C; j) { printf(容量%-3d: , j); for (int i 0; i N; i) { printf(%4d , dp[i][j]); } printf(\n); } printf(\n); int result dp[N][C]; // 回溯找出选择的物品和数量 printf(最优选择方案\n); int remaining_capacity C; for (int i N; i 1; i--) { int count 0; while (remaining_capacity w[i - 1] dp[i][remaining_capacity] dp[i][remaining_capacity - w[i - 1]] v[i - 1]) { count; remaining_capacity - w[i - 1]; } if (count 0) { printf( 物品%d选择%d件\n, i, count); } } printf(总价值%d\n, result); // 释放内存 for (int i 0; i N; i) { free(dp[i]); } free(dp); return result; }3.4 最长公共子序列LCS3.4.1 问题描述给定两个序列X和Y找出它们的最长公共子序列的长度。子序列不要求连续但必须保持相对顺序。3.4.2 动态规划解法#include stdio.h #include stdlib.h #include string.h // 最长公共子序列的动态规划解法 int longestCommonSubsequence(char *text1, char *text2) { int m strlen(text1); int n strlen(text2); // 创建二维DP数组 int **dp (int **)malloc((m 1) * sizeof(int *)); for (int i 0; i m; i) { dp[i] (int *)malloc((n 1) * sizeof(int)); } // 初始化边界条件 for (int i 0; i m; i) { dp[i][0] 0; } for (int j 0; j n; j) { dp[0][j] 0; } // 动态规划填表 for (int i 1; i m; i) { for (int j 1; j n; j) { if (text1[i - 1] text2[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] (dp[i - 1][j] dp[i][j - 1]) ? dp[i - 1][j] : dp[i][j - 1]; } } } int result dp[m][n]; // 输出LCS重建路径 printf(最长公共子序列: ); char *lcs (char *)malloc((result 1) * sizeof(char)); lcs[result] \0; int i m, j n, index result - 1; while (i 0 j 0) { if (text1[i - 1] text2[j - 1]) { lcs[index] text1[i - 1]; i--; j--; index--; } else if (dp[i - 1][j] dp[i][j - 1]) { i--; } else { j--; } } printf(%s\n, lcs); free(lcs); // 释放内存 for (int i 0; i m; i) { free(dp[i]); } free(dp); return result; } int main() { char text1[] ABCBDAB; char text2[] BDCABA; printf(序列1: %s\n, text1); printf(序列2: %s\n, text2); int lcs_length longestCommonSubsequence(text1, text2); printf(最长公共子序列长度: %d\n, lcs_length); return 0; }3.5 股票买卖问题3.5.1 问题描述给定一个数组其中第i个元素是第i天股票的价格。设计算法来计算最大利润。3.5.2 动态规划解法#include stdio.h #include stdlib.h // 只能进行一次交易的最大利润 int maxProfit_one_transaction(int prices[], int n) { if (n 1) return 0; int min_price prices[0]; int max_profit 0; for (int i 1; i n; i) { if (prices[i] min_price) { min_price prices[i]; } else { int profit prices[i] - min_price; if (profit max_profit) { max_profit profit; } } } return max_profit; } // 可以进行无限次交易的最大利润 int maxProfit_unlimited(int prices[], int n) { int max_profit 0; for (int i 1; i n; i) { if (prices[i] prices[i - 1]) { max_profit prices[i] - prices[i - 1]; } } return max_profit; } // 最多可以进行两次交易的最大利润 int maxProfit_two_transactions(int prices[], int n) { if (n 1) return 0; // 创建四个数组 int *first_buy (int *)malloc(n * sizeof(int)); int *first_sell (int *)malloc(n * sizeof(int)); int *second_buy (int *)malloc(n * sizeof(int)); int *second_sell (int *)malloc(n * sizeof(int)); // 初始化 first_buy[0] -prices[0]; first_sell[0] 0; second_buy[0] -prices[0]; second_sell[0] 0; for (int i 1; i n; i) { first_buy[i] (first_buy[i - 1] -prices[i]) ? first_buy[i - 1] : -prices[i]; first_sell[i] (first_sell[i - 1] first_buy[i - 1] prices[i]) ? first_sell[i - 1] : first_buy[i - 1] prices[i]; second_buy[i] (second_buy[i - 1] first_sell[i - 1] - prices[i]) ? second_buy[i - 1] : first_sell[i - 1] - prices[i]; second_sell[i] (second_sell[i - 1] second_buy[i - 1] prices[i]) ? second_sell[i - 1] : second_buy[i - 1] prices[i]; } int result second_sell[n - 1]; free(first_buy); free(first_sell); free(second_buy); free(second_sell); return result; } int main() { int prices[] {3, 3, 5, 0, 0, 3, 1, 4}; int n sizeof(prices) / sizeof(prices[0]); printf(股票价格: ); for (int i 0; i n; i) { printf(%d , prices[i]); } printf(\n); printf(只允许一次交易的最大利润: %d\n, maxProfit_one_transaction(prices, n)); printf(允许无限次交易的最大利润: %d\n, maxProfit_unlimited(prices, n)); printf(最多允许两次交易的最大利润: %d\n, maxProfit_two_transactions(prices, n)); return 0; }4.1. 自底向上迭代dp核心// 自底向上动态规划示例 int fibonacci_bottom_up(int n) { if (n 1) { return n; } int dp[n 1]; dp[0] 0; dp[1] 1; for (int i 2; i n; i) { dp[i] dp[i - 1] dp[i - 2]; } return dp[n]; }动态规划不仅能够帮助我们解决具体的算法问题还培养了我们将复杂问题分解为简单子问题的思维习惯感谢观看