LeetCode 1140 化整为零的DP求解思路

发表于

思路：

本题是要求解在1:n的石子堆内，先出手者的最大收益。

dp(i,j)表示，i:n的石子堆内，先出手者的最大收益。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        piles.insert(0, 0)
        n = len(piles)
        for i in range(1, n):
            piles[i] += piles[i - 1]
        a = [[0] * n for i in range(n)]

        def dp(i, j):
            if n - i <= 2 * j:
                return piles[n - 1] - piles[i - 1]
            if a[i][j] > 0:
                return a[i][j]
            for k in range(2 * j):
                if i + k >= n:
                    break
                if a[i][j] == 0:
                    a[i][j] = piles[n - 1] - piles[i - 1] - dp(i + k + 1, max(k + 1, j))
                else:
                    a[i][j] = max(a[i][j], piles[n - 1] - piles[i - 1] - dp(i + k + 1, max(k + 1, j)))
            return a[i][j]

        return dp(1, 1)

反思：

dp问题分两种，1）每增加一项，寻找第i项与第i-1项之间的递推关系。2）将大的范围，逐渐减小至小范围，临界条件已知，最后求解大范围处的值。