LeetCode 1223. 擲骰子模擬 Dice Roll Simulation - Java - DP

題目鏈接：1223. 擲骰子模擬

有一個骰子模擬器會每次投擲的時候生成一個 1 到 6 的亂數，

不過我們在使用它時有個約束，就是使得投擲骰子時，連續 擲出數字 i 的次數不能超過 rollMax[i]（i 從 1 開始編號），

現在，給你一個整數陣列 rollMax 和一個整數 n，請你來計算擲 n 次骰子可得到的不同點數序列的數量，

假如兩個序列中至少存在一個元素不同，就認為這兩個序列是不同的，由于答案可能很大，所以請回傳 模 \(10^9 + 7\) 之后的結果，

示例1：

輸入：n = 2, rollMax = [1,1,2,2,2,3]
輸出：34
解釋：我們擲 2 次骰子，如果沒有約束的話，共有 6 * 6 = 36 種可能的組合，但是根據 
	rollMax 陣列，數字 1 和 2 最多連續出現一次，所以不會出現序列 (1,1) 和 (2,2)，
	因此，最終答案是 36-2 = 34，

示例2：

輸入：n = 2, rollMax = [1,1,1,1,1,1]
輸出：30

示例3：

輸入：n = 3, rollMax = [1,1,1,2,2,3]
輸出：181

提示：

• 1 <= n <= 5000
• rollMax.length == 6
• 1 <= rollMax[i] <= 15

時間復雜度： \(O(n×6^2)\)
空間復雜度： \(O(n)\)

Java代碼：

class Solution {
	private int mod = 1000000007;

	public int dieSimulator(int n,
							int[] rollMax) {
		long[][] dp = new long[n + 1][7];

		for (int point = 1; point <= 6; ++point) {
			dp[1][point] = 1;
		}

		for (int i = 2; i <= n; ++i) {
			for (int j = 1; j <= 6; ++j) {
				dp[i][j] = getNum(dp, i, j, rollMax) % mod;
			}
		}

		long ret = 0;
		for (int point = 1; point <= 6; ++point) {
			ret += dp[n][point];
			ret %= mod;
		}

		if (ret < 0) {
			ret += mod;
		}

		return (int) ret;
	}

	private long getNum(long[][] dp,
						int i,
						int j,
						int[] rollMax) {
		long ret = 0;
		for (int point = 0; point <= 6; ++point) {
			ret += dp[i - 1][point];
			ret %= mod;
		}

		int repeatNum = rollMax[j - 1];
		// 去掉重復的統計資料
		if (i > repeatNum) {
			ret -= getRepeat(dp, i - 1, j, repeatNum);
			ret %= mod;
		}

		return ret;
	}

	private long getRepeat(	long[][] dp,
							int i,
							int j,
							int repeatNum) {
		if (i == repeatNum) {
			return 1;
		}

		if (repeatNum == 1) {
			return dp[i][j];
		} else {
			long ret = 0;
			for (int point = 1; point <= 6; ++point) {
				if (point != j) {
					ret += dp[i - repeatNum][point];
					ret %= mod;
				}
			}
			return ret;
		}
	}
}

Java代碼：

// 2019年10月13日22:56:49
// 這是我自己寫的，時間復雜度為O(n×6^3)
class Solution {
    public int dieSimulator(int n, int[] rollMax) {
        int mod = 1000000007;
        long [][] arr = new long[n + 1][7];
        Arrays.fill(arr[1], 1);
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= 6; ++j) {
                if (rollMax[j - 1] == 1) {
                    for (int k = 1; k <= 6; ++k) {
                        if (k == j) {
                            continue;
                        }
                        arr[i][j] += arr[i - 1][k];
                        arr[i][j] %= mod;
                    }
                    continue;
                }
                if (i - rollMax[j - 1] < 1) {
                    for (int k = 1; k <= 6; ++k) {
                        arr[i][j] += arr[i - 1][k];
                        arr[i][j] %= mod;
                    }
                    continue;
                }
                for (int k = 1; k <= 6; ++k) {
                    if (k == j) {
                        for (int k1 = 1; k1 <= 6; ++k1) {
                            if (k1 != j) {
                                arr[i][j] += arr[i - rollMax[j - 1]][k1];
                                arr[i][j] %= mod;
                            }
                        }
                        continue;
                    }
                    arr[i][j] += arr[i - 1][k];
                    arr[i][j] %= mod;
                }
            }
        }
        long ret = 0;
        for (long a : arr[n]) {
            ret += a;
            ret %= mod;
        }
        return (int) ret;
    }
}

原文鏈接：https://blog.csdn.net/pfdvnah/article/details/102539644

標籤：其他

上一篇：Truck History POJ - 1789

下一篇：Highways POJ - 1751