高质量的集团网站建设,织梦手机网站模板安装,郑州做旅游网站的公司,中仑建设网站【问题描述】[中等]
把n个骰子扔在地上#xff0c;所有骰子朝上一面的点数之和为s。输入n#xff0c;打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案#xff0c;其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。示例 1:输入: …【问题描述】[中等]
把n个骰子扔在地上所有骰子朝上一面的点数之和为s。输入n打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。示例 1:输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
示例 2:输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]限制1 n 11
【解答思路】 动态规划
第 1 步设计状态 n个骰子每个骰子6个面总情况数为6^n F(n,s)F(n,s)为当骰子数为n和为s的情况数量 第 2 步状态转移方程
第 3 步考虑初始化 int [][]dp new int[n1][6*n1];
第 4 步考虑输出 (double)dp[n][i])/Math.pow((double)6,(double)n); 第 5 步考虑是否可以状态压缩 是 时间复杂度O(N^2) 空间复杂度O(1)
class Solution {public double[] twoSum(int n) {int [][]dp new int[n1][6*n1];//边界条件for(int s1;s6;s)dp[1][s]1;for(int i2;in;i){for(int si;s6*i;s){//求dp[i][s]for(int d1;d6;d){//dp[i-1][s-d] i-1表示骰子数为 i-1 时点数和为 s-d 的次数筛子数为 i-1 时最小的点数和为 1 * (i - 1), 最大的点数和为 6 * (i -1)所以 s-d i-1, 如果 s-di-1那么数据非法得跳出本次循环if(s-di-1)break;//为0了dp[i][s]dp[i-1][s-d];}}}double total Math.pow((double)6,(double)n);double[] ans new double[5*n1];for(int in;i6*n;i){ans[i-n]((double)dp[n][i])/total;}return ans;}
}
空间优化 每个阶段的状态都只和它前一阶段的状态有关因此我们不需要用额外的一维来保存所有阶段。
用一维数组来保存一个阶段的状态然后对下一个阶段可能出现的点数 j 从大到小遍历实现一个阶段到下一阶段的转换。
public double[] twoSum(int n) {int []dp new int[6*n1];//边界条件for(int s1;s6;s)dp[s]1;for(int i2;in;i){for(int ji*6;ji;j--){dp[j] 0;for(int d1;d6;d){if(j-di-1)break;dp[j]dp[j-d];}}}double total Math.pow((double)6,(double)n);double[] ans new double[5*n1];for(int in;i6*n;i){ans[i-n]((double)dp[i])/total;}return ans;}【总结】
1. 动态规划流程
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
2. 动态规划牛逼 概率题活生生变成动态规划
参考链接https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/nge-tou-zi-de-dian-shu-dong-tai-gui-hua-ji-qi-yo-3/ 参考链接https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/dong-tai-gui-hua-by-shy-14/
