GeekPractice_DP - meruneru/tech_memo GitHub Wiki
่งฃใใชใใฃใใฎใงใ่งฃ็ญใ่ฆใใ ๏ผใฎๅๆฐใ๏ผใฎๅๆฐใ๏ผใฎๅๆฐใใใใใi2,i3,i5ใงใซใฆใณใใใฆใใๆน้ใๅใฃใฆใใใ
initialize
ugly[] = | 1 |
i2 = i3 = i5 = 0;
First iteration
ugly[1] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(2, 3, 5)
= 2
ugly[] = | 1 | 2 |
i2 = 1, i3 = i5 = 0 (i2 got incremented )
Second iteration
ugly[2] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(4, 3, 5)
= 3
ugly[] = | 1 | 2 | 3 |
i2 = 1, i3 = 1, i5 = 0 (i3 got incremented )
Third iteration
ugly[3] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(4, 6, 5)
= 4
ugly[] = | 1 | 2 | 3 | 4 |
i2 = 2, i3 = 1, i5 = 0 (i2 got incremented )
Fourth iteration
ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(6, 6, 5)
= 5
ugly[] = | 1 | 2 | 3 | 4 | 5 |
i2 = 2, i3 = 1, i5 = 1 (i5 got incremented )
Fifth iteration
ugly[4] = Min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)
= Min(6, 6, 10)
= 6
ugly[] = | 1 | 2 | 3 | 4 | 5 | 6 |
i2 = 3, i3 = 2, i5 = 1 (i2 and i3 got incremented )
Will continue same way till I < 150
//https://www.geeksforgeeks.org/ugly-numbers/
/* Function to get the nth ugly number*/
ull getNthUglyNo(int n) {
// code here
dp[0]=1;
ull next2=2, next3=3, next5=5;
ull i2=0, i3=0, i5=0;
ull ugly = 1;
for(ull i=1; i<n; i++){
ugly =min(next2, min(next3, next5));
dp[i] = ugly;
if(ugly==next2){
i2++;
next2 = dp[i2]*2;
}
if(ugly==next3){
i3++;
next3 = dp[i3]*3;
}
if(ugly==next5){
i5++;
next5=dp[i5]*5;
}
}
return ugly;
}n็ช็ฎใฎใใฃใใใใๆฐๅใ่ฟใ้ขๆฐใ
ๅ้กใซใๅคใๅคงใใใชใใใใmodulo 1000000007ใๅใใใจใจใใใฎใงใๆฐใฅใใชใใจ้้ใฃใฆใใพใใ
long long int nthFibonacci(long long int n){
// code here
dp[0]=0;
dp[1]=1;
for(long long int i=2; i<=n; i++){
dp[i] = (dp[i-1] + dp[i-2])%1000000007;
}
return dp[n];
}ใซใฟใฉใณๆฐใๆฑใใๅ้กใ
Cn = C0*Cn + C1*Cn-1 + C2*Cn-2 + ... +Cn*C0
cpp_int findCatalan(int n)
{
//code here
dp[0] = 1;
dp[1] = 1;
for(int i=2; i<=n; i++){
dp[i]=0;
for(int j=0; j<i; j++){
dp[i] += dp[j]*dp[i-j-1];
}
}
return dp[n];
}