https://docs.google.com/document/d/1qxA2wps0IhVRWULulQ55W4SGPMu2AE5MkBB37h8Dr58/
可乐饮料机
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=453698
这是一道非常简单的递归题。假设[a,b]表示按某个钮操作得到的饮料的体积范围，[A,B]表示我们需要得到的饮料的体积范围，那么题意告诉我们如果满足 A<=a && b<=B的话，那么就能满足条件。如果不能满足怎么办？我们试着将待求的[A,B]减去[a,b]，剩下的范围是[A-a,B-b]。我们这个时候仔细想一下，就会发现，假设[A-a,B-b]能够通过饮料机的操作得到，那么自然我们再操作一次[a,b]，就能得到[A,B]了。所以递归的关系就找到了。边界条件是[A,B]能被某一个操作满足，或者直到A<0都无法实现。
如果递归的层数特别多，可以记忆化一下。
有点像combination sum 的区间版
18. 可乐饮料机 高频 5次
有一系列按钮，每个按钮按下去会得到一定体积范围的可乐。先给定一个目标体积范围，问不限制按按钮次数，能否确定一定能得到目标范围内的可乐？
举例：有三个按钮，按下去得到的范围是[100, 120], [200, 240], [400, 410],
假设目标是[100, 110], 那答案是不能。因为按下一，可能得到120体积的可乐，不在目标范围里。
假设目标是[90, 120]，那答案是可以。因为按下一，一定可以得到此范围内的可乐。
假设目标是[300, 360], 那答案是可以，因为按下一再按二，一定可以得到此范围内
假设目标是[310, 360], 那答案是不能，因为按下一再按二，有可能得到300，永远没可能确定得到这个范围内的可乐。
假设目标是[1, 9999999999]，那答案是可以。随便按一个都确定满足此范围。
思路：dfs+memorization从0开始暴力解 一开始[0, 0] 通过bfs、dfs往上加直到出界
请问这道题目如果用dfs + memo的时间复杂度是不是 n!, n是bottom的size，如果不是的话，时间复杂度怎么分析？
这里的memorication不用记录true的情况，因为会直接返回不会将结果用于其他地方，所以用一个hashset存false的情况就可以了
这里的memorication不用记录true的情况，因为会直接返回不会将结果用于其他地方，所以用一个hashset存false的情况就可以了
这其实可以看做是自顶向下的dp
O(MNK)
public static boolean dfs(List<Soda> sodas, int volumeLower, int volumeUpper,
int targetLower, int targetUpper, Map<String, Boolean> memo) {
Boolean val = memo.get(volumeLower + "-" + volumeUpper);
if (val != null) {
return val;
}
if (volumeLower >= targetLower && volumeUpper <= targetUpper) {
return true;
}
if (volumeUpper > targetUpper) {
return false;
}
// if (volumeUpper - volumeLower > targetUpper - targetLower) retuurn false;
for (Soda soda : sodas) {
if (dfs(sodas, volumeLower + soda.lower, volumeUpper + soda.upper, targetLower, targetUpper, memo)) {//false的子问题会重复计算
memo.put(volumeLower + "-" + volumeUpper, true);
return true;
}
}
memo.put(volumeLower + "-" + volumeUpper, false);
return false;
}
据说这题是binary search？ 这个应该bfs，dfs都能做。但是据说还可以用dp，dp怎么做啊。谁能po个解法？
区间DP的做法：(Provider: anonym)
public static boolean coke(List<List<Integer>> buttons, List<Integer> target) {
public static boolean coke(List<List<Integer>> buttons, List<Integer> target) {
int m = target.get(0);
int n = target.get(1);
boolean[][] dp = new boolean[m + 1][n + 1];
//Init
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
for (List<Integer> button: buttons) {
if (i <= button.get(0) && j >= button.get(1)) {
dp[i][j] = true;
break;
}
}
}
}
for (int i = 0; i <= m; ++i) {
for (int j = 0; j <= n; ++j) {
for (List<Integer> button: buttons) {
int preL = i - button.get(0);
int preR = j - button.get(1);
if (preL >= 0 && preR >= 0 && dp[preL][preR]) {
dp[i][j] = true;
break;
}
}
}
}
return dp[m][n];
}
这算是一个多重背包问题。我曾经被面到过一个类似的：给一个调色板由一堆颜色组成，每个颜色有RGB三个分量。问能否调出一个目标颜色
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=453698
应该是背包问题，先来个简单的DFS + Memo，有空再想 DP和补Test Case
def vendor_machine(sodas, target_low, target_high): def dfs(curr_low, curr_high, memo={}): if (curr_low, curr_high) in memo: return memo[curr_low, curr_high] if curr_high > target_high: return False if target_low <= curr_low and curr_high <= target_high: return True for low, high in sodas: if dfs(curr_low + low, curr_high + high): memo[curr_low, curr_high] = True return True memo[curr_low, curr_high] = False return False return dfs(0, 0)
这是一道非常简单的递归题。假设[a,b]表示按某个钮操作得到的饮料的体积范围，[A,B]表示我们需要得到的饮料的体积范围，那么题意告诉我们如果满足 A<=a && b<=B的话，那么就能满足条件。如果不能满足怎么办？我们试着将待求的[A,B]减去[a,b]，剩下的范围是[A-a,B-b]。我们这个时候仔细想一下，就会发现，假设[A-a,B-b]能够通过饮料机的操作得到，那么自然我们再操作一次[a,b]，就能得到[A,B]了。所以递归的关系就找到了。边界条件是[A,B]能被某一个操作满足，或者直到A<0都无法实现。
如果递归的层数特别多，可以记忆化一下。
bool solution(vector<vector<int>>&p, int A, int B){ if (A<0) return false; for (int i=0; i<p.size(); i++) { if (A<=p[i][0] && B>=p[i][1]) return true; } for (int i=0; i<p.size(); i++) { if (solution(p,A-p[i][0],B-p[i][1])) return true; } return false;}有点像combination sum 的区间版
**首次发代码，给一个naive的递归解法，指数级时间复杂度O(2^N)
struct interval
{
int start;
int end;
interval(int a, int b)
{
start = a;
end = b;
}
};
bool getCoca(vector<interval> vec, interval target, int depth)
{
if(depth == vec.size()) return false;
if(target.start <= vec[depth].start && target.end >= vec[depth].end) return true;
if(target.start > vec[depth].start && target.end > vec[depth].end)
{
if( getCoca(vec, interval(target.start-vec[depth].start, target.end-vec[depth].end), depth+1))
{
return true;
}
}
return getCoca(vec, target, depth+1);
}
