当前位置: 首页 > java >正文

剑指offer62_骰子的点数

骰子的点数


将一个骰子投掷 n 次,获得的总点数为 s,s 的可能范围为 n∼6n。

掷出某一点数,可能有多种掷法,例如投掷 2 次,掷出 3 点,共有 [1,2],[2,1] 两种掷法。

请求出投掷 n 次,掷出 n∼6n 点分别有多少种掷法。

数据范围

1≤n≤10

样例1
输入:n=1输出:[1, 1, 1, 1, 1, 1]解释:投掷1次,可能出现的点数为1-6,共计6种。每种点数都只有1种掷法。所以输出[1, 1, 1, 1, 1, 1]
样例2
输入:n=2输出:[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]解释:投掷2次,可能出现的点数为2-12,共计11种。每种点数可能掷法数目分别为1,2,3,4,5,6,5,4,3,2,1。所以输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

算法思路

核心思想是通过递推关系式逐步构建不同骰子数量下的点数分布。

关键步骤

  1. 初始化f[0][0] = 1 表示掷0个骰子时点数和为0的情况只有1种
  2. 递推计算
    • 对于第 i 个骰子(从1到n)
    • 对于可能的点数和 j(从1到6*i)
    • 考虑当前骰子可能出现的点数 k(1到6),累加上一轮 i-1 个骰子时点数和为 j-k 的情况数
  3. 收集结果:将掷 n 个骰子时所有可能的点数和(从n到6n)的情况数存入结果数组
时间复杂度
  • O(n²):外层循环n次,中层循环最多6n次,内层循环最多6次,总体复杂度为O(n*(6n)*6)=O(n²)
空间复杂度
  • O(n²):使用了一个(n+1)×(6n+1)的二维数组存储中间结果
class Solution {
public:vector<int> numberOfDice(int n) {vector<int> res;  // 存储最终结果// f[i][j]表示掷i个骰子时点数和为j的情况数vector<vector<int>> f(n + 1, vector<int>(6 * n + 1, 0));// 初始条件:掷0个骰子点数和为0的情况有1种f[0][0] = 1;// 动态规划递推for(int i = 1; i <= n; i++) {            // 逐个增加骰子数量for(int j = 1; j <= 6 * i; j++) {    // 当前可能的点数和范围for(int k = 1; k <= min(j, 6); k++) { // 当前骰子的点数// 当前情况数等于之前i-1个骰子时点数和为j-k的情况数之和f[i][j] += f[i - 1][j - k];}}}// 收集n个骰子的所有可能结果(点数和从n到6n)for(int i = n; i <= n * 6; i++) {res.push_back(f[n][i]);}return res;}
};

实例演示

输入n = 2
输出[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]

执行过程

  1. 初始化:f[0][0] = 1
  2. 掷1个骰子:
    • f[1][1] = f[0][0] = 1
    • f[1][2] = f[0][1] = 1
    • f[1][6] = f[0][5] = 1
  3. 掷2个骰子:
    • f[2][2] = f[1][1] = 1
    • f[2][3] = f[1][2] + f[1][1] = 2
    • f[2][4] = f[1][3] + f[1][2] + f[1][1] = 3
    • f[2][12] = f[1][6] = 1
  4. 最终结果:f[2][2]f[2][12]的值[1,2,3,4,5,6,5,4,3,2,1]

输出结果[1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]


关键点总结

  1. 动态规划思想:将问题分解为子问题,利用已解决的子问题结果求解当前问题
  2. 状态定义f[i][j]表示掷i个骰子时点数和为j的情况数
  3. 递推关系:当前状态由前一轮的多个状态决定(取决于当前骰子的点数)
  4. 边界处理:注意点数和的最小值(n)和最大值(6n)
http://www.xdnf.cn/news/15409.html

相关文章:

  • Vue3入门-指令
  • brupsuite使用中遇到的一些问题(bp启动后浏览器无法连接)/如何导入证书
  • 智能体技术深度解析:从概念到企业级搭建指南
  • 安全参綉25暑假第一次作业
  • Student后台管理系统查询接口
  • CentOS服务器安装Supervisor使队列可以在后台运行
  • GAMES101 lec2-数学基础1(线性代数)
  • 为何说分布式 AI 推理已成为下一代计算方式
  • 特殊的整数-水仙花数
  • 【c++】c++11新特性(右值引用和移动语义)
  • Java报表导出框架
  • 详解BIO,NIO,AIO
  • 【git fetch submodule报错】Errors during submodule fetch 如何解决?
  • 【Java EE】多线程-初阶 认识线程(Thread)
  • urlencode、html实体编码、unicode
  • 进程---基础知识+命令+函数(fork+getpid+exit+wait+exec)
  • ACL流量控制实验
  • 12.如何判断字符串是否为空?
  • 记字节前端面试一道简单的算法题
  • 游戏玩法的专利博弈
  • 大话数据结构之 <链表>(C语言)
  • 使用 keytool 在服务器上导入证书操作指南(SSL 证书验证错误处理)
  • 【DOCKER】-4 dockerfile镜像管理
  • Python数据容器-通用功能
  • grpo nl2sql qwen3 模型强化学习训练有效果的成立条件有哪些
  • java--ThreadLocal创建以及get源码解析
  • 131. Java 泛型 - 目标类型与泛型推断
  • RNN(循环神经网络)
  • js与vue基础学习
  • Cesium源码打包