LC contest 149 (记录ing

比较难过的就是第二题, 明明做对了, 但是因为非常智障的问题一直没过.
第二题链接: 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;
    }
}