Function leetcode_for_rust::cd0322_coin_change::coin_change

pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32

Solutions

Approach 1: Dynamic Programming

• Time complexity: O(s*n)

• Space complexity: O(s)

• Runtime: 4 ms

• Memory: 3 MB

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let mut dp = vec![amount + 1; (amount + 1) as usize];
        dp[0] = 0;

        for i in 1..=amount {
            for &coin in coins.iter() {
                if i >= coin {
                    dp[i as usize] = i32::min(dp[i as usize], dp[(i - coin) as usize] + 1);
                }
            }
        }
        let last = *dp.last().unwrap();
        if last > amount { return -1; } else { return last; }
    }
}

Approach 2: Dynamic Programming

• Time complexity: O(s*n)

• Space complexity: O(s)

• Runtime: 4 ms

• Memory: 4 MB

impl Solution {
    pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
        let mut dp = vec![-1; (amount+1) as usize];
        dp[0] = 0;

        for i in 1..=amount as usize {
            dp[i] = std::i32::MAX;
            for &coin in coins.iter() {
                if i >= coin as usize && dp[i - coin as usize] != -1 {
                    dp[i] = i32::min(dp[i], dp[i - coin as usize] + 1);
                }
            }
            if dp[i] == std::i32::MAX { dp[i] = -1; }
        }
        *dp.last().unwrap()
    }
}