638. Shopping Offers

public class Solution {
    public int ShoppingOffers(IList<int> price, IList<IList<int>> special, IList<int> needs) {
        var memo = new Dictionary<string, int>();
        return Dfs(price, special, needs, memo);
    }
    private int Dfs(IList<int> price, IList<IList<int>> special, IList<int> needs, Dictionary<string, int> memo) {
        string key = Serialize(needs);
        if (memo.ContainsKey(key)) {
            return memo[key];
        }
        int minPrice = 0;
        for (int i = 0; i < needs.Count; i++) {
            minPrice += needs[i] * price[i];
        }
        foreach (var offer in special) {
            var newNeeds = new List<int>();
            bool valid = true;
            for (int i = 0; i < needs.Count; i++) {
                if (needs[i] < offer[i]) {
                    valid = false;
                    break;
                }
                newNeeds.Add(needs[i] - offer[i]);
            }
            if (valid) {
                minPrice = Math.Min(minPrice, offer[needs.Count] + Dfs(price, special, newNeeds, memo));
            }
        }
        memo[key] = minPrice;
        return minPrice;
    }
    private string Serialize(IList<int> needs) {
        return string.Join(",", needs);
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ShoppingOffers(vector<int> price, IList<vector<int>> special, vector<int> needs) {
        var memo = new unordered_map<string, int>();
        return Dfs(price, special, needs, memo);
    }
    private int Dfs(vector<int> price, IList<vector<int>> special, vector<int> needs, unordered_map<string, int> memo) {
        string key = Serialize(needs);
        if (memo.count(key)) {
            return memo[key];
        }
        int minPrice = 0;
        for (int i = 0; i < needs.size(); i++) {
            minPrice += needs[i] * price[i];
        }
        foreach (var offer in special) {
            var newNeeds = new List<int>();
            bool valid = true;
            for (int i = 0; i < needs.size(); i++) {
                if (needs[i] < offer[i]) {
                    valid = false;
                    break;
                }
                newNeeds.push_back(needs[i] - offer[i]);
            }
            if (valid) {
                minPrice = min(minPrice, offer[needs.size()] + Dfs(price, special, newNeeds, memo));
            }
        }
        memo[key] = minPrice;
        return minPrice;
    }
    private string Serialize(vector<int> needs) {
        return string.Join(",", needs);
    }
}

import java.util.*;

public class Solution {
    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return dfs(price, special, needs, new HashMap<>());
    }
    
    private int dfs(List<Integer> price, List<List<Integer>> special, List<Integer> needs, Map<List<Integer>, Integer> memo) {
        if (memo.containsKey(needs)) return memo.get(needs);
        
        int minPrice = 0;
        for (int i = 0; i < needs.size(); i++) {
            minPrice += needs.get(i) * price.get(i);
        }
        
        for (List<Integer> offer : special) {
            List<Integer> newNeeds = new ArrayList<>();
            for (int i = 0; i < needs.size(); i++) {
                if (offer.get(i) > needs.get(i)) break;
                newNeeds.add(needs.get(i) - offer.get(i));
            }
            if (newNeeds.size() == needs.size()) {
                minPrice = Math.min(minPrice, dfs(price, special, newNeeds, memo) + offer.get(offer.size() - 1));
            }
        }
        
        memo.put(needs, minPrice);
        return minPrice;
    }
}

var shoppingOffers = function(price, special, needs) {
    const memo = new Map();
    
    const dfs = (needs) => {
        const key = needs.join(',');
        if (memo.has(key)) {
            return memo.get(key);
        }

        let minPrice = needs.reduce((sum, need, i) => sum + need * price[i], 0);

        for (let offer of special) {
            const newNeeds = needs.map((need, i) => need - offer[i]);
            if (newNeeds.every(need => need >= 0)) {
                minPrice = Math.min(minPrice, offer[offer.length - 1] + dfs(newNeeds));
            }
        }

        memo.set(key, minPrice);
        return minPrice;
    };

    return dfs(needs);
};

def shoppingOffers(price, special, needs):
    memo = {}
    
    def dfs(cur_needs):
        val = sum(cur_needs[i] * price[i] for i in range(len(needs)))
        for sp in special:
            new_needs = []
            for i in range(len(needs)):
                if sp[i] > cur_needs[i]:
                    break
                new_needs.append(cur_needs[i] - sp[i])
            if len(new_needs) == len(needs):
                val = min(val, memo.get(tuple(new_needs), dfs(new_needs)) + sp[-1])
        memo[tuple(cur_needs)] = val
        return val

    return dfs(needs)

package main

import (
  "fmt"
  "strconv"
  "strings"
)

func shoppingOffers(price []int, special [][]int, needs []int) int {
  memo := make(map[string]int)
  return dfs(price, special, needs, memo)
}

func dfs(price []int, special [][]int, needs []int, memo map[string]int) int {
  key := serialize(needs)
  if val, exists := memo[key]; exists {
    return val
  }

  minPrice := 0
  for i := 0; i < len(needs); i++ {
    minPrice += needs[i] * price[i]
  }

  for _, offer := range special {
    newNeeds := make([]int, len(needs))
    valid := true
    for i := 0; i < len(needs); i++ {
      if needs[i] < offer[i] {
        valid = false
        break
      }
      newNeeds[i] = needs[i] - offer[i]
    }
    if valid {
      minPrice = min(minPrice, offer[len(needs)]+dfs(price, special, newNeeds, memo))
    }
  }

  memo[key] = minPrice
  return minPrice
}

func serialize(needs []int) string {
  var sb strings.Builder
  for _, need := range needs {
    sb.WriteString(strconv.Itoa(need))
    sb.WriteString(",")
  }
  return sb.String()
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

Algorithm

Рекурсивное вычисление стоимости

Определите функцию, которая рекурсивно вычисляет минимальную стоимость для оставшихся нужд, используя dynamic programming для запоминания уже вычисленных значений.

Использование специальных предложений

Для каждой комбинации товаров в специальных предложениях, определите, можно ли использовать это предложение без превышения нужд. Если можно, вычислите новую стоимость, given это предложение.

Выбор минимальной стоимости

Сравните стоимость при использовании специальных предложений и стоимость при покупке товаров по индивидуальным ценам, выбирая минимальную стоимость.

😎