# Finding recurrence and an algorithm to represent it

You find yourself in a country with integer coin denominations $c_1 < c_2 < ... < c_r$, where $c_1 = 1$. Unfortunately, the greedy algorithm is not guaranteed to find the optimal way to make change. Let $C(i)$ be the minimum number of coins needed to make change for $i$ cents.

(a) Find a recurrence for $C$.

(b) Write an algorithm for computing an array OPT$[0...n]$ where OPT$[i]$$= C(i)$.

I'm not really sure how to go about doing this. What does the information about the greedy algorithm tell us about the behavior of the problem? How can we use the information given to write a recurrence for $C(i)$?

-

The information about the greedy algorithm basically just tells you how not to approach the problem. – Brian M. Scott Dec 17 '12 at 2:44

## 1 Answer

It is a typical problem in Dynamic Programming. You can check Dynamic Programming Solution to the Coin Changing Problem.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8796607255935669, "perplexity_flag": "middle"}