0518.零钱兑换 II.md

解题关键点

• 还是动态规划，属于完全背包问题
• 创建一个长度为 target + 1 的背包，循环迭代即可
• 不需要对 coins 进行排序
• 时间复杂度 O(m * n) 空间复杂度 O(m)，其中 m 为 target，n 为 coins 列表的长度

代码

impl Solution {
    pub fn change(amount: i32, coins: Vec<i32>) -> i32 {
        let mut fp: Vec<i32> = vec![0; amount as usize + 1];
        fp[0] = 1;
        for c in coins {
            let mut i = c;
            while i <= amount {
                fp[i as usize] += fp[(i - c) as usize];
                i += 1;
            }
        }
        fp[amount as usize]
    }
}

测试用例

assert_eq!(change(5, vec![1, 2, 5]), 4);
assert_eq!(change(3, vec![2]), 0);
assert_eq!(change(10, vec![10]), 1);
assert_eq!(change(1000, vec![1,2,5,10,20,50,100]), 234896541);