一道google高频面试题，看到好多人讨论没有确切答案，请问大家有什么好的想法吗？题目如下：
可乐饮料机，有一系列按钮，每个按钮按下去会得到一定体积范围的可乐。先给定一个目标体积范围，问不限制按按钮次数，能否确定一定能得到目标范围内的可乐？
举例：有三个按钮，按下去得到的范围是[100, 120], [200, 240], [400, 410],.
假设目标是[100, 110], 那答案是不能。因为按下一，可能得到120体积的可乐，不在目标范围里。
假设目标是[90, 120]，那答案是可以。因为按下一，一定可以得到此范围内的可乐。
假设目标是[300, 360], 那答案是可以，因为按下一再按二，一定可以得到此范围内.
假设目标是[310, 360], 那答案是不能，因为按下一再按二，有可能得到300，永远没可能确定得到这个范围内的可乐
假设目标是[1, 9999999999]，那答案是可以。随便按一个都确定满足此范围
按钮有什么限制吗？比如本身没有overlap
假设按钮是[s1, e1],[s2, e2],[s3, e3]，target是[ts, te]
这实际上就是 coin change 变种，找 [s1,s2,s3] 是否可以拼出在[ts, te]内的最小amount，假设为t_min。
然后找 [e1,e2,e3] 是否可以拼出在[ts, te]内的最大amount，假设为t_max。
最后看t_min需要小于t_max
按钮应该本身是没有overlap的
哦，这里其实还有个问题，就是s和e在选择的时候，必须对应，也就是选了s2，必须选择e2。
这样分别考察ts和te是否无法保证拼出ts和te按钮的次数相等呢
对，要保持对应的
还是 coin change 变种，找 [s1,s2,s3] 是否可以拼出在[ts, te]内的amount，这里可能有多种。然后找到相应的[e1,e2,e3]的组合，看是否在[ts, te]内
。。。。。
dp[i]代表以 i 作为某些集合start和的end最小和
转移方程是
dp[i] = Min{dp[i-start[k]]+end[k]}
嗯，我理解你的意思了。就是当i是 [s1,s2,s3] 的组合sum up to i，相应的[e1,e2,e3]的组合应该最小。
这应该是正解。
哦哦哦，然后答案是判断dp[i] 是否小于要求的范围的end值吗？比如说如果我们要确定[100, 110] 是否可以，就要判断dp[100]是否小于110？
不好意思啊，我下午回复你的我自己删掉了。你说的对，我觉得这个例子应该是给错了。
楼上不完全正确。
试看dp[100],dp[101]…dp[110]里面有没有小于等于110的
有道理，我没考虑周全，感谢大神回复！
那这个空间不会很大吗？
比如[1, 9999999999]需要记录很多
我觉得可能是时间和空间的tradeoff，如果范围很大就用dfs直接做
你空间爆炸的时候时间也不靠谱啊。。。
Unfortunately这个题好像真的没有线性解法。。
我觉得还是需要一个2d的dp，这是我的python code，有不对的请大佬指正。。如果有target_range的lo，hi的limit，那么这个algorithm应该是O(lo * hi * n)的complexity
def solve(buttons, target_range):
'''
buttons: List[List[int]]
target_range: List[int]
returns: boolean
'''
lo, hi = target_range
dp = set([(0, 0)])
for s, e in buttons:
new_dp = set()
for s2, e2 in dp:
i = 1
while True:
# we try to push as many times as we can
s3, e3 = s2 + s * i, e2 + e * i
if s3 >= lo and e3 <= hi:
return True
elif s3 > lo: # missing the range [lo, s3]
break
new_dp.add((s3, e3))
i += 1
dp = dp | new_dp
return False