Dice Throw | GFG | Number Of Dice Rolls With Target Sum | LeetCode | Algorithm Explanation by alGOds
Вставка
- Опубліковано 18 вер 2024
- 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.geeks...
C++ Solution for Reference - ide.codingbloc...
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/alGOdsYou...
Join this telegram group for doubts and discussions : t.me/joinchat/...
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 : algods.99@gmail.com
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
![Maximum sum of i*arr[i] among all rotations of given array | GFG | Algorithm Explanation by alGOds](http://i.ytimg.com/vi/3YNs_Ggqb-Q/mqdefault.jpg)
Join this telegram channel for regular updates : t.me/alGOdsUA-cam
Join this telegram channel for doubts and discussions : t.me/joinchat/PqjeMhz0MBR-tg31OK2Dsg
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
Achint...you are amazing personality. I can't believe how you made complex things so easy through your explanation. Love you ❤️ guys.
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)
Nice work Achint bhai 👍🏻👍🏻
All the best
Thank you so much 😀
Amazinggggg explanation 🙌🙌
Some good quality work is here, Thanks for walking me through the 2d matrix example. Earned a subscriber.
Awesome, thank you!
Great Explanation. Had to subscribe...
Thankyou :)
Amazing explanation!
Excellent Explanation
Glad you liked it.Keep watching :)
Best explanation. Nice work.
*when OP solves a leetcode problem without a solution* here king you dropped this 👑
wow Great and Easy to understand Explanation. 👌
Glad you liked it
nice explaination , yeah when the target is > largest face value , it becomes interesting to just consider summing upto target-f
Nice explanation bro
Thanks for the walkthrough!
Glad to help Welcome :)
one of the best explaination for this ques........ earned a sub :0
thanks bro!!
Happy to help :)
Well explained 👌
Glad you liked it
Very well explained 👍
Glad it was helpful!
good explanation
Wow nice explanation 👏👍
Glad you liked it :)
Well explained bro 👍🏻👍🏻
Glad you liked it
this prob is super easy with memorization + recursion
Yes, that too with same complexities.
I really don't understand why are people choosing Tabulation method instead of Memoization.
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.
Yeah Sakthi, we have already corrected that error.Thankyou
I came here from your comment on the leetcode discussion forum. Thanx.
Glad it was helpful :)
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.
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.
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
@@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]
1k soon bhaiya😍😍
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.
DP is best explained with Top Down approach. I would suggest explain that as well
Noted ! We will try explaining that too :)
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.
This guy is so cute
Where was dat 8 sum number?