这是真的一开始有点难啊。题看的我不知道怎么用动态规划最有用的学习方法应该是找视频看动画化的才形象吧。最重要偶的还是要学会递推学会反推我觉得动规五部曲很有用啊摘抄自代码随想录确定dp数组dp table以及下标的含义确定递推公式dp的初始化确定遍历顺序如dp[i] 是依靠 dp[i - j]的状态所以遍历i一定是从前向后遍历先有dp[i - j]再有dp[i]举例推导dp数组这样一步一步就可以自己独立解决问题了ok来一题我来分析分析96. 不同的二叉搜索树1.下标含义是第i个结点dp[i]是1到i个结点的种数2.dp[i] dp[j - 1] * dp[i - j]; 哈哈其实这步我一开始写错了。3.dp[0]14.遍历i里面每一个数作为头结点的状态用j来遍历。class Solution { public: int numTrees(int n) { vectorintdp(n1); dp[0]1; for(int i1;in;i) { for(int j1;ji;j) { dp[i]dp[j-1]*dp[i-j]; } } return dp[n]; } };感觉背包就是把一维变二维找清楚什么是物品什么是背包一定要自己手写模拟一遍写了不少基础题。终于有题是完全自己想出来的了。多重背包一、定义01 背包每种物品最多选 1 件完全背包每种物品可以选无限件多重背包每种物品有最多 si 件可以选每件体积 vi价值 wi背包总容量 V求最大价值状态定义一维标准写法dp[j] 背包容量为 j 时能装的最大价值二、朴素做法暴力拆分不推荐大数据思路把第 i 种有 si 件的物品拆成 si 个独立物品直接跑 01 背包56. 携带矿石资源第八期模拟笔试五步法① 确定 dp 数组以及下标的含义dp[j]背包容量为j时能够装入矿石的最大总价值一维滚动数组写法压缩二维 dp只用一维数组保存背包不同容量下的最优解。② 确定递推公式对于第 i 种矿石我们可以取 k 件1≤k≤nums[i]且 k⋅weight[i]≤j不取这件矿石dp[j]保持原值取 k 件这件矿石dp[j - k * weight[i]] k * value[i]dp[j]max(dp[j], dp[j−k⋅w[i]]k⋅v[i])③ dp 数组如何初始化vectorint dp(bagweight1, 0);初始所有dp[j]0含义背包容量为 j还没有装入任何矿石时总价值一定是 0。没有负价值物品不需要初始化为负无穷。④ 确定遍历顺序三层循环顺序第一层 i遍历每一种矿石物品第二层 j背包容量从后往前遍历bagweight → weight [i]和 01 背包一样一维滚动数组逆序遍历防止同一物品被多次重复选取第三层 k枚举当前矿石取多少件1 ~ nums [i]关键点一维dp[j]是上层上一种物品的旧状态j 逆序才能保证更新dp[j]时dp[j - k*w[i]]没有被本次物品提前更新避免重复选。⑤ 举例推导 dp 数组暂省略#includebits/stdc.h using namespace std; int main() { int bagweight,n; cinbagweightn; vectorintweight(n,0); vectorintvalue(n,0); vectorintnums(n,0); for(int i0;in;i)cinweight[i]; for(int i0;in;i)cinvalue[i]; for(int i0;in;i)cinnums[i];//以上是输入 vectorintdp(bagweight1,0); for(int i0;in;i)//遍历物品遍历每一种矿石 { for(int jbagweight;jweight[i];j--)//遍历背包容量 { for(int k1;knums[i](j-k*weight[i])0;k)//枚举当前物品选多少个分离 / 拆分物品数量 { dp[j]max(dp[j],dp[j-k*weight[i]]k*value[i]); } } } coutdp[bagweight]endl; return 0; }目前我觉得的最关键的还是递推公式的确定得自己画表格推出来才行不然不知道上下两个数据的潜在关系是什么啊P1020 [NOIP 1999 提高组] 导弹拦截这道题有两个问题 问题 1一套系统最多拦截导弹数量 最长不上升子序列LNDS长度问题 2最少需要几套系统 最长上升子序列LIS长度Dilworth 定理Dilworth 定理偏序集最少的反链划分数 最长链长度翻译把序列拆成最少个不上升子序列等价于求原序列最长上升子序列长度问题一1. 确定 dp 数组以及下标的含义dp[i]以第i枚导弹结尾的最长不上升子序列的长度2. 确定递推公式遍历前面所有 ji如果 h[j]≥h[i]可以接在 j 后面满足不上升dp[i]max(dp[i],dp[j]1)初始默认dp[i] 1只选自己这一个导弹3. dp 数组如何初始化所有dp[i] 1含义每一枚导弹自身就是长度为 1 的子序列4. 确定遍历顺序两层循环外层 i从前往后遍历每一枚导弹作为子序列结尾内层 j遍历 i 前面所有导弹 0≤ji要用到前面 j 的 dp [j]所以 i 从小到大正序遍历5. 举例推导 dp 数组样例输入问题21. 确定 dp 数组以及下标的含义f[i]以第i枚导弹结尾的最长上升子序列长度2. 确定递推公式遍历前面所有 ji如果 h[j]h[i]f[i]max(f[i],f[j]1)初始f[i]13. dp 数组如何初始化所有f[i] 14. 确定遍历顺序外层 i 从小到大内层 j i 正序遍历5. 举例推导 dp 数组样例以下是部分AC部分超时的代码版本时间复杂度O (n²)#includebits/stdc.h using namespace std; int main() { vectorint h; int x; // 读入所有导弹高度 while(cin x) { h.push_back(x); } int n h.size(); vectorint dp(n,1); // 最长不上升子序列 vectorint f(n,1); // 最长上升子序列 for(int i0;in;i) { for(int j0;ji;j) { // 第一问不上升 h[j] h[i] if(h[j] h[i]) { dp[i] max(dp[i], dp[j]1); } // 第二问上升 h[j] h[i] if(h[j] h[i]) { f[i] max(f[i], f[j]1); } } } int ans1 0, ans2 0; for(int i0;in;i) { ans1 max(ans1, dp[i]); ans2 max(ans2, f[i]); } cout ans1 endl; cout ans2 endl; return 0; }全部ac贪心二分问了ai辅助理解代码好简短清晰的代码-_-我还做不到这种#includebits/stdc.h using namespace std; int main() { vectorint h; // 存储所有导弹的高度 int x; // 循环读取输入的导弹高度直到输入结束适配一行不定长输入 while(cin x) h.push_back(x); vectorint down; // 贪心数组维护最长【不上升】子序列down.size()就是第一问答案 vectorint up; // 贪心数组维护最长【上升】子序列up.size()就是第二问答案Dilworth定理 // 逐个遍历每一枚导弹的高度 for(auto num : h) { // 求最长不上升子序列第一问一套系统最多拦截导弹数 // upper_bound 在【降序】区间查找第一个 num 的元素迭代器greaterint()代表数组是降序 auto it upper_bound(down.begin(), down.end(), num, greaterint()); if(it down.end()) { // down中所有元素都 num可以接在末尾子序列长度1 down.push_back(num); } else { // 贪心替换把第一个小于num的元素换成num让后续更容易接上更多导弹 *it num; } // 求最长上升子序列第二问最少需要几套拦截系统 // lower_bound 在【升序】区间查找第一个 num 的元素迭代器默认升序无需额外比较函数 auto it2 lower_bound(up.begin(), up.end(), num); if(it2 up.end()) { // up中所有元素都 num可以接在末尾子序列长度1 up.push_back(num); } else { // 贪心替换把第一个大于等于num的元素换成num让后续更容易接更大数字 *it2 num; } } // down.size()最长不上升子序列长度up.size()最长上升子序列长度 cout down.size() \n up.size() endl; return 0; }upper_bound( 起始迭代器, 结束迭代器, 值, [比较函数] )作用在有序区间里二分查找返回迭代器默认升序不带比较器找到第一个 val的元素位置传入greaterint()区间降序找到第一个 val的元素位置down.end()不是最后一个元素是容器末尾后一个空位迭代器代表查找失败区间里没有符合条件的元素判断含义没有找到第一个 num 的元素down 内全部元素 ≥ num可以追加到数组尾部lower_bound(起始迭代器, 结束迭代器, 值, [可选比较函数])默认不传比较器要求区间升序排列功能二分查找返回第一个 ≥ val的元素迭代器P1091 [NOIP 2004 提高组] 合唱队形依旧是两个dp数组分开分析一、left 数组left [i]以 i 结尾左侧最长严格上升子序列dp 数组含义left[i]第 i 位同学作为子序列末尾从左边到 i 的最长严格上升子序列长度递推公式遍历 ji如果 h[j]h[i]left[i]max(left[i],left[j]1)初始化所有left[i] 1自身单独构成长度为 1 的子序列遍历顺序i 从左向右 0~n-1j 在每轮 i 中遍历 0~i-1从小到大举例推导样例二、right 数组right [i]以 i 为起点向右最长严格下降子序列dp 数组含义right[i]第 i 位同学作为峰顶向右延伸的最长严格下降子序列长度等价从右往左求以 i 结尾最长严格上升递推公式遍历 ji如果 h[j]h[i]right[i]max(right[i],right[j]1)初始化所有right[i]1遍历顺序i 从右向左 n-1 downto 0j 遍历 i1 ~ n-1举例推导样例#includebits/stdc.h using namespace std; int main() { int n; cin n; vectorint h(n); // 读取身高数组 for(int i 0; i n; i) { cin h[i]; } vectorint left(n, 1); // left[i]: 以i结尾左侧最长严格上升子序列 vectorint right(n, 1); // right[i]: 以i开头右侧最长严格下降子序列 // 计算left数组从左往右遍历 for(int i 0; i n; i) { for(int j 0; j i; j) { if(h[j] h[i]) // 严格上升 { left[i] max(left[i], left[j] 1); } } } // 计算right数组从右往左遍历 for(int i n - 1; i 0; i--) { for(int j i 1; j n; j) { if(h[j] h[i]) // i后面的比i矮严格下降 { right[i] max(right[i], right[j] 1); } } } // 枚举每个点作为山顶求最长合唱队形长度 int max_len 0; for(int i 0; i n; i) { max_len max(max_len, left[i] right[i] - 1); } // 总人数 - 最长保留人数 需要出列人数 cout n - max_len endl; return 0; }未完待续。