阿祁的部落格

LeetCode - Cherry Pickup I&II 解題心得 ( 題目一 )( 題目二 )

這裡因為兩題解法有點像，所以放在一起講。

解題概念:DP

解題方法:第一題一開始會有greedy的想法，就是把題目看成一個人從左上到右下跑兩次最佳解，而對於-1的格子把它改成-inf，所以保證不拿到，另外在第一次把最佳解拿到的櫻桃移掉，但是這樣是錯的，我也因此拿過WA，在某些特殊情況兩次最佳解並不是整體最佳解，所以我們只能放棄貪。我們試試看DP!

我們可以先得到一種定義dp[x1][x2][y1][y2]，代表第一人走到(x1,y1)、第二人走到(x2,y2)的最佳解，跟前面一樣視為兩個人，但是我們要怎麼判斷他們是同一格呢?我們改一下定義: 我們改成dp[step][x1][x2]，step代表兩個人各自總共走幾格，如果x1==x2代表他們在同一格，而y座標呢?其實我們發現每一步只有x或y加1兩種可能，總之y1=step-x1，y2=step-x2，而轉移分成四種(dp[step-1][x1][x2]、dp[step-1][x1-1][x2])、dp[step-1][x1-1][x2-1])、dp[step-1][x1][x2-1]))於是我們就可以求出整個的最佳解了!

接著是第二題，我覺得第二題比較直觀，就是dp[y][x1][x2]，和第一題一樣要判斷他是否出現在同一格，如果是就要少算一次，轉移是分成九種。

以上，兩題都可以在O(n^3)解決。