I am recently doing Minimum Fibonacci terms with sum equal to K. i have done using dp approach but tle. but why this problem works with greedy approach.

# | User | Rating |
---|---|---|

1 | tourist | 3686 |

2 | mnbvmar | 3509 |

3 | Benq | 3339 |

4 | LHiC | 3330 |

5 | wxhtxdy | 3329 |

6 | sunset | 3279 |

7 | Petr | 3275 |

7 | V--o_o--V | 3275 |

9 | yutaka1999 | 3190 |

10 | ecnerwala | 3153 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | Radewoosh | 189 |

3 | rng_58 | 164 |

4 | PikMike | 160 |

5 | Vovuh | 157 |

6 | Petr | 155 |

7 | 300iq | 154 |

8 | majk | 149 |

9 | Um_nik | 147 |

10 | Swistakk | 144 |

I am recently doing Minimum Fibonacci terms with sum equal to K. i have done using dp approach but tle. but why this problem works with greedy approach.

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/19/2019 05:05:08 (e3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

According to Zeckendorf's theorem any number can be uniquely described as a sum of Fibonacci numbers.

so,this unique representation comes from greedy approach ?

yes

I would like to say, that it isn't unique, unless you mention that the representation is such that no two consecutive fibonacci numbers ( Say $$$F_{n-1}$$$ and $$$F_{n}$$$ ) are used for the representation, because you can just use $$$F_{n+1}$$$ instead.

There is an optimal solution that uses each Fibonacci number at most once and never uses two consecutive Fibonacci numbers.

Proof: Take the lexicographically largest solution. It cannot use two consecutive numbers because such a solution would not be optimal (instead of F_n and F_{n+1} take just F_{n+2}). It cannot use 1 twice because using 2 once is better. It cannot use any bigger Fibonacci number twice because instead of F_n + F_n you can have F_{n+1} + F_{n-2} which gives you a lexicographically bigger solution with the same number of coins.

Each number has exactly one representation that uses each Fibonacci number at most once and never uses two consecutive Fibonacci numbers. The greedy algorithm constructs this representation and therefore its output is always optimal.