夜深人静写算法（二） - 动态规划 - 英雄哪里出来 - C++博客
暂且先不说动态规划是怎么样一个算法，由最简单的递推问题说起应该是最恰当不过得了。因为一来，递推的思想非常浅显，从初中开始就已经有涉及，等差数列 f[i] = f[i-1] + d（ i > 0， d为公差，f[0]为初项）就是最简单的递推公式之一；二来，递推作为动态规划的基本方法，对理解动态规划起着至关重要的作用。理论的开始总是枯燥的，所以让读者提前进入思考是最能引起读者兴趣的利器，于是【例题1】应运而生。
【例题1】在一个3 X N的长方形方格中，铺满1X2的骨牌（骨牌个数不限制），给定N，求方案数（图一 -1-1为N=2的所有方案），所以N=2时方案数为3。
图一 -1-1
这是一个经典的递推问题，如果觉得无从下手，我们可以来看一个更加简单的问题，把问题中的"3"变成"2"（即在一个2XN的长方形方格中铺满1X2的骨牌的方案）。这样问题就简单很多了，我们用f[i]表示2Xi的方格铺满骨牌的方案数，那么考虑第i列，要么竖着放置一个骨牌；要么连同i-1列，横着放置两个骨牌，如图2所示。由于骨牌的长度为1X2，所以在第i列放置的骨牌无法影响到第i-2列。很显然，图一 -1-2中两块黑色的部分分别表示f[i-1]和f[i-2]，所以可以得到递推式f[i] = f[i-1] + f[i-2] (i >= 2)，并且边界条件f[0] = f[1] = 1。
图一 -1-2
再回头来看3 X N的情况，首先可以明确当N等于奇数的时候，方案数一定为0。所以如果用f[i] (i 为偶数) 表示3Xi的方格铺满骨牌的方案数，f[i]的方案数不可能由f[i-1]递推而来。那么我们猜想f[i]和f[i-2]一定是有关系的，如图一 -1-3所示，我们把第i列和第i-1列用1X2的骨牌填满后，轻易转化成了f[i-2]的问题，那是不是代表f[i] = 3*f[i-2]呢？
Read full article from 夜深人静写算法（二） - 动态规划 - 英雄哪里出来 - C++博客
No comments:
Post a Comment