如何建设网站哪个济南兴田德润简介网站建设和网站设计区别

如何建设网站哪个济南兴田德润简介,网站建设和网站设计区别,新闻列表做的最好的网站,湖南seo推广软件算法设计中#xff0c;贪心算法和动态规划是解决最优化问题的两大核心思想。二者均聚焦于 “最优解”#xff0c;但解题策略截然不同#xff1a;贪心追求 “局部最优” 以逼近全局最优#xff0c;动态规划则通过 “记录子问题解” 避免重复计算#xff0c;确保全局最优。本…算法设计中贪心算法和动态规划是解决最优化问题的两大核心思想。二者均聚焦于 “最优解”但解题策略截然不同贪心追求 “局部最优” 以逼近全局最优动态规划则通过 “记录子问题解” 避免重复计算确保全局最优。本文将从原理、适用场景、经典案例出发结合 C 代码实现深入剖析两种算法的核心逻辑与应用差异。一、核心概念梳理1.1 贪心算法Greedy Algorithm核心思想每一步都做出当前状态下的最优选择局部最优且一旦选择便不可回溯最终期望通过一系列局部最优决策得到全局最优解。关键条件问题需满足「贪心选择性质」局部最优能推导出全局最优和「最优子结构」问题的最优解包含子问题的最优解。优缺点优点时间复杂度低实现简单缺点并非所有问题都适用若局部最优无法导向全局最优则贪心失效。1.2 动态规划Dynamic Programming, DP核心思想将复杂问题拆解为若干重叠子问题通过记录子问题的最优解DP 表避免重复计算最终合并子问题解得到全局最优。关键条件问题需满足「最优子结构」和「子问题重叠性」子问题会被多次重复计算。核心步骤定义状态DP 数组 / 表的含义推导状态转移方程确定初始条件计算最优解自底向上 / 自顶向下。优缺点优点能保证全局最优适用范围广缺点空间复杂度较高需存储子问题解状态转移方程设计难度大。二、经典案例对比实现2.1 案例 1找零钱问题贪心 vs 动态规划问题描述给定不同面额的硬币coins和一个总金额amount求凑成该金额所需的最少硬币数。若无法凑出返回 - 1。场景 1硬币面额满足贪心性质如 [1,5,10,25]当硬币面额为规范的整数倍如美元、人民币时贪心算法可直接取最大面额硬币逐步减少金额得到最优解。贪心实现Ccpp运行#include iostream #include vector #include algorithm using namespace std; // 贪心找零仅适用于硬币面额满足贪心选择性质的场景 int greedyChange(vectorint coins, int amount) { // 先将硬币按面额降序排序 sort(coins.rbegin(), coins.rend()); int count 0; for (int coin : coins) { if (amount 0) break; // 尽可能多取当前最大面额的硬币 int num amount / coin; count num; amount - num * coin; } // 若剩余金额不为0说明无法凑出 return amount 0 ? count : -1; } int main() { vectorint coins {1,5,10,25}; // 满足贪心性质的面额 int amount 41; int res greedyChange(coins, amount); if (res -1) { cout 无法凑出金额 endl; } else { cout 最少硬币数贪心 res endl; // 输出4251051 } return 0; }场景 2硬币面额不满足贪心性质如 [1,3,4]若硬币面额为[1,3,4]目标金额为 6贪心会选择4113 枚但最优解是332 枚。此时需用动态规划。动态规划实现Ccpp运行#include iostream #include vector #include climits using namespace std; // 动态规划找零通用解法 int dpChange(vectorint coins, int amount) { // 定义dp数组dp[i]表示凑成金额i所需的最少硬币数 vectorint dp(amount 1, INT_MAX); dp[0] 0; // 初始条件凑0元需要0枚硬币 // 遍历所有金额计算每个金额的最少硬币数 for (int i 1; i amount; i) { // 遍历所有硬币面额尝试更新dp[i] for (int coin : coins) { if (i coin dp[i - coin] ! INT_MAX) { dp[i] min(dp[i], dp[i - coin] 1); } } } return dp[amount] INT_MAX ? -1 : dp[amount]; } int main() { vectorint coins {1,3,4}; // 不满足贪心性质的面额 int amount 6; int res dpChange(coins, amount); if (res -1) { cout 无法凑出金额 endl; } else { cout 最少硬币数DP res endl; // 输出2 } return 0; }2.2 案例 2最长递增子序列LIS—— 动态规划经典应用贪心虽可优化 LIS 的时间复杂度但基础解法为动态规划。问题描述给定一个整数数组nums找到其中最长严格递增子序列的长度。动态规划实现Ccpp运行#include iostream #include vector #include algorithm using namespace std; // 动态规划解LIS时间复杂度O(n²) int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; // 定义dp数组dp[i]表示以nums[i]结尾的最长递增子序列长度 vectorint dp(n, 1); // 初始条件每个元素自身是长度为1的子序列 int maxLen 1; for (int i 1; i n; i) { // 遍历i之前的所有元素更新dp[i] for (int j 0; j i; j) { if (nums[i] nums[j]) { dp[i] max(dp[i], dp[j] 1); } } maxLen max(maxLen, dp[i]); } return maxLen; } // 贪心二分优化LIS时间复杂度O(n log n) int lengthOfLIS_Greedy(vectorint nums) { vectorint tails; // tails[i]表示长度为i1的递增子序列的最小末尾元素 for (int num : nums) { // 二分查找第一个大于等于num的位置 auto it lower_bound(tails.begin(), tails.end(), num); if (it tails.end()) { tails.push_back(num); // 可以延长子序列 } else { *it num; // 替换优化末尾元素为后续更长序列做准备 } } return tails.size(); } int main() { vectorint nums {10,9,2,5,3,7,101,18}; cout LIS长度DP lengthOfLIS(nums) endl; // 输出4 cout LIS长度贪心二分 lengthOfLIS_Greedy(nums) endl; // 输出4 return 0; }2.3 案例 3活动选择问题 —— 贪心经典应用问题描述给定多个活动的开始时间和结束时间选择最多的互不重叠活动。贪心实现Ccpp运行#include iostream #include vector #include algorithm using namespace std; struct Activity { int start; int end; }; // 贪心策略选择结束时间最早的活动 int activitySelection(vectorActivity acts) { // 按结束时间升序排序 sort(acts.begin(), acts.end(), [](const Activity a, const Activity b) { return a.end b.end; }); int count 1; // 至少选第一个活动 int lastEnd acts[0].end; // 遍历剩余活动选择不重叠的 for (int i 1; i acts.size(); i) { if (acts[i].start lastEnd) { count; lastEnd acts[i].end; } } return count; } int main() { vectorActivity acts {{1,2}, {3,4}, {0,6}, {5,7}, {8,9}, {5,9}}; cout 最多可选择的活动数 activitySelection(acts) endl; // 输出4 return 0; }三、贪心与动态规划的核心差异维度贪心算法动态规划决策方式局部最优一步到位不可回溯全局最优记录子问题解逐步推导子问题关系子问题无重叠独立决策子问题重叠需复用解适用场景满足贪心选择性质的问题最优子结构 子问题重叠的问题时间复杂度通常更低如 O (n)、O (n log n)较高如 O (n²)、O (nm)空间复杂度通常 O (1) 或 O (n)需存储 DP 表O (n) 或 O (nm)最优性不一定全局最优保证全局最优四、算法选择策略优先尝试贪心若问题满足 “每一步局部最优能推导出全局最优”如活动选择、哈夫曼编码优先用贪心实现简单且效率高贪心失效用 DP若局部最优无法得到全局最优如非规范面额找零、LIS或问题存在重叠子问题选择动态规划特殊场景优化部分问题如 LIS可通过 “贪心 二分” 优化动态规划的时间复杂度兼顾效率与最优性。五、总结贪心算法是 “短视的最优”依赖问题本身的性质动态规划是 “全局的最优”通过记录子问题解避免重复计算。二者均基于 “最优子结构”但贪心更强调 “贪心选择性质”动态规划更依赖 “子问题重叠性”。在实际开发中需先分析问题特性若能证明贪心选择的正确性优先使用贪心若无法证明或问题存在重叠子问题则选择动态规划。掌握两种算法的核心思想与适用场景是解决算法优化问题的关键。以上所有代码均可直接编译运行建议结合具体场景调试深入理解算法的执行过程与核心逻辑。