想问个关于动态规划的问题

来源:7-12 边界控制_二分查找

小学生6年级

2019-09-17

递归和循环其实其实也都还好。平常头痛的题还是动态规划。每次就属于看了答案后就会,不看就想不出来。感觉太巧了。有看过liubobo 的课,动态规划那儿感觉也没有什么太大的收获。 简单点的 DP 还好,复杂点的就感觉根本想不到那个状态转移方程,请问有什么思路么?

写回答

1回答

ccmouse

2019-09-21

动态规划在面试中要不要问事实上一直存在争议。但是面试时的确会出现那么一些动态规划的题,我一般会根据应聘者是否会动态规划,给与不一样的引导。

动态规划思路其实和递归是一样的,动态规划只是一个特殊的技巧,帮助我们去有效率的实现这一类递推(归)关系,也是状态转移方程。

你的问题主要在状态转移方程,那我还是强调两点:

一:原问题的答案可以由子问题推导出。子问题是一个黑盒,在我的课程中,从没有讨论过子问题的答案是怎么算出来的,我只讨论了如何从子问题的答案推导出原问题的答案。

二:子问题的规模一定要比原来的问题小。小1即可。不过不是所有的题都是这样。

除此之外对于动态规划,我们的状态转移方程还需要一些技巧,就是状态能够进行编码

可以是数组长度(例:最长公共子序列)

可以是数值(例:背包问题中背包的剩余重量)

可以是子序列起止点(例:矩阵链乘)

对于子问题的规模,我们也有:

比原问题减小1(例:最长公共子序列,背包问题)

枚举所有直接的子问题(例:矩阵链乘)

通常,如果我们发现贪心法明显不能时,尤其是题目对于某些数值规定范围(比如背包问题规定背包的大小为整数,并且最大不超过多少)时,会考虑动态规划,根据这些子问题的规模,状态编码,组成不同的维度,总能够设法凑出来。

希望能有所启发。

2
0

Google面试官亲授-Java面试新手尊享课

为面试新手量身定制的Java面试尊享课,解锁“鲤鱼跃龙门”的妙招

2853 学习 · 180 问题

查看课程