【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

这篇具有很好参考价值的文章主要介绍了【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯

【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

题目链接

剑指 Offer 60. n个骰子的点数

题目描述

把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. 为了能够让同学们更好的理解这个过程,我特意将整个思考的过程以及作图的过程都绘制在下面这张图中,希望可以通过下面这张图更好的帮助你理解整个过程,大家可以结合这张图来理解整个题目的求解思路。

【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

实现代码
class Solution {

    private int n;
    List<Double> list;
    public double[] dicesProbability(int n) {
        this.n=n;
        list=new ArrayList<>();
        int start=n,end=n*6;
        
        process(start,end,n);
        double[] ans=new double[list.size()];
        for(int i=0;i<list.size();i++){
            ans[i]=list.get(i);
        }
        return ans;
    }

    public void process(int start,int end,int cnt){
        for(int i=start;i<=end;i++){
            int count=dfs(i,cnt);
            list.add(1.0/Math.pow(6,n)*count);
        }
    }

    public int dfs(int target,int cnt){
        if(cnt==0) return target==0?1:0;
        int count=0;
        for(int i=1;i<=6;i++){
           count+=dfs(target-i,cnt-1); 
        }
        return count;
    }
}
运行结果

【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】


记忆化搜索

求解思路
  1. 根据我们递归的分析,在递归的过程中会产生重复的子过程,所以我们想到了加一个缓存表,也就是我们的记忆化搜索。
实现代码
class Solution {

    private int n;
    private List<Double> list;
    public double[] dicesProbability(int n) {
        this.n=n;
        list=new ArrayList<>();
        int start=n,end=n*6;
        process(start,end,n);
        double[] ans=new double[list.size()];
        for(int i=0;i<list.size();i++){
            ans[i]=list.get(i);
        }
        return ans;
    }

    public void process(int start,int end,int cnt){
        int[][] dp=new int[12*6][12];
        for(int i=0;i<dp.length;i++) Arrays.fill(dp[i],-1);
        for(int i=start;i<=end;i++){
            int count=dfs(i,cnt,dp);
            list.add(1.0/Math.pow(6,n)*count);
        }
    }

    public int dfs(int target,int cnt,int[][] dp){
        if(target<0) return 0;
        if(cnt==0) return dp[target][cnt]=target==0?1:0;
        if(dp[target][cnt]!=-1) return dp[target][cnt];
        int count=0;
        for(int i=1;i<=6;i++){
           count+=dfs(target-i,cnt-1,dp); 
        }
        return dp[target][cnt]=count;
    }
}
运行结果

【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】


动态规划

求解思路
  1. 接下来我们根据之前的递归思路以及记忆化缓存改写动态规划。
实现代码
class Solution {

    private int n;
    private List<Double> list;
    public double[] dicesProbability(int n) {
        this.n=n;
        list=new ArrayList<>();
        int start=n,end=n*6;
        process(start,end,n);
        double[] ans=new double[list.size()];
        for(int i=0;i<list.size();i++){
            ans[i]=list.get(i);
        }
        return ans;
    }

    public void process(int start,int end,int cnt){
        int[][] dp=new int[12*6][12];
        dp[0][0]=1;
        for(int target=1;target<=end;target++){
            for(int k=1;k<=cnt;k++){
                int count=0;
                for(int i=1;i<=6;i++){
                    if(target-i>=0) count+=dp[target-i][k-1]; 
                }
                dp[target][k]=count;
            }
            if(target>=start){
                list.add(1.0/Math.pow(6,n)*dp[target][cnt]);
            }   
        }
    }
}
运行结果

【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】


共勉

最后,我想送给大家一句一直激励我的座右铭,希望可以与大家共勉!
【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】

【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】文章来源地址https://www.toymoban.com/news/detail-418574.html

到了这里,关于【LeetCode: 剑指 Offer 60. n个骰子的点数 | 数学+ 暴力递归=>记忆化搜索=>动态规划】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode: 剑指 Offer II 090. 环形房屋偷盗(打家窃舍) | 暴力递归=>记忆化搜索=>动态规划】

    🍎作者简介:硕风和炜,CSDN-Java领域新星创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎 🍎座右铭:人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯🎯 大家再看这道题目之前,

    2023年04月14日
    浏览(45)
  • 每天一道leetcode:剑指 Offer 64. 求1+2+…+n(中等&递归)

    求 1+2+...+n ,要求不能使用乘除法、for、while、if、else、switch、case等及条件判断语句(A?B:C)。 1 = n = 10000 使用递归,我们马上的想法是: 或者: 但是题目要求不能出现if、A?B:C这样的,所以,我们只能直接返回什么东西。返回什么?返回n。只不过n要进行自加

    2024年02月12日
    浏览(50)
  • 每天一道leetcode:剑指 Offer 34. 二叉树中和为某一值的路径(中等&图论&深度优先遍历&递归)

    给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 树中节点总数在范围 [0, 5000] 内 -1000 = Node.val = 1000 -1000 = targetSum = 1000 使用递归深度优先遍历,使用前序遍历,在遍历途

    2024年02月12日
    浏览(48)
  • 剑指 Offer 49. !!丑数 (找数学规律)

    参考资料 注意到丑数 只包含 质因子是2,3,5。所以,丑数必然是有这三个数若干次相乘得到。而丑数序列保持从小到大,所以当前的丑数必然是前面某个丑数乘2或者3或者5得到的。

    2024年02月15日
    浏览(64)
  • 【LeetCode】剑指 Offer(21)

    目录 题目:剑指 Offer 39. 数组中出现次数超过一半的数字 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 40. 最小的k个数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题,我的思路是直接排序, 然后返回中间

    2023年04月10日
    浏览(65)
  • 【LeetCode】剑指 Offer(28)

    目录 题目:剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - I. 二叉树的深度 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 55 - II. 平衡二叉树 - 力扣(Leetcode) 题目的接

    2023年04月24日
    浏览(51)
  • 【LeetCode】剑指 Offer(25)

    目录 题目:剑指 Offer 49. 丑数 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 丑数这道题用到一点动态规划的思想, 具体思路如下: 根据题意: 如果说第一个丑数是一,包含质因子 2、3 和 5 的数称作丑数, 那么我们发现,之后的丑数: 都是前

    2023年04月09日
    浏览(51)
  • 【LeetCode】剑指 Offer(26)

    目录 题目:剑指 Offer 51. 数组中的逆序对 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这一道题,我的思路是用双指针暴力求解, 但这个数组长度,O(N^2)的时间复杂度肯定是不可能把所有样例跑完, 看了大佬的思路,用的是归并排序,(如果不

    2023年04月11日
    浏览(42)
  • 【LeetCode】剑指 Offer(27)

    目录 题目:剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 那么这道题呢, 如果只是作为一道题,或者说笔试题, 我们当然是二话不说直接暴力拿下, 来看代码: 是的,就是这么简单,三行代码暴力拿下

    2023年04月13日
    浏览(44)
  • 【LeetCode】剑指 Offer <二刷>(4)

    目录 题目:剑指 Offer 09. 用两个栈实现队列 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 10- I. 斐波那契数列 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 这道题我用 C++ 写的时候是比较简单顺手的,用 STL 可以

    2024年02月10日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包