rustgym/leetcode/
_638_shopping_offers.rs

1struct Solution;
2
3use std::collections::HashMap;
4
5impl Solution {
6    fn shopping_offers(price: Vec<i32>, special: Vec<Vec<i32>>, needs: Vec<i32>) -> i32 {
7        let n = price.len();
8        let m = special.len();
9        let mut memo: HashMap<Vec<i32>, i32> = HashMap::new();
10        memo.insert(vec![0; n], 0);
11        Self::dfs(needs, &mut memo, &price, &special, n, m)
12    }
13    fn dfs(
14        needs: Vec<i32>,
15        memo: &mut HashMap<Vec<i32>, i32>,
16        price: &[i32],
17        special: &[Vec<i32>],
18        n: usize,
19        m: usize,
20    ) -> i32 {
21        if let Some(&res) = memo.get(&needs) {
22            return res;
23        }
24        let mut res: i32 = needs.iter().zip(price.iter()).map(|(a, b)| a * b).sum();
25        'special: for j in 0..m {
26            for i in 0..n {
27                if special[j][i] > needs[i] {
28                    continue 'special;
29                }
30            }
31            let mut needs = needs.to_vec();
32            for i in 0..n {
33                needs[i] -= special[j][i];
34            }
35            res = res.min(Self::dfs(needs, memo, price, special, n, m) + special[j][n]);
36        }
37        memo.insert(needs, res);
38        res
39    }
40}
41
42#[test]
43fn test() {
44    let price = vec![2, 5];
45    let special = vec_vec_i32![[3, 0, 5], [1, 2, 10]];
46    let needs = vec![3, 2];
47    let res = 14;
48    assert_eq!(Solution::shopping_offers(price, special, needs), res);
49    let price = vec![2, 3, 4];
50    let special = vec_vec_i32![[1, 1, 0, 4], [2, 2, 1, 9]];
51    let needs = vec![1, 2, 1];
52    let res = 11;
53    assert_eq!(Solution::shopping_offers(price, special, needs), res);
54}
rustgym/leetcode/_638_shopping_offers.rs

rustgym/leetcode/
_638_shopping_offers.rs
