Back to Leetcode

Readme

Dynamic_Programming/2318.Number-of-Distinct-Roll-Sequences/Readme.md

latest1.3 KB
Original Source

2318.Number-of-Distinct-Roll-Sequences

我们在基于前i-1位的方案之上,考虑序列的第i位的填充时,思考能否填写某个数字d,需要的约束有:和前一位不能相等,和前一位必须互质,和前两位不能相等。可见,dp[i]关系到了前两位的具体方案。所以我们设计状态dp[i][a][b],表示前i位里最后两位数字分别是a和b的情况下,所有的合法方案数目。

接下来我们就很容易看出dp[i]与dp[i-1]之间的转移关系。因为i的最后两位是a和b,那么i-1的最后两位必然是某个数x和a。所以我们枚举所有合法的x使得dp[i]能将b接在dp[i-1]之后,要使得xab合法需要的条件是:

  1. a和x不能相等
  2. b和x不能相等
  3. x和a必须互质 满足这些条件的话,就意味着dp[i][a][b] += dp[i-1][x][a],即将所有合法的dp[i-1][x][a]方案后面直接加上一个b。

有人会说,这里dp[i][a][b]没有考虑检查a是否和x之前的那个数字相同呀。事实上,dp[i]的合法性是建立在dp[i-1]的基础上的。如果dp[i-1][x][a]代表了合法的方案数目,那么自然就不会存在a与x之前的数字相同的问题。

在实际计算中,我们在更新所有dp[i][a][b]的过程中,可以通过计算ab本身的合法性,来提前跳过一些不合法的dp[i][a][b]