问题：如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？.md

矫情吗；* 2023-05-30 09:21 1阅读 0赞

### 问题 ###

> 如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元？

动态规划的本质是将原问题分解为同性质的若干相同子结构，在求解最优值的过程中将子结构的最优值记录到一个表中以避免有时会有大量的重复计算。

例如硬币组合问题，若求凑够11元的最少硬币数，可以先从凑够0元、1元、2元……的子结构开始分析。

假设d(i)为凑够i元所需最少硬币数，则

d(0) = 0 　　　　　　　　理所当然
    
    d(1) = 1 　　　　　　　　要凑够1元，需要从面值小于等于1元的硬币中选择，目前只有面值为1元的硬币
    
    　　　　　　　　　　　　此时d(1) = d(0) + 1
    
    d(2) = d(2 - 1) + 1 = 2， 从面值小于等于2元的硬币中选择，符合要求的硬币面值为：1元。
    
    　　　　　　　　　　　　此时d(2) = d(2-1) + 1
    
    d(3) = d(3 - 3) + 1 = 1， 从面值小于等于3元的硬币中选择，符合要求的硬币面值为：1元，3元。
    
    　　　　　　　　　　　　此时有有两种选择：是否选择含有面值3元的硬币
    
    　　　　　　　　　　　　含有3元硬币：d(3) = d(3 - 3) + 1 = 1
    
    　　　　　　　　　　　　不含3元硬币：d(3) = d(3 - 1) + 1 = d(2) + 1 = 3
    
    　　　　　　　　　　　　自然是选择二者中较小值

依次类推…

### 算法思想 ###

假如要计算11元需要的面值数最小，那么，11元减去一张1元或者3元或者5元，即10元，8元，6元分别需要的面值数，取出最小，加上1，即可以得到11元最小的。  
所以，n元最小问题，是由n-1元，n-3元，n-5元三种状态里面取到的最优解。  
其中计算的递归树为：  
d(11) = min\{d(10),d(8),d(6)\} + 1  
递推式  
d(i) = min\{d(i-v)\} + 1,其中v为面值1，3，5；i为求值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]

### 实现代码 ###

/** * https://www.cnblogs.com/z941030/p/4908115.html * https://www.kancloud.cn/qiaodong/datastructure/134483#135_165 * DP * @since 2019-10-25 */
    public class Solution_2019_11_9 { 
        // 如果我们有面值为1元、3元和5元的硬币若干枚，如何用最少的硬币凑够11元
        public int select_coin(int[] coins, int total) { 
            // 状态转移方程
            int[] minCoins = new int[total + 1];
            minCoins[0] = 0;
    
            for (int i = 1; i <= total; i++) { 
                minCoins[i] = Integer.MAX_VALUE;
                for (int j = 0; j < coins.length; j++) { 
                    if (coins[j] <= i && minCoins[i - coins[j]] + 1 < minCoins[i]) { 
                        minCoins[i] = minCoins[i - coins[j]] + 1;
                    }
                }
            }
            System.out.println(Arrays.toString(minCoins));
            return minCoins[total];
        }
    
        public static void main(String[] args) { 
            System.out.println(new Solution_2019_11_9().select_coin(new int[]{ 1, 3, 5}, 11));
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191109115314551.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9qaWVuaXlpbWlhby5ibG9nLmNzZG4ubmV0,size_16,color_FFFFFF,t_70