Fibonacci Sequence vs Coin Change Problem with two Coins(with denomination and 1 and 2).

general
, ,
1

I was solving an interview problem, which goes like this, “A man can jump either 1 step or 2 step in a go, find the total number of unique ways in which he can reach to the nth step, if he initially was on the 0th step. Unique means that, for say n = 5 : 2 -> 1 -> 2, 2 -> 2 -> 1 and 1 -> 2 -> 2 are considered same.”

This is similar to the the popular programming puzzle with the constraint of counting only ‘unique’ ways added to it, where you are allowed to count redundant ways(which is similar to the Fibonacci sequence, following the recurrence relation dp[n] = dp[n-1] + dp[n-2]). But because this recurrence relation also counts redundant ways, this won’t work in the current version of the problem. After thinking for about 5-10 mins, I realised that it is just the modified version of the Coin Change problem with just 2 coins(of denomination 1 and 2). Needless to say I got AC but this left me thinking how does Coin Change avoid repetition but Fibonacci does not(okay, it is not exactly the Fibonacci sequence, but I am calling it because of the similarity in recurrence relation.). I get the intuition but can anyone present a more formal Mathematical proof?

1 Like
2

I cant understand what u mean by redundant ways

The recurrence dp[n]=dp[n-1] + dp[n-2] would give correct ans provided that dp[i] represents the number of unique ways to reach i.

Edit:

If there are coins of denomination a,b,c

Dp[n] gives the number of solution to equation ax+by+cz=n,which is what u need

(As by recurrence u can see that if u take z c type coins ,then u see how many solutions exists for ax+by=n-cz)

3

By redundant, I think he meant that “Ways which are same, if order doesnt matter.”

Eg, with coins 1 and 2, you can make 3 as-

1+1+1
2+1=1+2 (both of these ways are same/redundant).
2 Likes
4

What I am trying to point here, is consider:

The base case is: dp[1] = 1, dp[2] = 2
if repetitions were allowed dp[4] = 5, which basically follows by the bottom up approach dp[i] = dp[i-1] + dp[i-2]. However here dp[4] should be = 3. Why does counting the first way get us wrong answer(5)?

see this: https://practice.geeksforgeeks.org/problems/count-ways-to-nth-stairorder-does-not-matter/0

5

Thanks @vijju123 for clearing out, yes, I exactly meant this.

1 Like
6

You want proof that coin exchange recurrence is correct?