Here is the problem statement
http://www.spoj.com/problems/ACODE/
We will solve this task with dynamic programming (we will calculate the current answer with the help of already calculated answers). We will keep an array of answers A. We assume that A[I] shows the answer for the string fromt he begining to the element I. First a[0]=1; a[1]=1; now we loop over the rest fo the elements. For every digit I we check if the number containing the digits I and I-1 is less or equal to 26 we can conclude that the last 2 digits separetaly can be read in 2 ways, we will have our current a[I] equal to a[I-1]+a[I-2] ( we look at 2 different situations, if we look at the last 2 digits as separate letters that leaves us the asnwer of a[I-1] and If we look at them as they were one letter together that leaves us a[I-2])
. If the current digit is 0 or his neighbours are 0 or we can't make a 2 digit number with I and I-1 we assign a[I] tha value of a[I-1];
http://www.spoj.com/problems/ACODE/
We will solve this task with dynamic programming (we will calculate the current answer with the help of already calculated answers). We will keep an array of answers A. We assume that A[I] shows the answer for the string fromt he begining to the element I. First a[0]=1; a[1]=1; now we loop over the rest fo the elements. For every digit I we check if the number containing the digits I and I-1 is less or equal to 26 we can conclude that the last 2 digits separetaly can be read in 2 ways, we will have our current a[I] equal to a[I-1]+a[I-2] ( we look at 2 different situations, if we look at the last 2 digits as separate letters that leaves us the asnwer of a[I-1] and If we look at them as they were one letter together that leaves us a[I-2])
. If the current digit is 0 or his neighbours are 0 or we can't make a 2 digit number with I and I-1 we assign a[I] tha value of a[I-1];
Nice Explanation! :)
ReplyDeleteThanks! :)
A[1] can be either 1 or 2 depending upon the decoding of first two digits.
ReplyDeletethnx
ReplyDelete