Leetcode discuss: 1155. Number of Dice Rolls With Target Sum

 August 26, 2021

Here is the link. 

C# | Dynamic programming | Two states

Aug. 26, 2021
Introduction
The algorithm can be solved using dynamic programming technique. I like to write down a small case study and explain how to solve it in 10 minutes.

Warmup practice
I chose to practice Leetcode premium, Amazon code assessment. I came cross the algorithm.
Two states, first one is how many dices thrown, second one is sum of those thrown dice face value.

For example, d = 1, f = 6, target = 3, define a dp two dimension C# array, new int[d + 1, target + 1].

Go through three for loops, first one is to work on dice count, next one is to work on dice face value, the third one is to work on summation value of all thrown dice.

My performance
Edge case, first dice only can contribute to dp[1, value], value is dice's value itself. After that, increment value based on dice - 1.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DiceSum
{
    class Program
    {
        static void Main(string[] args)
        {
            // test case: 1, 6, 3, result should be 1
            var result = NumRollsToTarget(1, 6, 3);
            result = NumRollsToTarget(2, 6, 7); 
        }

        /// <summary>
        /// states: 
        /// Dices used: 1 to d
        /// Target value from 1 to target 
        /// 
        /// </summary>
        /// <param name="d"></param>
        /// <param name="f"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static int NumRollsToTarget(int d, int f, int target)
        {
            var dp = new int[d + 1, target + 1];           

            for (int dice = 1; dice < d + 1; dice++)
            {
                for (int value = 1; value <= f; value++)
                {                                      
                    for (var sum = target; sum >= 1; sum--)
                    {
                        if (sum - value >= 0)
                        {                            
                            if (dice == 1)
                            {
                                if (sum == value)
                                {
                                    dp[dice, sum] = 1;
                                }
                            }
                            else
                            {
                                dp[dice, sum] += dp[dice - 1, sum - value];
                                dp[dice, sum] = dp[dice, sum] % (1000 * 1000 * 1000 + 7);
                            }
                        }
                    }
                }
            }

            return dp[d, target];
        }
    }
}