[−][src]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() } }