Re: [问题] leetcode 464 can i win

楼主: JameC (智取其乳)   2017-06-16 12:35:21
这题我能想到的办法,是用位元dp。利用二进制表示剩下的数字的集合,第n位代表数字n。
举个例子,110101就代表5、4、2这三个数字所形成的集合。
假设 dp(state,total) 代表在集合state,还有total的情况下,是否会胜利。
若我们从集合里拿了一个数字n,则状态会转移到:
dp(state^(1<<n), total-n)
只要能找到一个n,使 dp(state^(1<<n), total-n) 为false的话,结果就是true了。
附上AC code:https://github.com/a9502854519/LeetCode/blob/master/LeetCode464.cpp

Links booklink

Contact Us: admin [ a t ] ucptt.com