[算法练习及思路-程序员面试金典(Java解法)]No51.硬币(完全背包问题+优化空间)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了[算法练习及思路-程序员面试金典(Java解法)]No51.硬币(完全背包问题+优化空间)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2033字，纯文字阅读大概需要3分钟。

内容图文

题号:no51

题目名:硬币

原题URL:https://leetcode-cn.com/problems/coin-lcci/

题目描述

硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例

示例 1：

 输入: n = 5
 输出：2
 解释: 有两种方式可以凑成总金额:
5=5
5=1+1+1+1+1

示例 2：

 输入: n = 10
 输出：4
 解释: 有四种方式可以凑成总金额:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

限制

• 注意:

  你可以假设：

  • 0 <= n (总金额) <= 1000000

思路

1.经典完全背包问题,容量固定,物品无限放

2.因为硬币可以无限放,所以以硬币做外层循环,避免重复

3.状态转移方程就是dp[ i ] [ j ] = (dp[ i - 1 ] [ j ] + dp [i] [j - coins[i-1]]),当如果可以用该硬币

如果不用该硬币,那就是上一个硬币的方法数就行dp[ i ] [ j ] = dp[ i - 1 ] [ j ]

4.可以将二维完全背包变成一维

解题代码

class Solution {
    public int waysToChange(int n) {
        //1000000007
        //硬币类型为25,10,5,1四种类型,总共是n元
        //当总值等于n的时候,其实一共有四种方法能达到
        //1.前面的硬币总值为n-25,最后一个硬币为25元
        //2.前面的硬币总值为n-10,最后一个硬币为10元
        //3.前面的硬币总值为n-5,最后一个硬币为5元
        //4.前面的硬币总值为n-1,最后一个硬币为1元
        //完全背包问题
        int mod = 1000000007;
        int[] coins = {1,5,10,25};
        int[][] dp = new int[coins.length+1][n+1];
        //先初始化所有硬币的取出方式都为1
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j < n + 1; j++) {
                //遍历硬币
                dp[i][j] = dp[i - 1][j];
                if (j - coins[i-1] >= 0) dp[i][j] = (dp[i - 1][j] + dp[i][j - coins[i-1]])%mod;
            }
        }
        return dp[coins.length][n];
    }
}

优化

1.优化思路就是讲二维变成一维,要去掉的维度要对原来没有影响

2.也就是说,可以作为滚动数组来操作

3.观察二维,可以看到状态方程式都是(i,j)和(i-1,j)在挂钩,其实用前面一维做滚动就够用了

class Solution {
    public int waysToChange(int n) {
        //完全背包问题
        int mod = 1000000007;
        int[] coins = {1,5,10,25};
        int[][] dp = new int[coins.length+1][n+1];
        //先初始化所有硬币的取出方式都为1
		dp[0] = 1;

        for (int i = 1; i <= coins.length; i++) {
            for (int j = 1; j < n + 1; j++) {
                //遍历硬币
                if (j - coins[i-1] >= 0) dp[j] = (dp[j] + dp[j - coins[i-1]])%mod;
            }
        }
        return dp[coins.length][n];
    }
}

内容总结

以上是互联网集市为您收集整理的[算法练习及思路-程序员面试金典(Java解法)]No51.硬币(完全背包问题+优化空间)全部内容，希望文章能够帮你解决[算法练习及思路-程序员面试金典(Java解法)]No51.硬币(完全背包问题+优化空间)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---