剑指offer-74、n个骰⼦的点数
<h2 id="题目描述">题目描述</h2><p>把 n 个骰⼦扔在地上，所有骰⼦朝上⼀⾯的点数之和为 s 。输⼊ n ，打印出 s 的所有可能的值出现的概率。</p>
<p>你需要⽤⼀个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰⼦所能掷出的点数集合中第 i ⼩的那个的概率。</p>
<p>示例1：</p>
<p>输⼊: 1<br>
输出: </p>
<p>示例2</p>
<p>输⼊: 2<br>
输出:</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力递归">暴力递归</h3>
<p>枚举所有骰子组合。递归计算每个骰子的点数，统计所有可能的和</p>
<pre><code class="language-java">public class Solution {
public double[] dicesProbability(int n) {
// 骰子点数范围：n到6n，共5n+1种可能
int[] counts = new int;
// 递归统计所有可能的和
backtrack(n, 0, counts);
// 计算概率
double total = Math.pow(6, n);
double[] res = new double;
for (int i = 0; i < counts.length; i++) {
res = counts / total;
}
return res;
}
private void backtrack(int remain, int sum, int[] counts) {
if (remain == 0) {
counts++; // 统计和出现的次数
return;
}
// 当前骰子可以是1到6点
for (int i = 1; i <= 6; i++) {
backtrack(remain - 1, sum + i, counts);
}
}
}
</code></pre>
<p>如果使⽤暴⼒法，每⼀个骰⼦扔到 1 - 6 的概率都是 1/6，如果有 n 个 骰⼦，先不看重复的情况，⼀共有 $6^n$ 种情况，点数的范围是 n ~ 6n ，也就是 5n+1 种。</p>
<ul>
<li><strong>时间复杂度</strong>：O(6ⁿ)，每个骰子有6种可能，n个骰子组合数为6ⁿ</li>
<li><strong>空间复杂度</strong>：O(n)，递归调用栈的深度</li>
</ul>
<p>以上的计算复杂度实在太⾼，我们不能接受。</p>
<h3 id="动态规划推荐">动态规划（推荐）</h3>
<p>其实，这道题可以⽤动态规划来处理， 1 个骰⼦的情况是已知的，⽽ 2 个骰⼦的情况呢？ 2 个骰⼦的情况，可以使⽤ 1 个骰⼦的情况推出， 3 个骰⼦的情况，可以使⽤ 2 个骰⼦的结果推出...</p>
<p><code>dp</code>表示i个骰子和为j的出现次数</p>
<p>执行过程示例（n=2）：</p>
<pre><code class="language-text">初始化dp=1, dp=1, ..., dp=1
计算dp = dp = 1
dp = dp + dp = 2
...
dp = dp (不存在) + ... + dp = 1
</code></pre>
<pre><code class="language-java">public class Solution {
public double[] dicesProbability(int n) {
// dp：i个骰子和为j的出现次数
int[][] dp = new int;
// 初始化：1个骰子的情况
for (int j = 1; j <= 6; j++) {
dp = 1;
}
// 填充状态转移表
for (int i = 2; i <= n; i++) { // 骰子数量从2到n
for (int j = i; j <= 6 * i; j++) { // 和的范围：i到6i
for (int k = 1; k <= 6 && k < j; k++) { // 最后一个骰子的点数
dp += dp;
}
}
}
// 计算概率
double total = Math.pow(6, n);
double[] res = new double;
for (int j = n; j <= 6 * n; j++) {
res = dp / total;
}
return res;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，外层循环n次，内层循环最多6n次</li>
<li><strong>空间复杂度</strong>：O(n²)，需要二维数组存储中间结果</li>
</ul>
<h3 id="空间优化动态规划">空间优化动态规划</h3>
<p>通过观察发现当前状态只依赖前一个状态，可以优化空间。通过滚动数组减少空间使用</p>
<pre><code class="language-java">public class Solution {
public double[] dicesProbability(int n) {
// 使用两个一维数组交替更新
int[] prev = new int;
int[] curr = new int;
// 初始化第一个骰子
for (int j = 1; j <= 6; j++) {
prev = 1;
}
// 动态规划填充
for (int i = 2; i <= n; i++) {
Arrays.fill(curr, 0); // 清空当前数组
for (int j = i; j <= 6 * i; j++) {
for (int k = 1; k <= 6 && k < j; k++) {
curr += prev;
}
}
// 交换数组，准备下一轮
int[] temp = prev;
prev = curr;
curr = temp;
}
// 计算概率
double total = Math.pow(6, n);
double[] res = new double;
for (int j = n; j <= 6 * n; j++) {
res = prev / total;
}
return res;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，外层循环n次，内层循环最多6n次</li>
<li><strong>空间复杂度</strong>：O(n)，只保留前一轮的结果，空间从O(n²)降到O(n)</li>
</ul>
<h3 id="数学公式法多项式展开">数学公式法（多项式展开）</h3>
<p>和为s的概率对应于(x+x²+...+x⁶)ⁿ展开式中xˢ的系数</p>
<pre><code class="language-java">public class Solution {
public double[] dicesProbability(int n) {
// 初始化多项式系数：1个骰子时各项系数为1
int[] coeff = new int;
for (int j = 1; j <= 6; j++) {
coeff = 1;
}
// 多项式乘法：计算(1x+1x²+...+1x⁶)^n
for (int i = 2; i <= n; i++) {
int[] newCoeff = new int;
// 多项式乘法计算
for (int j = 1; j <= 6; j++) {
for (int k = i - 1; k <= 6 * (i - 1); k++) {
newCoeff += coeff;
}
}
coeff = newCoeff;
}
// 计算概率
double total = Math.pow(6, n);
double[] res = new double;
for (int j = n; j <= 6 * n; j++) {
res = coeff / total;
}
return res;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，多项式乘法计算</li>
<li><strong>空间复杂度</strong>：O(n)，存储多项式系数</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19588032
頁:
[1]