2318. Number of Distinct Roll Sequences

Question

You are given an integer n. You roll a fair 6-sided dice n times. Determine the total number of distinct sequences of rolls possible such that the following conditions are satisfied:

1. The greatest common divisor of any adjacent values in the sequence is equal to 1.
2. There is at least a gap of 2 rolls between equal valued rolls. More formally, if the value of the i<sup>th</sup> roll is equal to the value of the j<sup>th</sup> roll, then abs(i - j) > 2.

Return the* total number** of distinct sequences possible*. Since the answer may be very large, return it modulo 10<sup>9</sup><span> </span>+ 7.

Two sequences are considered distinct if at least one element is different.

Solution

DFS+记忆化搜索剪枝。
辅助方法getValidNext计算前两个位置为last1和last2时的所有的下一个有效值，将返回值储存在next[][]数组中。

DFS搜索

DFS搜索，传入剩余骰子数量n，前两个骰子的值x和y。
从next[x][y]中得到所有有效值。并进行递归。
将返回结果加和并返回。
当n等于0时，只有一个组合，因此返回1。

记忆化搜索

在搜索时会重复计算很多相同的x，y与n的组合，因此可以采用记忆化搜索进行剪枝。
用memo[][][]数组记录x，y与n的状态。如果此前已经计算过其结果，则直接返回memo[x][y][n]。

Code

class Solution {
    List<Integer>[][] next;
    int[][][] memo;
    public int distinctSequences(int n) {
        next = new ArrayList[7][7];
        for(int i = 0; i <= 6; i++){
            for(int j = 0; j <= 6; j++){
                next[i][j] = getValidNext(i, j);
            }
        }
        memo = new int[7][7][10001];
        return count(n, 0, 0);
    }
    
    private int count(int n, int x, int y){
        if(n == 0) return 1;
        if(memo[x][y][n] != 0) return memo[x][y][n];
        List<Integer> validNext = next[x][y];
        int sum = 0;
        for(int z : validNext){
            sum += count(n-1, y, z);
            sum %= 1000000007;
        }
        memo[x][y][n] = sum;
        return sum;
    }
    
    private List<Integer> getValidNext(int last1, int last2){
        List<Integer> arr = new ArrayList<>();
        for(int i = 1; i <= 6; i++){
            if(last1 == 0 && last2 == 0) arr.add(i);
            else if(i == last1 || i == last2) continue;
            else if((last2 & 1) == 0 && (i & 1) == 0) continue;
            else if((last2 == 3 || last2 == 6) && (i == 3 || i == 6)) continue;
            else arr.add(i);
        }
        return arr;
    }
}