Correct me if I'm wrong dp[i][j]=how many numbers of length i with the last digit j(int base 10) dp[0][j]=0 dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number has i-1 digits , not j;
now the recursion to pass from one state to the next dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j , from 0 to k) That is to say , the number of numbers with length i and last digit j , will be equal to the number of numbers with the last digit k , for each k less than j .One is added because , we must not have included the 0 in the last case , but we will include the zero case here . this one corresponds to zero case . Finally , the answer will be dp[n][j] , 1<=j<=9 , sum up all these and u have the answer For example for 2 digits dp[1][1-9]=1 , as nothing preceeds them and as said in the problem , one digit numbers are always increasing/decreasing . next dp[2][1]=dp[1][1](As only 1 is less than , equal to 1 , the last digit in this state) dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2) Continuing this way , we will get the answer , may be 50 , though i din code it . similarly , for 3 digits Correct me if not! On Jan 25, 12:06 am, juver++ <avpostni...@gmail.com> wrote: > dp[i][j] - how many numbers of length i and with the last digit j. > Apply the scheme to increasing and decreasing number, then find ratio. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
