Plese help me On Dp Question

Revision en1, by adarsh851997, 2020-10-06 10:27:08

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.

Tags #dp, bottom-up

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English adarsh851997 2020-10-06 10:27:08 788 Initial revision (published)