DP Amazon Interview Quetion

sohesh doshi
1 min readJan 7, 2020

A frog jumps either 1, 2 or 3 steps to go to top. In how many ways can it reach the top.

def solution(num):  if num==1 or num==2 or num==3:    return num  return 1+solution(num-1)+solution(num-2)+solution(num-3)

Let’s Define Dp solution using recursive

def Dp_Solution(num):  temp=[0 for i in range(num+1)]  temp[0]=temp[1]=1  temp[2]=2  temp[3]=3  if num>3:    for i in range(4,num+1):      temp[i]=1+temp[i-1]+temp[i-2]+temp[i-3]  return temp[num]