Let ways[n][k][prev] denote the number of ways of selecting a sequence of
size K, where n is the current index,k is the size,prev is the previous
chosen element in the sequence.
then
ways[n][k][prev]=ways[n][k][prev]+ways[n-1][k][prev],
if a[n]>=a[prev]
ways[n][k][prev]=ways[n][k][prev]+ways[n-1][k][prev]+ways[n-1][k-1][n] ,
else
(Recursion + Memoization) Code:
int ways[10][10][10];
int ar[]={ 1, 4, 6, 2, 5,1000};
int i,j,k,K=3,N=4;
int rec(int n,int k,int prev){
if(k==0) return 1;
if(n<0) return 0;
if(~ways[n][k][prev]) return ways[n][k][prev];
else{
int a,b=0;
a=rec(n-1,k,prev);
if(ar[n]<ar[prev]) b=rec(n-1,k-1,n);
return ways[n][k][prev]=a+b;
}
}
int main(){
for(i=0;i<10;i++) for(j=0;j<10;j++) for(k=0;k<10;k++) ways[i][j][k]=-1;
printf("%d\n",rec(N,K,N+1));
return 0;
}
Now,this code can easily be converted to a DP solution....
--
*Regards,*
*Piyush Kapoor,*
*2nd year,CSE
IT-BHU*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
