@All... According to the constraints(SPOJ problem) wont this dp solution time out ?
On Tue, Jan 25, 2011 at 12:23 AM, sankalp srivastava < richi.sankalp1...@gmail.com> wrote: > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.
