建立动态规划状态转移方程的练习

algorithm

大学里面算法课老师教导过动态规划,但是就像看书要把书看厚再看薄一样,要把动态规划彻底理解,还是需要一些时间的锻炼。解动态规划问题,每个人都有自己的习惯的套路,我的理解是最核心的过程有两部,一个是找出问题的一个一个子“ 状态”,再一个就是建立“ 状态转移方程”(就是所谓的“ 递推关系式”)。把这个过程搞定,基本上动态规划的题目就解了一半了,剩下那些代码层面的事情,是把思路和数学方程实现而已了。

在实现的过程中,可能会用到一些技巧,比如“ 循环还是递归”,这只是实现的办法而已,不是动态规划的本质;再比如空

[……]阅读全文

再谈大楼扔鸡蛋的问题

egg 这道题是说,100 层楼,两个一模一样的鸡蛋,某层之上扔鸡蛋就会碎。问要测试多少次才能找出这层楼来。我曾经在去年初的这篇文章里面讨论过这个问题的解法,因为只想记录一下思路和讨论过程,写得很简略。现在,我想重新整理一下这个问题,再稍稍扩展和挖掘一下。希望可以用尽可能清晰易懂的描述,把这个问题的前后说清楚。

现在只有两个鸡蛋,而算法必须在各种合法输入下都是可行的,就是说要能找出这一层来,你得假设你的运气最差,这就意味着,我求解的是在每种扔鸡蛋的策略下都有一个需要扔的次数的最大值,而现在需要求解的是这些最大值中的最小值的问题。如果我只有一枚鸡蛋,这就意味着,我只能从第一层开始老老实实地一层一层往上试

[……]阅读全文

back to top