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

Categories:

题目描述
思路分析
1. 解法一：动态规划（推荐）
相似题目

题目描述

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

思路分析

解法一：动态规划（推荐）

核心思路：

dp[j] 表示当前投掷若干个骰子后，点数和为某值的概率。

每增加一个骰子，相当于与 [1..6] 做一次卷积。

用滚动数组迭代更新，避免二维数组。

复杂度分析：

时间复杂度：O(n^2)，其中 n 表示骰子个数。

空间复杂度：O(n)，用于存储概率数组。

class Solution {
    public double[] dicesProbability(int n) {
        double[] dp = new double[6];
        for (int i = 0; i < 6; i++) {
            dp[i] = 1.0 / 6.0;
        }

        for (int dice = 2; dice <= n; dice++) {
            double[] next = new double[5 * dice + 1];

            for (int j = 0; j < dp.length; j++) {
                for (int face = 1; face <= 6; face++) {
                    // 卷积累加，索引偏移为 face - 1
                    next[j + face - 1] += dp[j] / 6.0;
                }
            }

            dp = next;
        }

        return dp;
    }
}

func dicesProbability(n int) []float64 {
    dp := make([]float64, 6)
    for i := 0; i < 6; i++ {
        dp[i] = 1.0 / 6.0
    }

    for dice := 2; dice <= n; dice++ {
        next := make([]float64, 5*dice+1)

        for j := 0; j < len(dp); j++ {
            for face := 1; face <= 6; face++ {
                // 卷积累加，索引偏移为 face - 1
                next[j+face-1] += dp[j] / 6.0
            }
        }

        dp = next
    }

    return dp
}

相似题目

题目	难度	考察点
1155. 掷骰子等于目标和的方法数	中等	动态规划
377. 组合总和 Ⅳ	中等	动态规划
494. 目标和	中等	动态规划
518. 零钱兑换 II	中等	动态规划
279. 完全平方数	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/22511007