爱彼赢店面

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过程