请选择 进入手机版 | 继续访问电脑版
MSIPO技术圈 首页 IT技术 查看内容

力扣 1155. 掷骰子等于目标和的方法数(动态规划-java)

2023-07-13

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/number-of-dice-rolls-with-target-sum

题目描述

这里有 n 个一样的骰子,每个骰子上都有 k 个面,分别标号为 1 到 k 。
给定三个整数 n , k 和 target ,返回可能的方式(从总共 kn 种方式中)滚动骰子的数量,使正面朝上的数字之和等于 target 。
答案可能很大,你需要对 109 + 7 取模 。

示例 1:
输入:n = 1, k = 6, target = 3
输出:1
解释:你扔一个有6张脸的骰子。
得到3的和只有一种方法。

示例 2:
输入:n = 2, k = 6, target = 7
输出:6
解释:你扔两个骰子,每个骰子有6个面。
得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。

示例 3:
输入:n = 30, k = 30, target = 500
输出:222616187
解释:返回的结果必须是对 109 + 7 取模。

提示:
1 <= n, k <= 30
1 <= target <= 1000

动态规划

分组背包不仅仅有「组内物品最多选择一个」的情况,还存在「组内物品必须选择一个」的情况。
对于本题,可以将每个骰子看作一个物品组,且每次 必须 从物品组中选择一个物品(所掷得的数值大小视作具体物品)。

这样就把问题转换为:用d 个骰子(物品组)进行掷,掷出总和(取得的总价值)为的方案数。
虽然,我们还没专门讲过「背包问题求方案数」,但基本分析与「背包问题求最大价值」并无本质区别。
我们可以套用「分组背包求最大价值」的状态定义来微调:
f[i][j] 表示:表示考虑前i 个物品组,凑成价值为j 的方案数。

了方便,我们令物品组的编号从 开始,因此有显而易见的初始化条件
f[0][0] = 1;代表在不考虑任何物品组的情况下,只有凑成总价值为0 的方案数为 1,凑成其他总价值的方案不存在。
不失一般性考虑 f[i][j]f[i][j] 该如何转移,也就是考虑第 ii 个物品组有哪些决策。

根据题意,对于第 i 个物品组而言,可能决策的方案有:

第 i 个骰子的结果为 1,有 f[i][j]=f[i−1][j−1]

第 i 个骰子的结果为 2,有 f[i][j]=f[i−1][j−2]

...

第 ii 个骰子的结果为 m,有 f[i][j]=f[i−1][j−m]

f[i][j]f[i][j] 则是上述所有可能方案的方案数总和,即有:

f[i][j]=∑k=1mf[i−1][j−k],j>=k

代码演示

class Solution {
     int mod = (int)1e9+7;

      public int numRollsToTarget(int n, int m, int t) {
        int[][] dp = new int[n + 1][t + 1];
         dp[0][0] = 1;
        //骰子可以选的次数
        for (int i = 1; i <= n;i++){
            //需要凑够的点数大小
            for (int j = 0; j <= t;j++){
                //枚举所有的点数.
                for (int k = 1;k <= m;k++){
                    if (j >= k){
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
                    }
                }
            }
        }
        return dp[n][t];
    }
}

空间压缩

class Solution {
    int mod = (int)1e9+7;
    public int numRollsToTarget(int n, int m, int t) {
        int[] f = new int[t + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = t; j >= 0; j--) {
                f[j] = 0;
                for (int k = 1; k <= m; k++) {
                    if (j >= k) {
                        f[j] = (f[j] + f[j-k]) % mod;
                    }
                }
            }
        } 
        return f[t];
    }
}

动态规划专题

leetcode72. 编辑距离

leetcode514. 自由之路

leetcode474. 一和零

leetcode97. 交错字符串

leetcode464. 我能赢吗

leetcode902. 最大为 N 的数字组合

相关阅读

热门文章

    手机版|MSIPO技术圈 皖ICP备19022944号-2

    Copyright © 2024, msipo.com

    返回顶部