LeetCode如何計(jì)算n個(gè)骰子的點(diǎn)數(shù)

這篇文章主要介紹LeetCode如何計(jì)算n個(gè)骰子的點(diǎn)數(shù)，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

題目

把n個(gè)骰子扔在地上，所有骰子朝上一面的點(diǎn)數(shù)之和為S。輸入n，打印出S的所有可能的值出現(xiàn)的概率。

分析

直接法

假設(shè)骰子有face面，有n個(gè)骰子，那么總排列數(shù)就有face?個(gè)。（例如，有3個(gè)6面骰子，那么其總排列數(shù)為63=216個(gè)）。所有骰子的和最小值為n（假設(shè)骰子最小值為1），而和最大值為n * face(例如，有3個(gè)6面骰子，那么和最大值為18)， 那么就有 （n * face - n + 1）個(gè)可能和值，那么新建長度為（n * face - n + 1）的一維數(shù)組進(jìn)行統(tǒng)計(jì)不同S出現(xiàn)的次數(shù)。

然后骰子分別依次一個(gè)一個(gè)地投，并將其可能的值累加，最后將相應(yīng)數(shù)組元素自增。

最后，遍歷數(shù)組，除以總排列數(shù)，得出結(jié)果。

該算法時(shí)間復(fù)雜度為O(face?)，當(dāng)n越大，運(yùn)算時(shí)間越長。（n從12開始增大，等待時(shí)間就開始難以接受）空間復(fù)雜度為O(n * face)。

動(dòng)態(tài)規(guī)劃

確定問題解的表達(dá)式?？蓪(n, s)表示n個(gè)骰子點(diǎn)數(shù)的和為s的排列情況總數(shù)

確定狀態(tài)轉(zhuǎn)移方程。n個(gè)骰子點(diǎn)數(shù)和為s的種類數(shù)只與n-1個(gè)骰子的和有關(guān)。因?yàn)橐粋€(gè)普通骰子有六個(gè)點(diǎn)數(shù)，那么第n個(gè)骰子可能出現(xiàn)1到6的點(diǎn)數(shù)。所以第n個(gè)骰子點(diǎn)數(shù)為1的話，f(n,s)=f(n-1,s-1)，當(dāng)?shù)趎個(gè)骰子點(diǎn)數(shù)為2的話，f(n,s)=f(n-1,s-2)，…，依次類推。在n-1個(gè)骰子的基礎(chǔ)上，再增加一個(gè)骰子出現(xiàn)點(diǎn)數(shù)和為s的結(jié)果只有這6種情況！那么有：

f(n,s) = f(n-1,s-1) + f(n-1,s-2) + f(n-1,s-3) + f(n-1,s-4) + f(n-1,s-5) + f(n-1,s-6)

上面就是狀態(tài)轉(zhuǎn)移方程，已知初始階段的解為：當(dāng)n=1時(shí), f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。

該算法時(shí)間復(fù)雜度為O(n2)，空間復(fù)雜度為O(n2)。

以3個(gè)6面骰子為例，所用到dp[i][j]數(shù)組如下圖所示。

放碼

一、直接法

import java.util.Arrays;

public class SumOfNDices {

	public static int DICE_MAX_VALUE = 6;
	
	public double[] getProbability(int numOfDice) {
		if(numOfDice < 1) {
			throw new IllegalArgumentException();
		}
		
		int maxSum = DICE_MAX_VALUE * numOfDice;
		int[] sums = new int[maxSum - numOfDice + 1];
		Arrays.fill(sums, 0);
		
		setSums(numOfDice, sums);
		
		int total = (int)Math.pow(DICE_MAX_VALUE, numOfDice);
		
		return Arrays.stream(sums).mapToDouble((a)->(a * 1.0 / total)).toArray();
		
	}
	
	public void setSums(int numOfDice, int[] sums) {
		for(int i = 1; i <= DICE_MAX_VALUE; i++) {
			setSums(numOfDice, numOfDice - 1, i, sums);
		}
	}
	
	public void setSums(int numOfDice, int leftNumOfDice, int sum, int[] sums) {
		if(leftNumOfDice == 0) {
			sums[sum - numOfDice]++;
		}else {
			for(int i = 1; i <= DICE_MAX_VALUE; i++) {
				setSums(numOfDice, leftNumOfDice - 1, i + sum, sums);
			}
		}
	}
	
}

二、動(dòng)態(tài)規(guī)劃（二維數(shù)組）

public double[] getProbability2(int numOfDice) {
	if(numOfDice < 1) {
		throw new IllegalArgumentException();
	}
	int[][] dp = new int[numOfDice + 1][numOfDice * DICE_MAX_VALUE + 1];
	double[] result = new double[numOfDice * DICE_MAX_VALUE - numOfDice + 1];
	double total = Math.pow(DICE_MAX_VALUE, numOfDice);

	Arrays.fill(dp[1], 1, DICE_MAX_VALUE + 1, 1);

	for(int i = 1; i <= numOfDice; i++) {//如1, 2, 3, 4, 5, 6 
		for(int j = i; j <= DICE_MAX_VALUE * numOfDice; j++) {//n個(gè)6面骰子的和的可能值 ：6, 7, 8, 9, ...  
			for(int k = 1; k <= DICE_MAX_VALUE; k++) {//f(n, s) = f(n - 1, s - 1) + f(n - 1, s - 2) + f(n - 1, s - 3) + ...  
				dp[i][j] += (j >= k ? dp[i - 1][j - k] : 0); // j >= k 預(yù)防數(shù)組越界 

				if(i == numOfDice) {
					result[j - i] = dp[i][j] / total;
				}
			}
		}
	}

	return result;
}

由于每個(gè)dp[i][j]只于i-1時(shí)刻的狀態(tài)有關(guān)，所以可以刪去一個(gè)維度，簡(jiǎn)化算法。

三、動(dòng)態(tài)規(guī)劃（一維數(shù)組）

• 在上述解法的基礎(chǔ)上，刪去一個(gè)維度

• 第二個(gè)循環(huán)從后往前遍歷，避免覆蓋

public double[] getProbability3(int numOfDice) {
	if(numOfDice < 1) {
		throw new IllegalArgumentException();
	}
	int[] dp = new int[numOfDice * DICE_MAX_VALUE + 1];
	double[] result = new double[numOfDice * DICE_MAX_VALUE - numOfDice + 1];
	double total = Math.pow(DICE_MAX_VALUE, numOfDice);
	
	for(int i = 1; i <= DICE_MAX_VALUE; i++) {
		dp[i] = 1;
		result[i - 1] = 1.0 / DICE_MAX_VALUE;
	}
	
	for(int i = 2; i <= numOfDice; i++) {
		for(int j = DICE_MAX_VALUE * numOfDice; j >= 1; j--) {
			
			int temp = 0;
			for(int k = 1; k <= DICE_MAX_VALUE; k++) {
				temp += (j >= k) ? dp[j - k] : 0;
			}
			dp[j] = temp;
			
			if(i == numOfDice && j >= numOfDice) {
				result[j - i] = dp[j] / total;
			}
			
		}
	}
	
	return result;
}

測(cè)試

import java.util.Arrays;

import org.junit.Assert;
import org.junit.Test;

public class SumOfNDicesTest {

	@Test
	public void test() {
		SumOfNDices sd = new SumOfNDices();
		double[] result = sd.getProbability(1);
		System.out.println(result.length);
		System.out.println(Arrays.toString(result));
	}

	@Test
	public void test2() {
		SumOfNDices sd = new SumOfNDices();
		double[] result = sd.getProbability(10);
		double[] result2 = sd.getProbability2(10);
		
		Assert.assertArrayEquals(result, result2, 1E-10);
	}
	
	@Test
	public void test3() {
		SumOfNDices sd = new SumOfNDices();
		double[] result = sd.getProbability(10);
		double[] result3 = sd.getProbability3(10);

		Assert.assertArrayEquals(result, result3, 1E-10);
	}
}

以上是“LeetCode如何計(jì)算n個(gè)骰子的點(diǎn)數(shù)”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！