程序员面试金典08.11_go_硬币题目硬币。给定数量不限的硬币

题目硬币。给定数量不限的硬币，币值为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、动态规划；时间复杂度O(n) ，空间复杂度O(n)
func waysToChange(n int) int { coins := []int{1, 5, 10, 25} dp := make([][]int, 5) for i := 0; i <= 4; i++ {dp[i] = make([]int, n+1)dp[i][0] = 1 // 金额为0的情况，只有都不选，组合情况为1 } for i := 1; i <= 4; i++ {for j := 1; j <= n; j++ {if j-coins[i-1] >= 0 {dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]} else {dp[i][j] = dp[i-1][j]}} } return dp[4][n] % 1000000007}2、动态规划；时间复杂度O(n) ，空间复杂度O(n)
文章插图
func waysToChange(n int) int { coins := []int{1, 5, 10, 25} dp := make([]int, n+1) dp[0] = 1 for i := 1; i <= 4; i++ {for j := 1; j <= n; j++ {if j-coins[i-1] >= 0 {dp[j] = dp[j] + dp[j-coins[i-1]]}} } return dp[n] % 1000000007}总结Medium题目，零钱类问题，使用动态规划
相似的题目还有：
leetcode 322.零钱兑换
【程序员面试金典08.11_go_硬币】leetcode 518.零钱兑换II