JZ-074-n 個骰子的點數

n 個骰子的點數

題目描述

把 n 個骰子仍在地上，求點數和為 s 的概率。

題目鏈接: n 個骰子的點數

代碼

import java.util.AbstractMap;

import java.util.ArrayList;

import java.util.List;

import java.util.Map;

/**

* 標題：n 個骰子的點數

* 把 n 個骰仍在在地上，求點數和為 s 的概率。

*/

public class Jz74 {

/**

* 動態(tài)規(guī)劃

* 使用一個二維數組 dp 存儲點數出現的次數，其中 dp[i][j] 表示前 i 個骰子產生點數 j 的次數。

* 空間復雜度：O(N2)

*

* @param

* @return

*/

public List dicesSum(int n) {

final int face = 6;

final int pointNum = face * n;

long[][] dp = new long[n + 1][pointNum + 1];

for (int i = 1; i

dp[1][i] = 1;

for (int i = 2; i

for (int j = i; j

for (int k = 1; k

dp[i][j] += dp[i - 1][j - k];

final double totalNum = Math.pow(6, n);

List ret = new ArrayList();

for (int i = n; i

ret.add(new AbstractMap.SimpleEntry(i, dp[n][i] / totalNum));

return ret;

}

/**

* 動態(tài)規(guī)劃 + 旋轉數組

* 空間復雜度：O(N)

*

* @param n

* @return

*/

public List dicesSum2(int n) {

final int face = 6;

final int pointNum = face * n;

long[][] dp = new long[2][pointNum + 1];

for (int i = 1; i

dp[0][i] = 1;

int flag = 1; /* 旋轉標記 */

for (int i = 2; i

for (int j = 0; j

dp[flag][j] = 0; /* 旋轉數組清零 */

for (int j = i; j

for (int k = 1; k

dp[flag][j] += dp[1 - flag][j - k];

}

final double totalNum = Math.pow(6, n);

List ret = new ArrayList();

for (int i = n; i

ret.add(new AbstractMap.SimpleEntry(i, dp[1 - flag][i] / totalNum));

return ret;

}

public static void main(String[] args) {

}

}

【每日寄語】 香九齡，能溫席；孝于親，所當執(zhí)。

關鍵詞： JZ-074-n 個骰子的點數 java 動態(tài)規(guī)劃 final