有限制的随机数（递推版）

一、背景

之前在《Leetcode 第 158 场比赛回顾》文章中，第三题介绍了动态规划的一种解法。

那种解法是动态规划中最简单有效的方法，即递归实现。
也因为递归的缘故，很多人说这类题可以使用记忆化dfs搜索解决。

由于是递归，我们需要储存所有状态，导致使用空间是5000*16*6。

这里，我计划分享一个非递归的版本，即递推，然后可以发现，这个方法还有很大的优化空间。

二、状态转移方程

题意是有n次机会来随机生成数字，每次随机出的数字是1~6。
但是有个限制，相同的数字连续出现的次数有个限制。
问最终生成的合法的数字序列有多少种。

我们定义出了状态：f(k, index, n),代表数字index在前面出现k次时，再掷n次骰子会出现多少序列。

经过简单逻辑推理，我们从后到前得出了递归方程：
f(k, index, n) = 五个 f(1, newindex, n-1) + 一个合法的f(k+1, index, n-1)。

如果使用递推的方式来看的话，则是看哪些状态能够到达f(k, index, n)。

其实这个状态来源只有两种情况。

情况一：k > 1，那么只能从f(k-1, index, n-1)转移过来。
情况二：k == 1，那么只能从f(x, y, n-1)转移过来，其中y != index，x为任意值。

汇总一下就得到下面的状态转移方程：

f(k, index, n) = f(k-1, index, n-1)  
f(k, index, n) = sum(f(x, y, n-1)), k==1&y!=index  

情况二用文字描述比较简单，但是实际涉及很多状态。
比如index等于1，那么涉及下面这些状态

f(1, 2, n-1)
f(2, 2, n-1)
...
f(max2, 2, n-1)
f(1, 3, n-1)
f(2, 3, n-1)
...
f(max3, 3, n-1)
...
f(1, 6, n-1)
...
f(max6, 6, n-1)

面对这么多状态，大概有6*15个，还是蛮多的。
所以需要预处理这些状态的和。

也许有人注意到了，这个二维状态就是一个矩阵。
而情况二的状态和其实就是不包含第index行的矩阵和。
如果我们有每一行的和以及整个矩阵的和，相减就可以快速得到情况二的答案。

每一行的和定义为sum[index]，整个矩阵的和定义是all，则情况二可以改写为具体的公式。

f(1, index, n) = all[n-1] - sum[n-1][index]

三、滚动数组

当我们看到下面的方程时，有经验的你肯定可以发现，状态n只与状态n-1有关，

f(k, index, n) = f(k-1, index, n-1)  
f(1, index, n) = all[n-1] - sum[n-1][index]

所以数组里面n这个维度就没必要了。
定义一个大小为2的滚动数组来循环使用即可。

由此我们就可以实现出代码了。

时间复杂度：O(n*6*16)，与递归一样
空间复杂度：O(2*6*16)

四、最后

动态规划的题，有一个特点就是解题思路有无限种可能。
有时候换一种角度思考，就会找到一种更优的时间或者更优的空间。

后面我有机会我继续这道题的其他解法。
每种解法都会涉及到不同的知识，敬请期待。

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code