想问个关于动态规划的问题
来源:7-12 边界控制_二分查找

小学生6年级
2019-09-17
递归和循环其实其实也都还好。平常头痛的题还是动态规划。每次就属于看了答案后就会,不看就想不出来。感觉太巧了。有看过liubobo 的课,动态规划那儿感觉也没有什么太大的收获。 简单点的 DP 还好,复杂点的就感觉根本想不到那个状态转移方程,请问有什么思路么?
写回答
1回答
-
ccmouse
2019-09-21
动态规划在面试中要不要问事实上一直存在争议。但是面试时的确会出现那么一些动态规划的题,我一般会根据应聘者是否会动态规划,给与不一样的引导。
动态规划思路其实和递归是一样的,动态规划只是一个特殊的技巧,帮助我们去有效率的实现这一类递推(归)关系,也是状态转移方程。
你的问题主要在状态转移方程,那我还是强调两点:
一:原问题的答案可以由子问题推导出。子问题是一个黑盒,在我的课程中,从没有讨论过子问题的答案是怎么算出来的,我只讨论了如何从子问题的答案推导出原问题的答案。
二:子问题的规模一定要比原来的问题小。小1即可。不过不是所有的题都是这样。
除此之外对于动态规划,我们的状态转移方程还需要一些技巧,就是状态能够进行编码。
可以是数组长度(例:最长公共子序列)
可以是数值(例:背包问题中背包的剩余重量)
可以是子序列起止点(例:矩阵链乘)
对于子问题的规模,我们也有:
比原问题减小1(例:最长公共子序列,背包问题)
枚举所有直接的子问题(例:矩阵链乘)
通常,如果我们发现贪心法明显不能时,尤其是题目对于某些数值规定范围(比如背包问题规定背包的大小为整数,并且最大不超过多少)时,会考虑动态规划,根据这些子问题的规模,状态编码,组成不同的维度,总能够设法凑出来。
希望能有所启发。
20
相似问题