1155. Number of Dice Rolls With Target Sum

Description:

You have d dice and each die has f faces numbered 1, 2, ..., f. You are given three integers d, f, and target.

Return the number of possible ways (out of fd total ways) modulo 109 + 7 to roll the dice so the sum of the face-up numbers equals target.

'''
[1] brute force)

def numRollsToTarget(d,f,target):
    def bf(cur_dice,max_dice,face,cur_sum,target):
        if cur_dice == max_dice:
            if cur_sum==target:
                return 1
            return 0
        
        total_count=0
        for i in range(1,face+1):
            total_count += bf(cur_dice+1,max_dice,face,cur_sum+i,target)
        
        return total_count%1000000007
        
        
    return bf(0,d,f,0,target)
    
- T/C: O(f^d)
- S/C: O(d) # for function-stack
'''

'''
[2] DP)

F(n,target) is the # of cases where making target value using n dice(s).

then, in the case n==2, target==7, and f==6
F(2,7)=F(1,1)+F(1,2)+F(1,3)+F(1,4)+F(1,5)+F(1,6)
=> F(n,target)= F(n-1,target-1)+F(n-1,target-2)+F(n-1,target-3)+...+F(n-1,target-f)

of course, there are some cases F(n,target)==0 (when f==2, d==1, target=3 / F(1,3)=0)

making dp_matrix, n==2, f==5, target 10

* below tabel is 0-indexed

  |  0   1   2   3   4   5   6   7   8   9
------------------------------------------
0 |  1   1   1   1   1   0   0   0   0   0   
1 |  0   1   2   3   4   5   4   3   2   1

row== the number of dices, col== every cases which making col_index(target)
then, dp[n-1][target-1] ==> answer


dp=[[0]*target for _ in range(d)]
        
        for col in range(target):
            if col < f:
                dp[0][col]=1
            else:
                dp[0][col]=0
        
        for row in range(1,d):
            for col in range(target):
                
                for above_col in range(col-f,col):
                    if above_col<0:
                        continue
                    dp[row][col]+=dp[row-1][above_col]
                    
        return dp[d-1][target-1]%1000000007
        
- T/C: O(d*f*target)
- S/C: O(d*target) # for dp_matrix
'''

'''
[3] DP - optimization)

I just need dp[row-1][col], which is an array, to make dp[row][col] array
so, not maintaining the whole dp_matrix, just keep just arrays

dp_above=[0 for _ in range(target)]
for col in range(target):
    if col < f:
        dp_above[col]=1
    else:
        dp_above[col]=0

for row in range(1,d):
    dp_tmp=[0 for _ in range(target)]
            
    for col in range(target):
        new_case=0
        for above_col in range(col-f,col):
            if above_col<0:
                continue
            else:
                new_case+=dp_above[above_col]
            dp_tmp[col]=new_case
        dp_above=copy.deepcopy(dp_tmp)
                    
return (dp_above[target-1])%1000000007
        
- T/C: O(d*f*target)
- S/C: O(2*target) # for dp_tmp, dp_above
'''


class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        dp_above=[0 for _ in range(target)]
        for col in range(target):
            if col < f:
                dp_above[col]=1
            else:
                dp_above[col]=0

        for row in range(1,d):
            dp_tmp=[0 for _ in range(target)]
            
            for col in range(target):
                new_case=0
                for above_col in range(col-f,col):
                    if above_col<0:
                        continue
                    else:
                        new_case+=dp_above[above_col]
                dp_tmp[col]=new_case
            dp_above=copy.deepcopy(dp_tmp)
                    
        return (dp_above[target-1])%1000000007