The problem statement
We can solve this task using dynamic programming. Suppose we have the number of words which end with zero, one and two. Lets make arrays zero[N], one[N], two[N] where zero[I], one[I], two[I] each will show the number of words with length I ending with 0, 1 and 2 respectively. The task says to find the number of words which have a neighboring digit difference at most 1 which means that numbers 0 and 2 can't be neighbors. zero[I] shows the number of words which have length I and end with 0. So I can say that when it comes to calculating the words with length I+1 there will be at least zero[I] words which will end in 0 and zero[I] words which will end 1 because after 0 only the digits 0 and 1 can come. So here is a general formula
suppose we have the answer for the length I ,
the formula for I+1 would be
zero[i]=zero[i-1]+one[i-1]; (Because we can add 0 and 1 to 0)
one[i]=zero[i-1]+one[i-1]+two[i-1]; (because we can add 0 1 and 2 to 1)
two[i]=one[i-1]+two[i-1]; (because we can add 1 and 2 to 2)
We can solve this task using dynamic programming. Suppose we have the number of words which end with zero, one and two. Lets make arrays zero[N], one[N], two[N] where zero[I], one[I], two[I] each will show the number of words with length I ending with 0, 1 and 2 respectively. The task says to find the number of words which have a neighboring digit difference at most 1 which means that numbers 0 and 2 can't be neighbors. zero[I] shows the number of words which have length I and end with 0. So I can say that when it comes to calculating the words with length I+1 there will be at least zero[I] words which will end in 0 and zero[I] words which will end 1 because after 0 only the digits 0 and 1 can come. So here is a general formula
suppose we have the answer for the length I ,
the formula for I+1 would be
zero[i]=zero[i-1]+one[i-1]; (Because we can add 0 and 1 to 0)
one[i]=zero[i-1]+one[i-1]+two[i-1]; (because we can add 0 1 and 2 to 1)
two[i]=one[i-1]+two[i-1]; (because we can add 1 and 2 to 2)
No comments:
Post a Comment