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