【每日一题】掷骰子等于目标和的方法数

本文主要是介绍【每日一题】掷骰子等于目标和的方法数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：动态规划
写在最后

Tag

【动态规划】【数组】

题目来源

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

题目解读

你手里有 n 个一样的骰子，每个骰子都有 k 个面，分别标号 1 到 n。给定三个整数 n，k 和 target，返回这个 n 个骰子正面朝上的数字组成 target 的所有方案数。答案可能很大，返回对 $1 e 9 + 7$ 取模后的值。

解题思路

方法一：动态规划

我们可以使用动态来解决本题。

状态

记 f[i][j] 表示使用 i 个骰子且数字和为 j 的方案数。

转移关系

我们可以枚举最后一个骰子的数字，数字的范围在 [1, k]，使用 i 个骰子组成的数字和为 j 的方案数为:

$f\left[ i,j \right] =\sum_{x=1}^k{f\left[ i-1 \right] \left[ j-k \right]}$

base case

f[0][0] = 1，计即我们还没有掷骰子，数字之和为 0 时的方案数。

最终返回

最终返回 f[n][target]，表示使用 n 个骰子正面朝上的数字组成 target 的所有方案数

实现代码

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

优化

注意观察状态转移方程，f[i][j] 只会从 f[i-1, ...] 转移过来，因此只需要存储第 i 行和第 i-1 行的值，使用两个一维数组代替二维数组进行转态转移。

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