adarsh851997's blog

By adarsh851997, history, 4 years ago, In English

here is one of the dp question in which i got stucked ;please someone help me . i know there are many geneious people here for whom this problem will be a cakewalk.

PROBLEM:: A rat gives birth to 2 rat on day 1 and on day 2 it gives birth to 3 rat and on third day it dies. how many rats will be present at Nth day .intially there are K rats are present; k and n are upto 1e4;

MY SOLUTION here is what i did i tried to calcualte number od rats present on day i,let it be dp[i].

so,dp[i]=number of rats on (i-1) day+number of rats on (i-2) day + (birth on (i-1) day)*2 + (birth on (i-2) day)*3 -death on i-3 th day; is iam right? or something is wrong the problem was asked in interview of airtel and the interviewer was not satisfied.

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it