比较难过的就是第二题, 明明做对了, 但是因为非常智障的问题一直没过.
第二题链接: https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/
先是一个非常智障的问题: 我以为10^9是Math.pow(10,9)...翻来覆去的改了半个小时.
然后因为long的overflow问题, 一直没有debug出来.因为每一步存储的时候都需要注意overflow! 所以每次在+, +=的时候注意都需要mod (10^9+7)
自己想的DFS解法
class Solution {
HashMap<String, Long> memo;
int MOD = 1000000000+7;
public int numRollsToTarget(int d, int f, int target) {
memo = new HashMap<>();
long res = helper(d, f, target);
System.out.println(res);
return (int)res%((int)(Math.pow(10,9)+7));
}
public long helper(int d, int f, int target){
if (d==0 && target==0) return 1;
else if (target<0||(target>f && d==1)||d<0) return 0;
String key = Integer.toString(d)+" "+Integer.toString(target);
if (memo.containsKey(key)) return memo.get(key);
long res= 0;
for(int i = 1;i<=f;i++){
res = (res + (helper(d - 1, f, target - i) % MOD)) % MOD;
}
memo.put(key, res);
return res;
}
}
动态规划解法: 参考GFG的做法或者参考roll dice (LintCode20 算dice概率那题的简化版本)
class Solution {
int MOD = 1000000000+7;
public int numRollsToTarget(int d, int f, int target) {
int [][]dp=new int[d+1][f*d+1];
if (target>f*d) return 0;
for(int i = 1;i<=f;i++){
dp[1][i] = 1;
}
for(int i=2;i<=d;i++){
for(int j=i;j<=i*f;j++){
int temp = 0;
for(int k=1;k<=f;k++){
if(j-k>=0){
temp= (temp+(dp[i-1][j-k])%MOD)%MOD;
}
}
dp[i][j]=temp;
}
}
return dp[d][target] % MOD;
}
}
