엔지니어 게시판
LeetCode 솔루션 분류

1155. Number of Dice Rolls With Target Sum

컨텐츠 정보

본문

[Medium] 

You have n dice and each die has k faces numbered from 1 to k.

Given three integers nk, and target, return the number of possible ways (out of the kn total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.


You have n dice and each die has k faces numbered from 1 to k.

Given three integers nk, and target, return the number of possible ways (out of the kn total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 109 + 7.

 

Example 1:

Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.

Example 2:

Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 109 + 7.

 

Constraints:

  • 1 <= n, k <= 30
  • 1 <= target <= 1000

관련자료

댓글 1

Coffee님의 댓글

  • 익명
  • 작성일
Runtime: 17 ms, faster than 82.26% of Java online submissions for Number of Dice Rolls With Target Sum.
Memory Usage: 41.6 MB, less than 78.98% of Java online submissions for Number of Dice Rolls With Target Sum.

class Solution {
    
    private final int MODULO = 1000000007;
    private Integer[][] cache;
    
    private int n = 0;
    private int k = 0;
    
    public int numRollsToTarget(int n, int k, int target) {
        
        this.n = n;
        this.k = k;
        this.cache = new Integer[n+1][target+1];
        return dp(0, target);
        
        
    }
    
    public int dp(int i, int remain){
        // escape condition
        if(i == n && remain == 0){
            return 1;  
        } 
        
        if(i > n || remain < 0){
            return 0;  
        } 
        
        if(cache[i][remain] != null){
            return cache[i][remain];
        } 
        
        int ans = 0;
        for(int num = 1; num <= k; num++) {
            ans += dp(i + 1, remain - num);
            ans %= MODULO;
        }
        
        return cache[i][remain] = ans;
    }
}
전체 396 / 13 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 161 명
  • 오늘 방문자 4,279 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,048 명
알림 0