数字型递推

不知道大家有没有注意到有一种算法题目，题目的参数就是几个整数，然后让你求总的方案数。

实际上仅仅是求总的方案数这一点，我的第一反应就是递推，然后就尝试找递推公式。如果再加上题目的参数是几个整数，那么这个题目大概率就是递推了，我把这种题目叫做数字型递推。

不确定其他人有没有这种叫法，我是自己想的，如果有更好的叫法，欢迎告诉我。

1. 什么是数字型递推

数字型递推就是题目的参数是几个整数，然后让你求总的方案数。这种题目的特点是：

1. 题目的参数是几个整数。
2. 题目的要求是求总的方案数。

2. 数字型递推的解题思路

和解决动态规划题目一样，我们的思路还是找到子问题，即如何找到问题规模更小的同样问题。

由于题目的参数是几个整数，那么很容易想到的就是将题目给的参数作为递推的参数。

比如爬楼梯的题目，题目给的参数是楼梯的阶数 n，那么我们就可以将楼梯的阶数作为递推的参数。

def dp(n):
    pass

接下来考虑 dp(n) 和 dp(n-1)、dp(n-2)、dp(n-3) …. 之间的关系。

也就是说如果你已经计算出来 dp(n-1)、dp(n-2)、dp(n-3) …. 的值，那么你可以计算出 dp(n) 的值吗？

如果你的答案是肯定的，说明你找到了递推公式。

对于这道题来说，由于第 n 阶楼梯只能从第 n-1 阶楼梯或者第 n-2 阶楼梯上来，所以 dp(n) = dp(n-1) + dp(n-2)。也就是说可以通过 dp(n-1) 和 dp(n-2) 的值计算出 dp(n) 的值。

我们成功地找到了递推公式，那么我们就可以写出代码了。

@cache
def dp(n):
    if n == 1:
        return 1
    if n == 2:
        return 2
    return dp(n-1) + dp(n-2)

我们会在后面《如何找递推公式》部分通过几个更难的题目来展示如何找递推公式。

3. 如何找递推公式

找递推公式是数字型递推的关键，找到递推公式，题目就解决了一大半，剩下的就是些细节问题。

接下来，我们通过力扣上难度为困难的几道题目来展示如何找递推公式。

1866. 恰有 K 根木棍可以看到的排列数目

题目链接：恰有 K 根木棍可以看到的排列数目

题目给了 n 和 k 两个参数，n 表示木棍的数量，k 表示恰有 k 根木棍可以看到的排列数目，返回的是方案数。

和爬楼梯一样，我们考虑将 n 和 k 作为递推的参数。

def dp(n, k):
    pass

容易想到的是前面放置了 n - 1 根木棍的情况下，我们现在要放置第 n 根木棍，那么有几种情况？这几种情况加和起来就是 dp(n, k) 的值。

由于小的不能挡住大的，大的能挡住小的。因此如果放置最大的木棍，那么这根木棍一定是可见的。相反，如果放置最小的木棍，除非你放到最左边，否则这根木棍一定是不可见的。

我们需要枚举所有长度的木棍，然后再枚举木棍放置的位置来递推答案么？

我们可以不这么做。

由于 n - 1 根木棍已经是长度各不相同的。因此放置第 n 根木棍的时候，不管第 n 根长度是多少，至少它和其他 n - 1 根木棍长度一定也是不同的。而不管你的第 n 根木棍长度是多少，方案数一定是相同的。换句话说，就是无论第 n 根木棍长度如何，算出来的方案数一定是相同的。

你也可以这么理解，对于一个方案来说，你先放置第 n 根木棍，然后再放置其他 n - 1 根木棍，这个方案和你先放置其他 n - 1 根木棍，然后再放置第 n 根木棍是一样的。

另外我发现，如果第 n 根木棍是最小的，那么就很容易计算出 dp(n, k) 的值。具体来说就是：

1. 放到第一个位置的话，方案数就是 dp(n-1, k-1)，因此自己必然能被看到。
2. 放到第二个位置的话，方案数就是 dp(n-1, k)，因此自己必然不能被看到。
3. 。。。

因此 dp(n, k) = dp(n-1, k-1) + dp(n-1, k) * (n-1)。

3317. 安排活动的方案数

题目链接：3317. 安排活动的方案数

题目给了三个整数，n，x 和 y。n 表示表演者的数量，x 是节目数，y 是可以给节目打 [1-y] 分的评分。求总的方案数。

和上面一样，我们考虑将 n，x 和 y 作为递推的参数。

def dp(n, x, y):
    pass

和前面题目一样，我们现在考虑安排第 n 个表演者，也就是前面已经安排了 n-1 个表演者的情况下，我们现在要安排第 n 个表演者。

我们很快就发现，前面的节目的评分如何，对总体方案数没有影响，但是前面已经分配了多少节目对总体方案数有影响。

也就是说前面的递推参数中的 y 是没有用的，我们可以去掉 y。

def dp(n, x):
    pass

第 n 个表演者：

1. 可以分配到前面的 x 个节目中的任意一个，那么 dp(n, x) = dp(n-1, x) * x。
2. 也可以分配到一个新的节目中，那么 dp(n, x) = dp(n-1, x-1)。

你可以有疑问，为什么不是 dp(n-1, x - 1) * 剩下的节目数呢？这是因为我们现在没有考虑节目的顺序。但是顺序不同难道不是不同的方案么？

没错，不过这个问题我们稍后解决，我们先计算不考虑顺序的方案数。

但是就算不考虑顺序，我们还剩下两个问题。

1. 我们需要枚举一共参加了多少节目（因为题目说明有的节目可以没有人的），也就是说答案是 dp(n, 1) + dp(n, 2) + … + dp(n, x)。
2. 对于某一个安排来说，一个节目的得分有 y 种可能，因此对于 x 个节目来说，有 pow(y, x) 种可能。

因此不考虑顺序，代码如下：

def dp(n, x):
    if n == 0 and x == 0:
        return 1
    if n == 0 or x == 0:
        return 0
    return dp(n-1, x) * x + dp(n-1, x-1)

total_ways = 0
for j in range(1, x + 1):
    total_ways = (total_ways + dp(n, j) * pow(y, j))

最后我们再考虑顺序的问题。对于一个安排来说，我们只需要将节目的全部排列数加和起来就是答案了。注意是节目的排列数，而不是表演者的排列数。具体来说就是 A(x, j)，指的是 x 个节目中选 j 个节目的排列数。

def dp(n, x):
    if n == 0 and x == 0:
        return 1
    if n == 0 or x == 0:
        return 0
    return dp(n-1, x) * x + dp(n-1, x-1)

total_ways = 0
for j in range(1, x + 1):
    total_ways = (total_ways + dp(n, j) * pow(y, j) * A(x, j))

4. 总结

数字型递推是一类题目，题目的参数是几个整数，然后让你求总的方案数。这种题目的解题思路和动态规划一样，找到递推公式，然后写出代码。

状态的设计套路是将题目的参数作为递推的参数。

确定了状态，接下来观察更小的子问题和原问题有没有什么联系。

确定连接的常见技巧就是考虑放置第 n 个元素的情况，然后考虑第 n 个元素和其他元素的关系。这是找递推公式的关键。而找递推公式又是数字型递推的关键，最后我们通过几个难度为困难的题目展示了如何找递推公式。

最后，希望大家多多练习，加油！