http://www.spoj.com/problems/HPPROF/
We will solve this with dynamic programming. Let us have an array A where we will keep our answers, elements A[i] shows the number of possibilities from the beginning of the string to the i th element. Initially A[1] is 1 because with one digit we can make only one possible combination. Let us also have A[0] equal to 1. For element I there are 2 possibilities either the element I is considered as a separate number or the elements I-1 and I be considered as one. Now for every element I the answer equals to A[i-1] at least, also we need to check if the elements I and I-1 form an 2 digit number which is smaller than 21 and there are no leading zeroes then the answer would be A[i-1]+A[i-2] .
Here is the short pseudo code
first a[i]=a[i-1]
if ( a[i-1] and a[i] make a number smaller than 20 and a[i-1] is not zero)
a[i]=a[i]+a[i-2];
Check the source code for a better understanding.
We will solve this with dynamic programming. Let us have an array A where we will keep our answers, elements A[i] shows the number of possibilities from the beginning of the string to the i th element. Initially A[1] is 1 because with one digit we can make only one possible combination. Let us also have A[0] equal to 1. For element I there are 2 possibilities either the element I is considered as a separate number or the elements I-1 and I be considered as one. Now for every element I the answer equals to A[i-1] at least, also we need to check if the elements I and I-1 form an 2 digit number which is smaller than 21 and there are no leading zeroes then the answer would be A[i-1]+A[i-2] .
Here is the short pseudo code
first a[i]=a[i-1]
if ( a[i-1] and a[i] make a number smaller than 20 and a[i-1] is not zero)
a[i]=a[i]+a[i-2];
Check the source code for a better understanding.
No comments:
Post a Comment