http://www.spoj.com/problems/NOVICE43/
We can solve this task using dynamic programming. Let us have an array A[11][26] where the element A[I][J] shows the number of valid sequences of length I where the last present letter is the Jth letter. Let's look on an example
for 1 there is one sequence "a"
for 2 there are 2 sequences "ab" "aa"
for 3 there are 5 sequences "aaa" "aab" "aba" "abb" "abc"
So, A[3][2] will be 3 because there are 3 sequences which have a length of 3 and their "biggest" letter is b. A[3][3] will be 1 because there is only 1 sequence of length 3 which has the "biggest" letter of 'c'.
So here is how our dynamic approach will look like
for every A[i][j]
we can add all the letters to form the i+1 length from 1 to J+1 the letter, for every letter added if that letter is smaller than J => the "biggest" letter will still be J.
This is the formula
for A[i][j]
A[i+1][j]=A[i+1][j]+j*A[i][j];
A[i+1][j+1]=A[i][j];
We can solve this task using dynamic programming. Let us have an array A[11][26] where the element A[I][J] shows the number of valid sequences of length I where the last present letter is the Jth letter. Let's look on an example
for 1 there is one sequence "a"
for 2 there are 2 sequences "ab" "aa"
for 3 there are 5 sequences "aaa" "aab" "aba" "abb" "abc"
So, A[3][2] will be 3 because there are 3 sequences which have a length of 3 and their "biggest" letter is b. A[3][3] will be 1 because there is only 1 sequence of length 3 which has the "biggest" letter of 'c'.
So here is how our dynamic approach will look like
for every A[i][j]
we can add all the letters to form the i+1 length from 1 to J+1 the letter, for every letter added if that letter is smaller than J => the "biggest" letter will still be J.
This is the formula
for A[i][j]
A[i+1][j]=A[i+1][j]+j*A[i][j];
A[i+1][j+1]=A[i][j];
No comments:
Post a Comment