【DSA】作業五,Dice Sum Game

Dynamic Programming題

題目大意是:有八個格子,四個代表個位數,四個代表十位數,骰一個骰子八次,每次放在這八個格子的其中一個,全部放滿之後計算總和,如果超過150就爆掉輸了,求不爆掉情況下最高分,用DP來做,理論上會是118嗎

理論是什麼理論呢?先從DP的概念開始說好了,DP就是把大問題變成一堆小問題,然後小問題求最佳解(因為小問題比較好求),之後所有最佳解加起來就會是大問題的最佳解,而且在拆成小問題的時候,小問題會重複,所以我們就把做個的存起來建表,遇到一樣的小問題就直接從表裡取值,不用重複計算

這題就設一個函數D(p,q,s),p是十位數剩下幾個格子可以放,q是個位數,s是目前總和多少,這題要做的就是求每一個情況下,他走到最後的期望值是什麼,所以會變成:

D(p,q,s) = 1/6(Max(D(p-1,q,s+10), D(p,q-1,s+1))+ 1/6(Max(D(p-2,q,s+20), D(p,q-2,s+2))+ 1/6(Max(D(p-3,q,s+30), D(p,q-3,s+3))+ 1/6(Max(D(p-4,q,s+40), D(p,q-4,s+4))+ 1/6(Max(D(p-5,q,s+50), D(p,q-5,s+5))+ 1/6(Max(D(p-6,q,s+60), D(p,q-6,s+6))

因為下一次骰會出現1~6種可能,且可以放十位或個位數,所以就選擇最大的,但要加上Boundry Condition,s>150要回傳0,p或q不能小於零,p和q為零的時候回傳s

理論感覺就是個遞迴,但是實作還是要想一下,我最後建了兩個三維陣列,一個儲存每一個情況的期望值,一個記錄每一個可能的期望值有沒有計算過,之後計算時,如果有計算過就直接回傳,沒計算就去計算

然後再決定的時候,如果放在十位數的期望值比較大,就放十位數,反之亦然

不過我很腦殘卡在一個問題三天,幹你老師……

就是1/6在預設int下是0,要直接/6……超低能

做出來速度還蠻快的,目前第九名