DP Amazon Interview Quetion
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]