建设部网站建筑工程质保期wordpress 转发

建设部网站建筑工程质保期,wordpress 转发,国际军事新闻联播,网站视频提取作为一名深耕算法的练习生#xff0c;动态规划#xff08;DP#xff09;绝对是绕不开的重点——它不像贪心那样直观#xff0c;也不像暴力那样“无脑”#xff0c;但掌握后就能解决一大类最优解、计数类问题。最近我集中刷了4道经典DP题#xff0c;从“最少硬币”到“马拦…作为一名深耕算法的练习生动态规划DP绝对是绕不开的重点——它不像贪心那样直观也不像暴力那样“无脑”但掌握后就能解决一大类最优解、计数类问题。最近我集中刷了4道经典DP题从“最少硬币”到“马拦过河卒”一路踩坑一路总结终于摸透了核心套路。今天就以第一视角把这4道题的解题思路、代码实现、踩坑记录全部分享出来希望能帮到和我一样在DP里摸爬滚打的小伙伴技术文章大纲DP实战避坑指南经典题目选取与背景介绍选取4道具有代表性的动态规划题目如背包问题、最长公共子序列、股票买卖问题、编辑距离简要说明其在实际开发或面试中的高频出现场景。动态规划核心思想回顾动态规划的三要素重叠子问题、最优子结构、状态转移方程与两种实现方式自顶向下记忆化、自底向上递推。避免直接复述理论结合题目特点强调如何识别DP适用性。题目1背包问题的填表陷阱分析01背包问题的状态定义误区如错误初始化边界条件代码实现中数组越界的常见错误。给出正确定义状态转移方程的示例dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i]) if j w[i] else dp[i-1][j]对比错误写法如未处理负数索引强调预处理的重要性。题目2最长公共子序列的索引混淆说明字符匹配时下标对齐的典型错误如误用s1[i] s2[j]而忽略偏移量。展示正确循环边界与条件判断for i in range(1, len(s1)1): for j in range(1, len(s2)1): if s1[i-1] s2[j-1]: dp[i][j] dp[i-1][j-1] 1指出未考虑空字符串时的初始化漏洞。题目3股票买卖问题的状态遗漏针对含冷冻期的问题分析因缺少“持有/未持有”状态维度导致的转移错误。列举完整三维状态定义dp[i][k][0] max(dp[i-1][k][0], dp[i-1][k][1] prices[i]) # 第i天未持有 dp[i][k][1] max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) # 第i天持有对比简化版本遗漏交易次数限制的后果。题目4编辑距离的递推方向错误讨论从dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]三个方向递推时的优先级混淆问题。演示正确的最小值选取逻辑if word1[i-1] word2[j-1]: dp[i][j] dp[i-1][j-1] else: dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])提醒字符相等时直接继承左上角值的易忽略点。调试与验证技巧打印DP表格检查中间状态的方法边界测试用例设计如空输入、极值数据。单元测试断言示例assert edit_distance(horse, ros) 3性能优化与扩展空间压缩技巧如滚动数组结合题目特点选择维度优化的可行性分析。给出背包问题的一维数组优化代码dp[j] max(dp[j], dp[j-w[i]] v[i]) # 逆向遍历总结与高频FAQ整理面试中关于DP的常见提问如“如何确定状态维度”“为什么记忆化比暴力快”附GitHub代码仓库链接供读者实践。一、最少硬币问题别被贪心误导DP才是万能解这是我接触的第一道DP最优解问题一开始差点走了贪心的弯路还好及时刹住了车。解题思路明确状态定义找对转移方程题目要求用给定面额的硬币凑出指定金额w求最少需要多少枚硬币。一开始我想当然用贪心优先选大面额硬币比如用1、5、11凑15贪心会选111*45枚但实际最优解是5*33枚——这就说明贪心在这题里不成立必须用DP。核心思路拆解状态定义设f[j]表示“凑出金额j所需的最少硬币数”。这个定义是DP的核心必须先想清楚。初始化因为要找最小值所以先把f数组初始化为一个很大的数我用了1145141919大家也可以用INT_MAX表示初始状态下无法凑出该金额而f[0]要初始化为0因为凑出金额0不需要任何硬币。状态转移遍历每一种硬币对于每个金额j从硬币面额a[i]到w如果j a[i]那么f[j]就可以通过“凑出j - a[i]的最少硬币数 1枚当前硬币”来更新即f[j] min(f[j], f[j - a[i]] 1)。我的代码实现带注释#includebits/stdc.h using namespace std; long long n,w,a[1010],f[100010]; // f数组开100010覆盖w最大可能值 int main(){ cinnw; for(int i1;in;i)cina[i]; // 读入n种硬币面额 // 初始化所有金额初始为大值f[0]0漏了f[0]0会全错 for(int i1;i10010;i)f[i]1145141919; // 遍历每种硬币更新状态 for(int i1;in;i) for(int ja[i];jw;j) f[j]min(f[j],f[j-a[i]]1); // 状态转移核心 coutf[w]endl; return 0; }踩坑记录这些错误千万别犯坑1数组开小了一开始我把f数组开成了10010结果当w超过10010时直接越界报错。后来查了题目范围把f数组开到100010才解决大家一定要根据题目给出的w最大值来定义数组大小。坑2忘记初始化f[0]一开始我只初始化了f[1..10010]没管f[0]导致所有状态转移都基于一个不确定的值结果全是乱码。记住DP的边界条件一定要处理好二、纸币组合计数有序循环顺序是关键错一步全错这题和上一题都是硬币相关但问题从“求最少枚数”变成了“求组合总数”而且有个隐藏坑——顺序不同算不同组合这直接决定了循环顺序。解题思路区分有序/无序选对循环顺序题目要求“用给定硬币凑出金额b求有多少种不同的方法顺序不同算不同方法”。比如用1和2凑312和21是两种不同方法。这个需求直接影响循环顺序核心思路如下状态定义设f[j]表示“凑出金额j的不同方法数”。初始化f[0] 1因为凑出金额0只有1种方法——不用任何硬币这是所有状态转移的基础。状态转移因为是有序组合所以要先遍历金额j从1到b再遍历每种硬币a[i]。对于每个j如果j a[i]就把f[j - a[i]]的方法数加到f[j]里相当于“在凑出j - a[i]的基础上加一枚a[i]硬币”最后对1e97取模避免溢出。这里要重点说明如果是“无序组合”顺序不同算一种要先遍历硬币再遍历金额而“有序组合”必须先遍历金额再遍历硬币两者顺序不能搞反我的代码实现带注释#includebits/stdc.h using namespace std; int n,b,f[10001],a[1005]; const int mod 1e97; // 题目要求取模 int main(){ cinnb; for(int i1;in;i){ cina[i]; // 读入硬币面额 } f[0]1; // 边界条件凑0元1种方法 // 有序组合先遍历金额再遍历硬币 for(int i1;ib;i){ for(int j1;jn;j){ if(i-a[j]0){ // 确保j-a[i]合法 f[i](f[i]f[i-a[j]])%mod; // 状态转移 } } } cout(f[b]%mod); }踩坑记录循环顺序错了答案直接凉一开始我没注意“有序”这个条件沿用了上一题“先遍历硬币再遍历金额”的顺序结果算出的答案比样例少了很多。后来才想明白先遍历硬币的话会避免重复组合比如12和21只会算一次不符合题目“有序”的要求。把循环顺序调换后答案就对了三、数字金字塔递归会栈溢出迭代递推才是王道这是一道非常经典的线性DP题思路很直观但一开始用递归做差点崩了后来换成迭代递推才顺利解决。解题思路从顶到底递推处理好边界题目是一个n层的数字金字塔从顶层走到底层每次只能走到相邻的下一层节点求经过节点的数字和最大是多少。核心思路是“逐层递推记录每个位置的最大和”状态定义设dp[i][j]表示“走到第i行第j列时的最大数字和”行和列从0开始计数。初始化dp[0][0] 金字塔顶层的数字因为顶层只有一个节点。状态转移对于第i行第0列每行最左边只能从第i-1行第0列走过来所以dp[i][0] dp[i-1][0] a[i][0]对于第i行第i列每行最右边只能从第i-1行第i-1列走过来所以dp[i][i] dp[i-1][i-1] a[i][i]对于中间的节点0 j i可以从第i-1行第j-1列或第j列走过来取两者的最大值再加上当前节点的数字即dp[i][j] max(dp[i-1][j-1], dp[i-1][j]) a[i][j]。最终答案最后一行所有dp[n-1][j]中的最大值。我的代码实现带注释#includebits/stdc.h using namespace std; int main() { int n; cinn; int a[n1][n1]; // 存储金字塔数字 for(int i0;in;i){ for(int j0;ji;j){ cina[i][j]; // 读入第i行第j列的数字 } } int dp[n1][n1]{0}; // dp数组初始化 dp[0][0]a[0][0]; // 顶层初始化 // 从第1行开始递推 for(int i1;in;i){ for(int j0;ji;j){ if(j0){ // 最左边只能从上一行同一列来 dp[i][j]dp[i-1][j]a[i][j]; }else if(ji){ // 最右边只能从上一行前一列来 dp[i][j]dp[i-1][j-1]a[i][j]; }else{ // 中间取上一行相邻两个的最大值 dp[i][j]max(dp[i-1][j-1],dp[i-1][j])a[i][j]; } } } // 找最后一行的最大值 int x0; for(int j0;jn;j){ xmax(x, dp[n-1][j]); } coutx; return 0; }踩坑记录递归栈溢出迭代才是正解一开始我想用递归做思路是“当前节点的最大和 当前数字 下一行相邻两个节点的最大和”但当n比较大比如n1000时直接栈溢出报错了。后来才反应过来递归的深度是n当n较大时会超出系统栈的限制而迭代递推是逐层计算没有栈溢出的问题效率也更高。四、马拦过河卒路径计数的变种避开马的控制点是核心这题是“网格路径计数”的变种难点在于要避开马的位置和马能跳到的位置控制点一开始我差点漏了对控制点的判断导致答案错误。解题思路先判障碍再算路径题目是说卒从(0,0)出发只能向右或向下走马在某个位置卒不能走到马的位置或马能跳到的位置求卒走到目标位置(bx, by)的路径数。核心思路是“先预处理障碍位置再用DP计算路径数”障碍判断先写一个check函数判断某个位置(x,y)是否是马的位置或马的控制点。马的走法是“日”字所以控制点满足“横纵坐标差的和为3且最大差为2”即|mx - x| |my - y| 3 且 max(|mx - x|, |my - y|) 2。状态定义用一维数组f[j]表示“当前行第j列的路径数”因为每次只能向右或向下走当前行的路径数只和上一行、当前行左边的路径数有关用一维数组可以优化空间。初始化因为卒从(0,0)出发对应到数组中我给坐标加了2的偏移避免越界f[2] 1表示初始位置有1种路径。状态转移遍历每一行i从2到bx2和每一列j从2到by2如果当前位置是障碍就把f[j]置0没有路径能到这里否则f[j] f[j-1]当前位置的路径数 左边位置的路径数因为上一行的路径数已经累积在f[j]里了。我的代码实现带注释#include cmath #include cctype #include cstdio #include cstdlib #include iostream #include algorithm #define ll long long // 快速读入函数提升输入效率 inline int read(){ int num 0; char c getchar(); while(!isdigit(c)) c getchar(); while(isdigit(c)) num (num 1) (num 3) (c ^ 0), c getchar(); return num; } int bx, by, mx, my; ll f[30]; // 一维DP数组优化空间 // 判断(x,y)是否是障碍马的位置或控制点 inline bool check(int x, int y) { if(x mx y my) return 1; // 马的位置 // 马的控制点日字走法 return (std::abs(mx - x) std::abs(my - y) 3) (std::max ((std::abs(mx - x)), std::abs(my - y)) 2); } int main(){ // 坐标加2偏移避免越界比如x0时x-2-2会数组越界 bx read() 2, by read() 2, mx read() 2, my read() 2; f[2] 1; // 初始位置(0,0)对应偏移后的(2,2)路径数为1 // 遍历每行每列 for(int i 2; i bx; i){ for(int j 2; j by; j){ if(check(i, j)){ // 遇到障碍路径数置0 f[j] 0; continue; } f[j] f[j - 1]; // 状态转移当前路径数 左边路径数 } } printf(%lld\n, f[by]); return 0; }踩坑记录坐标越界漏判控制点坑1坐标越界一开始我没给坐标加偏移当x0或y0时check函数里计算|mx - x|可能会导致数组访问越界。后来给所有坐标加了2的偏移就解决了这个问题。坑2漏判控制点一开始我只判断了马的位置没判断马能跳到的控制点导致卒走到控制点的路径也被计算了答案比样例大。加上check函数里的控制点判断后答案就正确了。总结DP的核心是“状态定义边界转移方程”刷完这4道题我对DP的理解更深了一层其实DP并没有那么难关键是抓住三个核心——明确的状态定义、正确的边界条件、合理的状态转移方程。再给大家分享几个小技巧1. 做DP题先想清楚“状态代表什么”再推导转移方程不要上来就写代码2. 边界条件一定要处理好比如f[0]的初始化很多错误都出在边界上3. 遇到路径计数、最优解问题先考虑DP是否适用再想其他方法4. 数组大小要根据题目范围定义避免越界必要时用一维数组优化空间。以上就是我刷这4道DP题的全部经验啦如果大家有其他DP题的解题技巧或者我哪里讲得不对欢迎在评论区交流 最后祝大家都能攻克DP这个难关