Dice Throw | GFG | Number Of Dice Rolls With Target Sum | LeetCode | Algorithm Explanation by alGOds

In this video, Achint has explained the optimized approach for solving the question #DiceThrow from #GeeksForGeeks and #NumberOfDiceRollsWithTargetSum from #LeetCode using Dynamic Programming.
Question Link - practice.geeksforgeeks.org/pr...
C++ Solution for Reference - ide.codingblocks.com/s/248384
Feel free to ask any of your doubts and discuss your attempts related to this question in the comments section 😇.
Join this telegram channel for regular updates : t.me/alGOdsCZcams
Join this telegram group for doubts and discussions : t.me/joinchat/PqjeMhz0MBR-tg3...
Do like and subscribe to our channel and click the bell icon so you don’t miss any future videos!!.
Don’t forget to tell us about the Questions you need an explanatory video for in the comments section. We’ll definitely take care of it😁.
Here is the Subscription Link : / algods99
Connect with us on Gmail : [e-mail]
The contributors to this channel and their profile links are enlisted below
1) Vishesh Aggarwal:
LinkedIn :- / vishesh-aggarwal-830b5...
2) Vaibhav Varshney:
LinkedIn :- / vaibhav-varshney
3) Vagish Yagnik:
LinkedIn :- / vagish-yagnik-9203b0172
4) Vishesh Jain:
LinkedIn :- / vishesh-jain-138097174
5) Achint Dawra:
LinkedIn :- / achint-dawra-ba9550168
6) V Sriram:
LinkedIn :- / sriram-v-08b098170
7) Varun Bajlotra:
LinkedIn :- / varun-bajlotra-17715a170
8) Vikas Yadav:
LinkedIn :- / vikas-yadav-b432b5107

[@alGOds99]

Join this telegram channel for regular updates : t.me/alGOdsCZcams
Join this telegram channel for doubts and discussions : t.me/joinchat/PqjeMhz0MBR-tg31OK2Dsg

[@anshulbatra8967]

Achint...you are amazing personality. I can't believe how you made complex things so easy through your explanation. Love you ❤️ guys.

[@kashavisharma6668]

Amazinggggg explanation 🙌🙌

[@davidakoji3696]

Best explanation. Nice work.

[@pushkardureja6863]

one of the best explaination for this ques........ earned a sub :0

[@raj_kundalia]

Amazing explanation!

[@aakankshajaiswal9770]

Was very helpful in understanding the solution. Thankyou! Below is my code in python:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
mod = 10**9 + 7

dp = [1] + [0]*target # dp[0] must be 1 because we can reach target 0 in 1 way, array size - target + 1
for dice in range(1, n + 1): # run dice from 1 to n
pre = dp[:] # use to store copy of previous array
dp = [0]*(target + 1) # make current array 0 to avoid previous feedback
for face in range(1, k + 1): # face loop before target, to get combinations (121 is same as 211)
for target_sum in range(face, target + 1): # run from face to avoid target_sum - face becoming negative
dp[target_sum] += pre[target_sum - face]
return dp[target] % mod

[@MrThepratik]

nice explaination , yeah when the target is > largest face value , it becomes interesting to just consider summing upto target-f

[@rahgurung]

Some good quality work is here, Thanks for walking me through the 2d matrix example. Earned a subscriber.

[@alGOds99]

Awesome, thank you!

[@tanujsaini3993]

Nice work Achint bhai 👍🏻👍🏻
All the best

[@alGOds99]

Thank you so much 😀

[@hrishikeshkonderu1638]

Nice explanation bro

[@adk920]

Thanks for the walkthrough!

[@alGOds99]

Glad to help Welcome :)

[@arshagrawal3036]

Thanx for the visualisation!
Though the time complexity can be reduce by using a prefix sum of the previous row as we would require always sum from i-(num of faces) to i. Also we can reduce space complexity as we would only need previous array only.
This would make the overall time complexity as O(n*target) and space complexity as O(target)

[@kumarkrishna7274]

wow Great and Easy to understand Explanation. 👌

[@alGOds99]

Glad you liked it

[@ashishchawla1243]

Great Explanation. Had to subscribe...

[@alGOds99]

Thankyou :)

[@piyushyadav7077]

good explanation

[@arpit_singh10]

thanks bro!!

[@alGOds99]

Happy to help :)

[@khawajausmannadeem]

Excellent Explanation

[@alGOds99]

Glad you liked it.Keep watching :)

[@narendratrivedi8113]

1k soon bhaiya😍😍

[@Panda-W-T-F]

Well explained bro 👍🏻👍🏻

[@alGOds99]

Glad you liked it

[@sparkle_batra]

Well explained 👌

[@alGOds99]

Glad you liked it

[@bobobob1230]

*when OP solves a leetcode problem without a solution* here king you dropped this 👑

[@anshikaaggarwal7982]

Very well explained 👍

[@alGOds99]

Glad it was helpful!

[@sakthinatesan2996]

Shouldn't the time complexity be O(dices * target * faces). Because for each (dices, target) we have to find the sum of dice-1 with 1..f faces.

[@alGOds99]

Yeah Sakthi, we have already corrected that error.Thankyou

[@anitachaudhary1004]

Wow nice explanation 👏👍

[@alGOds99]

Glad you liked it :)

[@pruthvirajk6019]

Can you just explain why this is not equal to subset sum problem becuase we are given 1 to m numbers and we are asked to form a sum equal to X where each and every number can be used more than once.Same thing here right.

[@alGOds99]

Yeah,this analogy is correct but another limitation you need to add is that although the number can be used more than once but not more than "n" times and also you need to select exactly "n" numbers in the range [1,m] such that they sum upto X.

[@ashishchawla1243]

That's what I thought initially but it cannot be solved using subset sum. Because even if you use the subset sum inspired from the unbounded knapsack that allows to have repeat values still the order in which the numbers appear on the dice will be an issue.
For example :-
m =4
n =3
x =5
The subset sum will give the answer 2.
2,2,1 and 3,1,1
whereas the answer should be 6
2,2,1
2,1,2
1,2,2
3,1,1
1,3,1
1,1,3

[@ashishchawla1243]

@@alGOds99 This can be taken care using this code by introducing an extra argument c which keeps count of how many dice rolls are remaining but still order matters which we cannot solve using subset sum.
Code:-
a = [x+1 for x in range(m)]
S = Target Sum
n = m or len(a)
c = number of dice throws left
def ss(a,S,n,c):
if c > S:
return 0
if c == S:
return 1
if c == 0:
return 0
if S == 0:
return 1
elif n == 0:
return 0
else :
if a[n-1]

[@pleasesirmorevideos4684]

this prob is super easy with memorization + recursion

[@dataman4503]

Yes, that too with same complexities.
I really don't understand why are people choosing Tabulation method instead of Memoization.

[@dpshock3925]

Where was dat 8 sum number?

[@srajankishorgupta1011]

I came here from your comment on the leetcode discussion forum. Thanx.

[@alGOds99]

Glad it was helpful :)

[@abhi4unme2002]

The key problem is to find out how we decided on 2d array for DP. How one will get the intuition for any other random problem to use 2D or 1D or 3D array? If anyone can teach this, then there will not be any need of such videos.

[@manthanmahajan5612]

ANSWER THIS PLEASE !!!!!!!!!!!
Assume you are rolling two six-sided dice, each side having an equal chance of occurring. Write a function my_monopoly_dice(), where the output is the sum of the values of the two dice thrown but with the following extra rule: if the two dice rolls are the same, then another roll is made, and the new sum added to the running total. For example, if the two dice show 3 and 4, then the running total should be 7. If the two dice show 1 and 1, then the running total should be 2 plus the total of another throw. Rolls stop when the dice rolls are different.

[@AnikashChakraborty]

DP is best explained with Top Down approach. I would suggest explain that as well

[@alGOds99]

Noted ! We will try explaining that too :)

[@HornOKPlease]

This guy is so cute