自学内容网 自学内容网

【动态规划-分组背包】力扣1155. 掷骰子等于目标和的方法数

这里有 n 个一样的骰子,每个骰子上都有 k 个面,分别标号为 1 到 k 。

给定三个整数 n、k 和 target,请返回投掷骰子的所有可能得到的结果(共有 kn 种方式),使得骰子面朝上的数字总和等于 target。

由于答案可能很大,你需要对 10^9 + 7 取模。

示例 1:
输入:n = 1, k = 6, target = 3
输出:1
解释:你掷了一个有 6 个面的骰子。
得到总和为 3 的结果的方式只有一种。

示例 2:
输入:n = 2, k = 6, target = 7
输出:6
解释:你掷了两个骰子,每个骰子有 6 个面。
有 6 种方式得到总和为 7 的结果: 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

动态规划

static constexpr int MOD = 1e9+7;

class Solution {
public:
    int numRollsToTarget(int n, int k, int target) {
        vector<int> dp(target+1);
        dp[0] = 1;
        for(int i = 0; i < n; i++){
            for(int j = target; j >= 0; j--){
                dp[j] = 0;
                for(int x = 1; x <= k; x++){
                    if(j >= x){
                        dp[j] = (dp[j] + dp[j-x]) % MOD;
                    }
                }
            }
        }
        return dp[target];
    }
};

时间复杂度:O(n⋅k⋅target),即为动态规划需要的时间。
空间复杂度:O(n⋅target) 或 O(target),即为动态规划需要的空间。

分组背包:同一组内的物品至多/恰好选一个。

在这道背包问题中,采用了滚动数组的方式来优化空间。
首先我们先定义一个向量dp[j],含义是目标和为j的时候的方案数。
然后初始化dp[0]=1。
首先我们先遍历每个骰子,也就是遍历i,然后接着倒序循环从target到0的目标和,并且在每次第二层循环的时候,令dp[j] = 0,最后循环骰子可能的点数x。

当我们已经确定了某个骰子i的时候,在他之前的前i-1个骰子,已经记录到了可能产生的目标和中,所以我们在计算第i个骰子可能产生的目标和的时候,是依赖于之前骰子产生的目标和。由于骰子只能投一次,且在下面的状态转移方程dp[j] = (dp[j] + dp[j-x]) % MOD;中,dp[j]代表的是可能产生的目标和,这取决于这次骰子的点数x,dp[j-x]取决于之前骰子产生的目标和。

我们需要注意的是,我们需要在计算产生的目标和j的方法数之前,令dp[j] = 0,使结果正确。这是因为当进入第 i 次投掷循环时,我们要重新计算所有可能的点数总和。每次投掷都会通过考虑当前骰子数(x)的影响,更新 dp[j]。如果不重置 dp[j],它会保留前一次计算的值,从而导致错误的累积计算。

最后返回dp[target]即可。


原文地址:https://blog.csdn.net/sjsjs11/article/details/142565085

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!