Re: [問題] leetcode 464 can i win
看板Prob_Solve (計算數學 Problem Solving)作者JameC (CmeJa)時間7年前 (2017/06/16 12:35)推噓0(0推 0噓 0→)留言0則, 0人參與討論串4/4 (看更多)
這題我能想到的辦法，是用位元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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.70.213.197
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1497587727.A.071.html
※ 編輯: JameC (61.70.213.197), 06/16/2017 12:36:10
討論串 (同標題文章)
完整討論串 (本文為第 4 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
