题解 | 换钱的方法数

package main

import (
	"fmt"
)
const Mod = 1e9+7
func main() {
    a := 0
    b := 0
    for {
        n, _ := fmt.Scan(&a, &b)
        if n == 0 {
            break
        } else {
            coins := make([]int, a)
            for i:=0; i<a; i++ {
                fmt.Scan(&coins[i])
            }
            fmt.Printf("%d\n", process(coins, b, 0))
        }
    }
}

func process(coins []int, aim int, index int) int {
    if len(coins) == 0 || aim < 0{
        return 0
    }
    dp := make([][]int, len(coins)+1)
    for i:=0; i<len(dp); i++ {
        dp[i] = make([]int, aim+1)
        dp[i][0] = 1
    }
    dp[len(coins)][0] = 1
    for i:=len(dp)-2; i>=0; i-- {
        for j:=1; j<=aim; j++ {
            // for k:=0; k*coins[i] <= j; k++ {
            //     dp[i][j] += dp[i+1][j-k*coins[i]]
            //     dp[i][j] = dp[i][j]%Mod
            // }
		    // 枚举行为可以进一步优化
		    // eg 假设某个位置dp[i][j]，需要依次枚举 0-k次
		   // dp[i][j] k = 0时，依赖 dp[i+1][j] 处的值
		   // dp[i][j] k > 0时, 可以认为只依赖 dp[i][j-coins[i]] 处的值（前提不越界
            dp[i][j] = (dp[i+1][j])
            if j>=coins[i] {
                dp[i][j] += (dp[i][j-coins[i]])
            }
            dp[i][j] = dp[i][j]%Mod
        }
    }
    return dp[0][aim]
}