dp心得 约定不等于承诺〃 2021-07-16 12:21 421阅读 0赞 DP心得 动态规划是把一个问题分成若干个子问题，其中每一步求取最优的解，然后把这些解保存下来，再利用这些已有的解推出之后所要求的。应该满足如下条件： 1.最优子结构： 对于所要求解的最终问题，我们要求出其最优的解。而这个问题可以分为很多个与最终问题相似的子问题，对于每个子问题我们求出其最优的解，再运用这些最优子问题的解来推导出最终问题。因为问题与子问题相似故可以用相同的方法从最简单（即规模最小的那个子问题）层层递推，直到得到最终问题的解。 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 \[8\] 。 2.无后效性。 对于每一个阶段而言（问题），所要求出的最优策略（对于该问题的最优解）只有当前的状态决定（当前所记录的本问题的子问题的解），而不直接受之前的状态决定。状态对应于对之前求出的子问题情况的一个总结，是一个客观条件。 状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性 。 动态规划的一般思路： 1.将原问题拆分为子问题。（子问题具有和原问题相同或类似的求解方式）。 2.确定状态。（注意把历史交代清楚，这与之后的第四步，如何推导状态转移方程相关思考具有哪些参数才能进行后续推导。） 3.初始化开始状态。 4.确定状态转移方程。(如何利用当前的子问题的最优解推出当前问题的最优解) 线性dp: 最长上升子序列 dp\[i\] 以第i个元素作为结尾的最长上升序列元素数 为何如此定义？ 可能因为对应上文第二点，我们需要将历史交代清楚，如果dp\[i\]是前i个元素最长上升序列数，那我们不知道它的最后一个元素是啥，就无从往后推导。 转移方程： dp\[i\]=maxd(dp\[i\],dp\[j\]) j<i&&lst\[j\]<lst\[i\] 和最大的连续串 dp\[i\] 以第i个元素结尾的和最大的串 dp\[i\]=max(lst\[i\],dp\[i-1\]+lst\[i\]) 最长公共子序列 dp\[i\]\[j\] 序列a前i个元素和序列b前j个元素的最长公共子序列 dp\[i\]\[j\]= dp\[i-1\]+dp\[j-1\] ,a\[i\]=b\[j\] = max(dp\[i-1\]\[j\],dp\[i\]\[j-1\]) ,a\[i\]!=b\[j\] 区间dp: 石子合并： 有n堆石子，每相邻两堆石子合并会产生相邻两堆石子总合的贡献，问怎样使石子合并为一堆总贡献最大。 dp\[i\]\[j\] i到j合并的石子的最大值 dp\[i\]\[j\]=max(dp\[i\]\[j\],dp\[i\]\[k\]+dp\[k+1\]\[j\]+sum\[i\]\[j\]) ,i=<k<=j 使用记忆化搜索dfs
相关 心得 心得: 今天老师说了学习算法的最大误区就是题就做一遍，可以按照五毒神掌走；至少5遍； 而且说了学习算法要注意： 找规律，因为计算机只能做重复的事情，所以找规律是最好 迈不过友情╰/ 2023年07月24日 08:12/ 0 赞/ 12 阅读
相关 程序员心得 在这个世界上，有数百万的人热衷于软件开发，他们有很多名字，如：软件工程师（Software Engineer），程序员（Programmer），编码人（Coder），开发人员（ 待我称王封你为后i/ 2022年08月08日 11:51/ 0 赞/ 174 阅读
相关 个人心得 突然一看有近两个月的时间没有更新博客了。两个月没有写博客了感觉是在技术方面有些懈怠了，那么在接下来的一段时间里面会有一个很长时间的连续的更新博客。争取达到每天更新一篇博客，持续 朱雀/ 2022年05月26日 05:20/ 0 赞/ 188 阅读
相关 读书心得 读Spring profile解决多环境配置问题 Spring容器-ApplicationContext都做了什么？ 创建BeanFactory来装配BeanDefinit 偏执的太偏执、/ 2022年05月17日 11:53/ 0 赞/ 199 阅读
相关 自考心得 在没考试前，我就想要写点东西，给以后自考留下点东西，方便以后自考的学习。不用说的那么夸张，前人栽树，后人乘凉。只需要，自己种树，自己能乘凉就好。 三遍读书法，第一遍，我觉得还 傷城~/ 2022年05月03日 06:58/ 0 赞/ 246 阅读
相关 dp 题目链接：[http://acm.upc.edu.cn/problem.php?cid=1028&pid=3][http_acm.upc.edu.cn_problem.php_ 我不是女神ヾ/ 2022年04月10日 09:52/ 0 赞/ 192 阅读
相关 心得 不要重复发明轮子，要充分利用已有的资源，比如程序框架[MFC][]、函数库，插件等。 重复现成的、可用的、已经证明很好用的东西就是造轮子 [MFC]: https://ww 本是古典 何须时尚/ 2022年03月26日 11:10/ 0 赞/ 240 阅读
相关 一点心得 这两天更的有点勤，总结了一下最近的状况，记录下来。 学python有一段时间了，从大一开始首先是java，自己找网课琢磨，大二又花了一个寒假的时间找python相关的书来看， 水深无声/ 2022年01月14日 04:15/ 0 赞/ 324 阅读
相关 心得 这一学期已经过去了，在这一学期中，我对自己很不满意，心思完全没有放在学习上面，对于JAVA这门课程来说，没有认真的在学习，上课总是在睡觉，没有听老师认真的讲课，我对于我自己的表 约定不等于承诺〃/ 2021年12月12日 09:29/ 0 赞/ 318 阅读
相关 dp心得 DP心得 动态规划是把一个问题分成若干个子问题，其中每一步求取最优的解，然后把这些解保存下来，再利用这些已有的解推出之后所要求的。应该满足如下条件： 1.最优子结构 约定不等于承诺〃/ 2021年07月16日 12:21/ 0 赞/ 422 阅读
迈不过友情╰
朱雀
傷城~
还没有评论，来说两句吧...