LeetCode 1155. 掷骰子等于目标和的方法数

Categories:

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

题目描述

✅ 1155. 掷骰子等于目标和的方法数

思路分析

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

核心思路：

dp[i][s] 表示投掷 i 个骰子和为 s 的方案数。

状态转移：枚举本次骰子的点数 face。

使用滚动数组减少空间。

复杂度分析：

时间复杂度：O(n _ k _ target)，其中 n 为骰子数，k 为面数。

空间复杂度：O(target)，使用滚动数组。

class Solution {
    public int numRollsToTarget(int n, int k, int target) {
        int mod = 1_000_000_007;
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            int[] next = new int[target + 1];
            for (int sum = 1; sum <= target; sum++) {
                long ways = 0;
                for (int face = 1; face <= k && face <= sum; face++) {
                    ways += dp[sum - face];
                }
                next[sum] = (int) (ways % mod);
            }
            dp = next;
        }

        return dp[target];
    }
}

func numRollsToTarget(n int, k int, target int) int {
	const mod = 1000000007
	cur := make([]int, target+1)
	cur[0] = 1

	for i := 1; i <= n; i++ {
		next := make([]int, target+1)
		for sum := 1; sum <= target; sum++ {
			ways := 0
			for face := 1; face <= k && face <= sum; face++ {
				ways = (ways + cur[sum-face]) % mod
			}
			next[sum] = ways
		}
		cur = next
	}

	return cur[target]
}

相似题目

题目	难度	考察点
377. 组合总和 Ⅳ	中等	动态规划
518. 零钱兑换 II	中等	动态规划
494. 目标和	中等	动态规划
1154. 一年中的第几天	简单	数学
279. 完全平方数	中等	动态规划

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/80978117