menu combo
国人小哥＋一个shadow abc
老哥人很nice!
// Input:
Menu:
"Fruit": 2.15,
"Fries": 2.75,
"Salad": 3.35,
"Wings": 3.55,
"Mozzarella": 4.20,
"Plate": 5.80,
target = 4.3
output:
[["fruit", "fruit"]]
假设给你一份菜单 找出所有combo最终的价格的等于target price.
很显然backtracking题目，秒了 最后聊了聊corner case.
这题有个follow up，不给target price，给一个getPrice(“Mozzarella”, “Wings”)各种组合的API，menu combo会被call很多次，要你设计一个数据结构怎么存。。。
组合是指 m 个 “Mozzarella” + n 个 “Wings” 吗？
hashmap存就好了吧
遍历所有可能组合存hashmap？太大了吧
不是，原题有点记不清了，好像是存任意若干个组合（不是n个同一种），call最终的价格
应该可以把组合map成一个数字，这样也就是存储若干数字，如果是连续区间的数字可以存成interval
另外就是存储小于一定值(比如100)的price对应的combo，相当于cache，更大的price可以在这个cache的基础上计算出来，相当于省去计算price在前100的dp过程