最小编辑距离(Edit distance)

1. /// Coin change via Dynamic Programming

3. /// coin_change(coins, amount) returns the fewest number of coins that need to make up that amount.
4. /// If that amount of money cannot be made up by any combination of the coins, return `None`.
5. ///
6. /// Arguments:
7. ///     * `coins` - coins of different denominations
8. ///     * `amount` - a total amount of money be made up.
9. /// Complexity
10. ///     - time complexity: O(amount * coins.length),
11. ///     - space complexity: O(amount),
12. pub fn coin_change(coins: &[usize], amount: usize) -> Option<usize> {
13. let mut dp = vec![std::usize::MAX; amount + 1];
14. dp[0] = 0;

16. // Assume dp[i] is the fewest number of coins making up amount i,
17. // then for every coin in coins, dp[i] = min(dp[i - coin] + 1).
18. for i in 0..=amount {
19. for j in 0..coins.len() {
20. if i >= coins[j] && dp[i - coins[j]] != std::usize::MAX {
21. dp[i] = dp[i].min(dp[i - coins[j]] + 1);
22. }
23. }
24. }

26. match dp[amount] {
27. std::usize::MAX => None,
28. _ => Some(dp[amount]),
29. }
30. }

32. #[cfg(test)]
33. mod tests {
34. use super::*;

36. #[test]
37. fn basic() {
38. // 11 = 5 * 2 + 1 * 1
39. let coins = vec![1, 2, 5];
40. assert_eq!(Some(3), coin_change(&coins, 11));

42. // 119 = 11 * 10 + 7 * 1 + 2 * 1
43. let coins = vec![2, 3, 5, 7, 11];
44. assert_eq!(Some(12), coin_change(&coins, 119));
45. }

47. #[test]
48. fn coins_empty() {
49. let coins = vec![];
50. assert_eq!(None, coin_change(&coins, 1));
51. }

53. #[test]
54. fn amount_zero() {
55. let coins = vec![1, 2, 3];
56. assert_eq!(Some(0), coin_change(&coins, 0));
57. }

59. #[test]
60. fn fail_change() {
61. // 3 can't be change by 2.
62. let coins = vec![2];
63. assert_eq!(None, coin_change(&coins, 3));
64. let coins = vec![10, 20, 50, 100];
65. assert_eq!(None, coin_change(&coins, 5));
66. }
67. }