AMZSEQ

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]. 

RECOMMENDED QUESTION :

Try your hands on this simple question.

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;

}