# Editing Dynamic programming

**Warning:** You are not logged in. Your IP address will be publicly visible if you make any edits. If you **log in** or **create an account**, your edits will be attributed to your username, along with other benefits.

The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.

Latest revision | Your text | ||

Line 78: | Line 78: | ||

This problem exhibits optimal substructure in the following sense. Suppose we have found out how to make change for <math>n</math> cents using some minimal collection of coins, and we take one coin away (with value <math>x</math>), leaving a collection of coins with total value <math>n-x</math>. Then, what we are left with ''must'' be an optimal way to make change for <math>n-x</math>. This is because if we had any ''better'' way (fewer coins) of making change for <math>n-x</math>, then we could just add the coin of value <math>x</math> back in, and get a better way of making change for <math>n</math> cents than what we originally assumed was minimal, a contradiction. | This problem exhibits optimal substructure in the following sense. Suppose we have found out how to make change for <math>n</math> cents using some minimal collection of coins, and we take one coin away (with value <math>x</math>), leaving a collection of coins with total value <math>n-x</math>. Then, what we are left with ''must'' be an optimal way to make change for <math>n-x</math>. This is because if we had any ''better'' way (fewer coins) of making change for <math>n-x</math>, then we could just add the coin of value <math>x</math> back in, and get a better way of making change for <math>n</math> cents than what we originally assumed was minimal, a contradiction. | ||

− | For example, if we have 48 cents in the form of one 25-cent coin, one 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with one 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 6 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling | + | For example, if we have 48 cents in the form of one 25-cent coin, one 10-cent coins, two 5-cent coins, and three 1-cent coins, and we take away the 25-cent coin, then we are left with one 10-cent coins, two 5-cent coins, and three 1-cent coins, that is, 6 coins totalling 23 cents. However, 7 coins is not the least number of coins required to change 23 cents; we could do it in 5 (using two 10-cent coins and three 1-cent coins). This proves that our original way of making change for 48 cents was not optimal, as we can just add the quarter back in (so we'll have one 25-cent coin, two 10-cent coins, and three 1-cent coins, or 6 coins totalling 25 cents) and get a better way. Whenever we have a suboptimal solution to a subinstance, we will also have a suboptimal solution to the original instance; so an optimal solution to the original instance is only allowed to contain optimal solutions to subinstances. |

To solve the change problem using DP, we start by considering the simplest possible case: when the amount to be changed is zero. Then, the optimal (and only) solution is to use no coins at all. But whenever we change a positive amount, we must use at least one coin. If we take any coin (with value <math>x</math>) away from the optimal change for amount <math>n</math>, then we are left with optimal change for <math>n-x</math>. This implies that we can make optimal change for <math>n</math> using at least one of the following ways: make optimal change for <math>n-d_1</math> and add one coin of value <math>d_1</math>; or make optimal change for <math>n-d_2</math> and add one coin of value <math>d_2</math>; ...; or make optimal change for <math>n-d_m</math> and add one coin of value <math>d_m</math>. This is because if ''none'' of these are optimal, then when we make optimal change for <math>n</math>, and remove some coin of value <math>d_i</math>, leaving <math>n-d_i</math>, we will have optimal change for <math>n-d_i</math>, but we already know that adding a coin of value <math>d_i</math> to the leftover collection does ''not'' give optimal change for <math>n</math>, and yet it regenerates the original collection, which we assumed to be optimal, and this is a contradiction. | To solve the change problem using DP, we start by considering the simplest possible case: when the amount to be changed is zero. Then, the optimal (and only) solution is to use no coins at all. But whenever we change a positive amount, we must use at least one coin. If we take any coin (with value <math>x</math>) away from the optimal change for amount <math>n</math>, then we are left with optimal change for <math>n-x</math>. This implies that we can make optimal change for <math>n</math> using at least one of the following ways: make optimal change for <math>n-d_1</math> and add one coin of value <math>d_1</math>; or make optimal change for <math>n-d_2</math> and add one coin of value <math>d_2</math>; ...; or make optimal change for <math>n-d_m</math> and add one coin of value <math>d_m</math>. This is because if ''none'' of these are optimal, then when we make optimal change for <math>n</math>, and remove some coin of value <math>d_i</math>, leaving <math>n-d_i</math>, we will have optimal change for <math>n-d_i</math>, but we already know that adding a coin of value <math>d_i</math> to the leftover collection does ''not'' give optimal change for <math>n</math>, and yet it regenerates the original collection, which we assumed to be optimal, and this is a contradiction. |