Amazing solution man. It took me some time to understand the values of l and r, but finally understood after doing with pen and paper. Its nice that u leave some blank spaces so that we can think, instead of spoon feeding. Keep growing.👍👍👍
For overflows - I am making sure I take mod on every addition so that the number never goes beyond given MOD. Why I am subtracting - because every number is modulus M, the left part can be smaller than the right. And you cannot use negative number with mod, hence I added mod (as adding mod is equal to adding zero if you take MOD).
Can you also explain the last problem from the biweekly 136 contests last problem that is using tree rerouting[DP on Trees] would love to see your explanation on that topic :)
@@codingmohan Why max though? if the loop in recursion is starting from prv1, why cant it just be prv1(l = prv1) everything excluding this part was clear. I am gonna have to rewatch this multiple times.
Sorry I didn't realise that it could be a long jump. For you to help - you can simply code the entire thing in 2D version and then you will realise that you are only using the previous index values itself. Try that once.
can anyone provide optimization of this using 2d DP-class Solution { public: int mod = 1e9 + 7; int dp[2001][1001]; int countOfPairs(vector& nums) { int n = nums.size(); memset(dp,0,sizeof(dp)); for(int p1=0;p1=0;idx--){ for(int p1=0;p1= 1 ? nums[idx-1]-p1 :1000); for (int i = p1; i = val) { ans = (ans + dp[idx + 1][i]) % mod; } } dp[idx][p1]=ans; } } return dp[0][0]; } };
Common pattern in LeetCode contests - prefix sums DP.
Can you show me similar problems
Amazing solution man. It took me some time to understand the values of l and r, but finally understood after doing with pen and paper. Its nice that u leave some blank spaces so that we can think, instead of spoon feeding. Keep growing.👍👍👍
Excelent Explanation Thanks a lot. also thanks to clear why I need to think in a bottom up approach. #kudus #salute and #respect.
very nice explanation, thanks
Can you tell me about your pratice strategy from beginner to leetcode master ?
please xplain how you are handling the overflows. Why you are adding the mod while getting the range sum.
For overflows - I am making sure I take mod on every addition so that the number never goes beyond given MOD.
Why I am subtracting - because every number is modulus M, the left part can be smaller than the right. And you cannot use negative number with mod, hence I added mod (as adding mod is equal to adding zero if you take MOD).
Super Explanation . Thanks a lot.
Can you also explain the last problem from the biweekly 136 contests last problem that is using tree rerouting[DP on Trees] would love to see your explanation on that topic :)
Thanku bhaiya very good explanation
bro great explanination. Just a request, can you please use dark mode for these notes, it really hurts the eyes
I started with full black but based on feedback I changed.
The issue is that in black background, the free colors doesn't works well.
do we actually save time when we take out the prv2 parameter since it’s dependent on the first 2 anyways?
We do because previously we would have to compute more states. Another way to visualize is - look at the 3D dp vs 2D dp).
Bhaiya biweekly bhi discuss kr do please
l = max(prv1, nums[i] - prv2)
I didnt understand why we are doing this
why to include prv1?
Because the condition in the first array needs to be satisfied as well.
In the recursion look at the starting index of the loop.
@@codingmohan Why max though? if the loop in recursion is starting from prv1, why cant it just be prv1(l = prv1)
everything excluding this part was clear.
I am gonna have to rewatch this multiple times.
There is a "if" condition in the loop. Try to think into that direction
in the end solution was not good just you made 2d into 1d
Sorry I didn't realise that it could be a long jump.
For you to help - you can simply code the entire thing in 2D version and then you will realise that you are only using the previous index values itself. Try that once.
No, i got the intuition this is just a space otmization but wanna complete first with 2d dp
can anyone provide optimization of this using 2d DP-class Solution {
public:
int mod = 1e9 + 7;
int dp[2001][1001];
int countOfPairs(vector& nums) {
int n = nums.size();
memset(dp,0,sizeof(dp));
for(int p1=0;p1=0;idx--){
for(int p1=0;p1= 1 ? nums[idx-1]-p1 :1000);
for (int i = p1; i = val) {
ans = (ans + dp[idx + 1][i]) % mod;
}
}
dp[idx][p1]=ans;
}
}
return dp[0][0];
}
};
int countOfPairs(vector& nums)
{
int n = nums.size();
vector dp(n,vector(1001,0));
for(int i = 0; i
bhai last 10 min khud bolke khud smjh liya aapne