作者:whisper
链接:https://www.proprogrammar.com/article/1023
声明:请尊重原作者的劳动,如需转载请注明出处
动态规划中的计数型问题就是利用动态规划的算法思想去计算出解决这个问题有多少种方法。
比如,从起点走到终点,可以有多少条路径,注意,是多少条,而不是具体路线的描述。
当然也有具体每一条路线的问法,这是 dfs 的问题了。
计数是组合数学的重要内容。不考虑用母函数等手段求解析解的话,计数问题一般有两种做法:
以卡特兰数为例,
在实际问题中,绝大多数都是用方法 2 来做,首先是因为递推关系相对好找一些,另外即使找到了组合数公式,依然要面临求组合数的问题。
在找递推关系时,有时需要手算若干例子找规律,然后猜想递推关系再验证。
下一小节我们用两道例题看一下这两种方法的思考过程。
本题更好想的做法是用动态规划来做,对于位置 (i,j),它可能从上面或左面转移而来,因此状态设计和状态转移可以写成如下形式:
dp[i][j] := 从 (0,0) 到 (i,j) 的方法数
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
按照计数问题的思路,我们可以这样想:从 (0,0) 走到 (m, n) 一共需要走 m + n - 2 步,其中 m - 1 步是向下走的,n - 1 步是向右走的。因此问题转化为从 m + n - 2 中选 m - 1 个,共有多少选法。
这个问题的组合数公式比较好写,如下:
我们可以用递推的方式求这个组合数,参考杨辉三角。
很多问题用动态规划的思考方式思考时,可能会发现状态不是很好设计,或者不是很好转移,组合数公式也不好想,此时需要手算一些例子,看看能不能找到一些规律,找到突破口进而得到递推公式。
本题是典型的一例。
本题是问:k 种颜色,n 个栅栏,最多连续 2 个颜色相同,问有多少涂色的方案。
Step 1:手算若干例子,记 dp[i]:=i 个栅栏的方案数 :
// n > 0, k > 0
n == 1: dp[n] = k
n == 2: dp[n] = k * k
n == 3: dp[n] = k * k * k - k
n == 4: dp[n] = k * (k * k * k - k) - k * k
Step 2:通过上述手算例子,可以猜想如下递推公式:
如果要证明,可以考虑数学归纳法。
Step 3:将递推关系视为动态规划的状态转移,求解问题。
如果递推关系是线性的,可以用矩阵快速幂加速,这是下一章的内容。下一小节中有 16 道计数问题的练习题,练习这些题目时重点体会寻找递推关系的过程。
组合数学中的格路模型,每个格路模型都有一个等价的放球模型
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论