1155. 掷骰子的N种方法
这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, ..., f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。
示例 1：
输入：d = 1, f = 6, target = 3 输出：1
示例 2：
输入：d = 2, f = 6, target = 7 输出：6
示例 3：
输入：d = 2, f = 5, target = 10 输出：1
示例 4：
输入：d = 1, f = 2, target = 3 输出：0
示例 5：
输入：d = 30, f = 30, target = 500 输出：222616187
提示：
1 <= d, f <= 301 <= target <= 1000
因为自己动态规划学的不好，所以用记忆化搜索来做的
class Solution { int dp[35][1050];//计算结果 int vis[35][1050];//标记是否已经进行了计算 int F; int mod = 1e9+7; public: int DFS(int d,int tar){ //第d次选择，剩余tar if(d>tar) return 0; if(d ==0){ if(tar == 0) return 1; else return 0; } if(vis[d][tar]>0) return dp[d][tar]; //如果已经进行了计算，就返回结果 int ans = 0; for(int i =1;i<=F && i<=tar;i++){ ans+=DFS(d-1,tar-i); // ans%=mod; } vis[d][tar] = 1;//已经算出了结果，做一个标记 return dp[d][tar] = ans;//记忆化 } int numRollsToTarget(int d, int f, int target) { F = f; return DFS(d,target); } };