##
__AMZ Word__

Link to the question : AMZSEQ

###
__HINT : __

A very good question on dynamic programming. We take an array a[] and assign a[0] = 1. Now, we can make 1 letter words in 3 ways , i.e, use any of the digit. Similarly if you solve for 2 letter words by applying a bit of permutation and combination, you will get it to be 7. Similarly, by using the relation , a[2] = 7 , in 3 letter words, you will find number of ways to be 17. Hence we conlude the conclusion that a[i]= 2* a[i-1] + a[i-2].

###
__SOURCE CODE: __

#include <iostream>

using namespace std;

int main()

{

long long int a[25];

int x;

a[0] = 1;

a[1] = 3;

for(int i = 2; i < 25; i++)

a[i] = 2*a[i-1] + a[i-2];

cin >> x;

cout << a[x] << endl;

return 0;

}

there is a problem in you hint, that is there should be 17 in place of 15.

ReplyDeleteyeah, thanks !!

Delete