qxixp
BAN USERThis is another DP problem, with two steps 1, 2. It is a Fibonacci sequence as mentioned above. But what if Frog can jump S1, S2 ... Sn steps?
The number of ways to n is equal to
N[n-S1] + N[n-S2] + .. N[n-Sn] if (n-Si) > 0,
N[0] + 1 if n = Si
N[0] equals 0
The time complexity is equal to n x S, n is the sum and S is number of jumps frog has
The space complexity is equal to n
You can use merge sort approach. Use a variable, n, to keep the count of nth smallest number. Keep track of the current nth smallest number, if both values are the same and is equal to the ith smallest number, skip both values, otherwise increment n and update the smallest number. If n equals k, return the nth smallest number
If one of them reaches to the end of the array, do a while loop from there until n reaches k.
It is F[n] = F[n-1] + F[n-2]
- qxixp February 28, 2014F[3] = F[2] + F[1]
1 1 1 part of F[2]
2 1 part of F[2]
1 2 part of F[1]
F[2]
1 1
2
F[1]
1