- 0!= 几?
- 现在给你无限个 1×2 的多米诺骨牌,定义 fn= 用这种骨牌填满一个 n×2 的矩形的方案数。现在请问,f0= 几?
这俩问题有点沙雕,但是都是有实际意义的,两个问题的答案应该都等于 1。第二个问题出现在《具体数学》生成函数章节的开头。具体数学原文:
恰有一种方式用多米诺牌覆盖一个 2×0 矩形,即不用多米诺牌覆盖,于是 f0=1。
你可能觉得这种说法有点扯淡。我们可以换一个做法:可推导出 fi=fi−1+fi−2,f1=1,f2=2,于是我们人为定义 f0=1。
但是对于某些复杂的计数问题的dp转移式,比如我写的cf1666f的:
fi,j=(cntji−(pcntj−1−i))fi,j−1+(cntj−1(i−1)−[pcntj−1−(i−1)])fi−1,j−1
反向推导有点困难。同时在往后做这题时,我发现计算本题答案时需要求出 f0,0 的值,然后我就意识到 f0,0 不仅仅是个dp的起始点,是有实际意义的。
再举个知名点的例子:noip2021 数列。由于楼主实在是不能理解 f0,0,0,0 是什么鬼。于是自己求了一遍只有一位的答案:
for(int i = 1; i <= n; ++i) {
dp[0][i][i&1][i>>1] = powv[0][i];
}
但是我前面说了,计数dp的零点似乎是有实际意义的,所以想问一问如何理解dp的零点的值。