硬币

题目链接

思路

dp即可

go解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func waysToChange(n int) int {

	dp := make([]int, n+1)

	coins := []int{1, 5, 10, 25}

	for i := 0; i < 4; i++ {
		for j := 1; j <= n; j++ {
			if coins[i] < j {
				dp[j] += dp[j-coins[i]]
			}
			if coins[i] == j {
				dp[j]++
			}
			dp[j] %= 1000000007
		}
	}
	return dp[n]
}