Snapchat - give sum target list<Integer>
first who hits target wins
// DP 从 1-N 不重复取数 加到sum 上 第一个超过target赢 先手可以赢吗?
开始想错了,以为和climbing stairs和combination sum iv一个类型,是一个dfs
dfs(list, sum, target)
1. 如果list长度是0,那么就说明当前玩家没机会赢了,返回false
2. 如果list长度是1,那么说明该玩家赢了,因为后面一个玩家已经没机会抽了
3. 对于list中的数依次尝试:
如果当前数字加上sum能够达到target了,就返回true
否则,从list中把这个数移除,递归
如果递归的结果是true,也就是说下一个玩家会赢,也就是说当前玩家会输,那么result是false
再把这个数加回去,记得放回原位!
代码:
public class ChooseOneNumFirstWIllWin {
public boolean dfs(List<Integer> list, int sum, int target) {
if(list.size() == 0) {
return false;
}
if(list.size() == 1) {
return true;
}
boolean result = true;
for(int i = 0; i < list.size(); i++) {
if(sum + list.get(i) >= target) {
return true;
}
int cur = list.remove(i);
if(dfs(list, sum + cur, target)) {
result = false;
}
list.add(i, cur);
}
return result;
}
public static void main(String[] args) {
List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3,4,5));
int sum = 0;
int target = 11;
ChooseOneNumFirstWIllWin sample = new ChooseOneNumFirstWIllWin();
System.out.println(sample.dfs(list, sum, target));
}
}