动态规划经典题目-找零钱的方案数

25-03-07 18:21

2317

13290

blog.csdn.net

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-atom-one-dark">

class="toc">

文章目录

一、题目描述
二、解题思路（最朴素方法）
三、代码实现
四、优化
五、执行结果

一、题目描述

在美国，硬币按照面值1，5，10，25，50来铸造(单位为美分)。现在考虑按照面值{d₁,…, d_k}(单位为分)来铸造硬币的某个国家.我们想统计有多少种方式能找开n分钱，并记种数为C(n)。例如当所在国家硬币面值集合为{1,6,10}时,C(5)=1,C(6)到C(9)都是2，C(10)=3，C(12)=4。

给出一种高效算法来算出C(n)并分析该算法的时间/空间复杂度。(提示:通过计算C(n,d)来解决问题,C(n,d)是最高面值为d情况下能找开n分钱的方式种数.千万注意不要重复计数.)

———题目来源：《算法设计指南》

示例：

输入：coins = [2,3,5] total = 10
输出：4
解释：2 + 3 + 5是一种
	 2 + 2 + 3 + 3是一种
	 2 + 2 + 2 + 2 + 2 + 2是一种
     5 + 5是一种
     总共4种。
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

二、解题思路（最朴素方法）

1. 定义状态

设dp[i][j]表示使用前i个面值不同的硬币找出零钱j的方案数。

2. 定义状态转移方程

$\sum_{k=0}^{n}(dp[i - 1][j - k \times d_i])$ ，其中 $\lfloor \frac{j}{d_i} \rfloor$ 。这里解释一下 $d p [i - 1]$ 表示使用前 $i - 1$ 个面值不同的硬币，其中第 $i$ 个硬币可能使用0个或多个，上限为 $\lfloor \frac{j}{d_i} \rfloor$ 个，下限为0个。

3. 初始化

dp[0][j]表示不使用硬币找出j的方案数，根据实际情况是找不出来的，故初始化为0。

dp[i][0]表示使用前i个面值不同硬币找出0美分的方案数量，很显然dp[i][0]初始化为1即可。

三、代码实现

/**
 * 第8章第7题 找零钱问题
 *
 * @author hh
 */
public class Solution {

    /**
     *找零钱的方案数
     *
     * @param coins 硬币面值集合
     * @param total 找的零钱总数
     * @return 方案数
     */
    public int exchange(int[] coins,int total) {
        int[][] dp = new int[coins.length + 1][total + 1];
        //dp[0][i] = 0,i > 0时
        for(int i = 1; i <= total; i++){
            dp[0][i] = 0;
        }
        for(int i = 0; i <= coins.length ; i++){
            dp[i][0] = 1;
        }
        for(int i = 1; i <= coins.length ; i++){
            for(int j = 1; j <= total ; j++){
                dp[i][j] = 0;
                for(int k = 0; k <= (j / coins[i -1]) ; k++){
                    dp[i][j] += dp[i-1][j - k * coins[i - 1]];
                }
            }
        }
        return dp[coins.length ][total];
    }

    public static void main(String[] args){
        Solution solution = new Solution();
        int[] coins = new int[]{2,3,5};
        int total = 10;
        System.out.println(solution.exchange(coins,total));
    }

}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

class="hide-preCode-box">

四、优化

对于解题思路中的k其实是没必要计算的，这样就减少了一个循环。状态方程变为：

$dp[i][j] = sum(dp[i - 1][j],dp[i][j - d_i])$

表示的含义是前i-1种硬币凑成j的方案数加上前i种硬币凑成j - d_i的方案数。第二个式子表示最少有一枚硬币i凑成零钱总数j的方案数。

代码如下所示：

public class Solution2 {

    /**
     * 找零钱的方案数
     *
     * @param coins 硬币面值集合
     * @param total 找的零钱总数
     * @return 方案数
     */
    public int exchange(int[] coins, int total) {
        int[][] dp = new int[coins.length + 1][total + 1];
        for (int i = 0; i <= coins.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= coins.length; i++) {
            for (int j = 0; j <= total; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= coins[i - 1]) {
                    dp[i][j] += dp[i][j - coins[i - 1]];
                }
            }
        }
        return dp[coins.length][total];
    }

    public static void main(String[] args) {
        Solution2 solution = new Solution2();
        int[] coins = new int[]{2, 3, 5};
        int total = 10;
        System.out.println(solution.exchange(coins, total));
    }

}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

class="hide-preCode-box">

上面是对时间复杂度进行优化，下面对空间进行优化，考虑到dp[i][j]只跟dp[i-1]和dp[i]有关，我们可以把二维降成一维，代码如下所示：

public class Solution3 {

    /**
     * 找零钱的方案数
     *
     * @param coins 硬币面值集合
     * @param total 找的零钱总数
     * @return 方案数
     */
    public int exchange(int[] coins, int total) {
        int[] dp = new int[total + 1];
        dp[0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            for (int j = coins[i - 1]; j <= total; j++) {
                dp[j] += dp[j - coins[i - 1]];
            }
        }
        return dp[total];
    }

    public static void main(String[] args) {
        Solution3 solution = new Solution3();
        int[] coins = new int[]{2, 3, 5};
        int total = 10;
        System.out.println(solution.exchange(coins, total));
    }

}
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}"> class="hide-preCode-box">1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

五、执行结果

注：本文转载自blog.csdn.net的仁者乐山智者乐水的文章"https://blog.csdn.net/qq_39559641/article/details/117173247"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。

复制链接

发表评论

/ 登录

评论记录：

未查询到任何数据！