Hi Everyone!
In the last post we introduced you to the Dynamic Programming with a simple problem of finding Longest increasing sub-sequence. Now In this post we are going to discuss one more problem which involves both Dynamic programming and Fast-Exponentiation.
What is Fast Exponentiation ?
Suppose a real number ‘A’ is Given and you are asked to find A^n where n is a positive integer.
Here is O(n) algorithm to solve the problem…
Intialise Product=1
int Power(int a,int n)
int i=1
for(int i=0;i<n;i++)
Product*=a;
return Product;
But Can we do it faster ?…
Yes! Fast-exponentiation helps us to do that and it can be solved in O(log n) time.
The Logic behind this is the following!
pow(a,n)=pow(pow(a,n/2),2) if n is even
pow(a,n)=pow(pow(a,n/2),2)*a if n is odd
The pseudo-code for the O(log n) algorithm is..
int Power(int a,int n)
if (n==0) return 1;
else if (n==1) return a;
else
int k=Power(a,n/2)
if (n%2) return k * k * a;
else return k*k;
Now let us discuss the problem involving Both DP and Fast exponentiation!
Problem : Given a number ‘n’.Find in how many ways it can be represented as sum of 1’s 2’s and 3’s . As answer can be large find its modulo 1000000007
Example:
5 can be represented with 1’s 2’s 3’s in the following 13 ways..
1+1+1+1+1
1+1+1+2
1+1+2+1
1+2+1+1
2+1+1+1
2+2+1
2+1+2
1+2+2
1+1+3
1+3+1
3+1+1
3+2
2+3
Solution : The problem can be easily solved using Dynamic Programming..
Of course DP is the standard approach to solve this kind of problem
Suppose n=x1+x2+x3+…..+xm
Here xm can be 1 ,2 or 3 . . and remaining expression x1+x2+….. +xm-1 is some way of representing n-1 or n-2 or n-3 respectively
from above we can deduce following recurrence relation…
Let DP[n] denotes no of ways of representing n using 1,2,3’s `
and obviouslyDP[0]=0
DP[1]=1
DP[2]=2
DP[3]=4
and for any n>3 DP[n]=DP[n-1] + DP[n-2] + DP[n-3]
for any value of n we can find solution using O(n) memory and O(n) time..
The only thing you need to do is to run a loop from i=4 to n and calculate DP[i] using
DP[i]=DP[i-1] + DP[i-2] + DP[i-3]
But this can be solved even in a better way…
The above recurrence relation can be written in Matrix notation as..
To calculate (n-1)th power of matrix we can use fast exponentiation
i.e
pow(a,n)=pow(pow(a,n/2),2) if n is even
pow(a,n)=pow(pow(a,n/2),2)*a if n is odd
So the problem can be solved in O(logn) time..
You can understand it better by looking at the code ..
I used C++ Operator Oveloading concept in my solution to do matrix multiplication..
Here is the implementation of O(log n) algorithm using C++..
#include<iostream>
using namespace std;
typedef unsigned long long ull;
#define mod 1000000007
class ThreeByThree
{public:
ull a[4][4];
ThreeByThree operator * (ThreeByThree);
void display();
};
ThreeByThree ThreeByThree:: operator *(ThreeByThree p)
{
ThreeByThree x;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
ull sum=0;
for(int k=1;k<=3;k++)
{
sum+=((a[i][k]%mod)*(p.a[k][j]%mod))%mod;
}
x.a[i][j]=sum%mod;
}
}
return x;
}
void ThreeByThree::display()
{
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
cout<<a[i][j]<<" ";
}
cout<<endl;
}
}
ThreeByThree fastExponentiation(ThreeByThree p,ull n)
{
ThreeByThree Identity;
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
if(i==j) Identity.a[i][j]=1;
else Identity.a[i][j]=0;
}
}
if(n==0) return Identity;
else if(n==1) return p;
else
{
ThreeByThree x=fastExponentiation(p,n/2);
if(n%2) return x*x*p;
else return x*x;
}
}
int main()
{
int t;
ThreeByThree p;
p.a[1][1]=1;p.a[1][2]=1;p.a[1][3]=1;
p.a[2][1]=1;p.a[2][2]=0;p.a[2][3]=0;
p.a[3][1]=0;p.a[3][2]=1;p.a[3][3]=0;
cout<<"Enter no of test cases:\n";
cin>>t;
int count=0;
while(t--)
{ ull n;
count++;
cout<<"Enter n:\n";
cin>>n;
if(n==0)
{
cout<<"The ans for test "<<count<<" is\n";
cout<<0<<endl;
}
else
{
ThreeByThree x=fastExponentiation(p,n-1);
ull ans=(((x.a[3][1])%mod*4)%mod+((x.a[3][2])%mod*2)%mod+((x.a[3][3])%mod*1)%mod)%mod;
cout<<"The ans for test "<<count<<" is\n";
cout<<ans<<endl;
}
}
}
Hope this post will be useful to you in understanding How DynamicProgramming works in solving various kind of Problems..
Please post any doubts and suggestions in the Comments.
Keep looking for the next post! 🙂
Programming Club, IIT Indore 