\u52a8\u6001\u89c4\u5212\u662f\u7b97\u6cd5\u9762\u8bd5\u7684"\u8fc7\u6ee4\u5668"\u3002\u51e0\u4e4e\u6240\u6709\u5927\u5382\u7684\u9762\u8bd5，DP \u9898\u7684\u51fa\u73b0\u9891\u7387\u4ec5\u6b21\u4e8e\u6570\u636e\u7ed3\u6784\u7684\u5e94\u7528\u9898\u3002\u4f46 DP \u53c8\u662f\u6700\u8ba9\u4eba\u6709\u632b\u8d25\u611f\u7684\u65b9\u5411\u2014\u2014\u770b\u9898\u89e3\u89c9\u5f97\u903b\u8f91\u901a\u7545，\u81ea\u5df1\u5199\u603b\u662f\u5728\u72b6\u6001\u5b9a\u4e49\u6216\u8f6c\u79fb\u65b9\u7a0b\u4e0a\u5361\u58f3\u3002<\/p>\n
7 \u6708\u6211\u628a LeetCode \u4e0a\u7684 DP \u9898\u6309\u9898\u578b\u505a\u4e86\u7cfb\u7edf\u5206\u7c7b\u548c\u96c6\u4e2d\u8bad\u7ec3\u3002\u4e00\u4e2a\u5173\u952e\u53d1\u73b0\u662f：DP \u9898\u505a\u4e0d\u51fa\u6765\u7684\u6838\u5fc3\u539f\u56e0\u4e0d\u662f"\u4e0d\u806a\u660e"，\u800c\u662f\u6ca1\u6709\u5efa\u7acb\u4ece\u9898\u76ee\u7279\u5f81\u5230 DP \u7c7b\u578b\u7684\u6620\u5c04\u76f4\u89c9\u3002\u6362\u53e5\u8bdd\u8bf4，\u4f60\u770b\u5b8c\u9898\u76ee\u540e\u65e0\u6cd5\u5feb\u901f\u5224\u65ad\u5b83\u662f"\u80cc\u5305"\u8fd8\u662f"\u533a\u95f4 DP"\u8fd8\u662f"\u72b6\u6001\u538b\u7f29"，\u8fd9\u5c31\u5bfc\u81f4\u6bcf\u6b21\u90fd\u8981\u4ece\u96f6\u5f00\u59cb\u63a8\u5bfc\u3002<\/p>\n
\u672c\u7bc7\u6587\u7ae0\u7684\u76ee\u6807\u662f：\u5efa\u7acb\u4e00\u4e2a\u53ef\u64cd\u4f5c\u7684 DP \u9898\u578b\u5206\u7c7b\u4f53\u7cfb，\u8ba9\u6bcf\u4e00\u7c7b\u9898\u578b\u90fd\u6709\u5bf9\u5e94\u7684\u8bc6\u522b\u7279\u5f81\u548c\u89e3\u9898\u6a21\u677f\u3002<\/p>\n
DP \u7684\u4e09\u4e2a\u6838\u5fc3\u6982\u5ff5\u2014\u2014\u6700\u4f18\u5b50\u7ed3\u6784\u3001\u91cd\u53e0\u5b50\u95ee\u9898\u3001\u65e0\u540e\u6548\u6027\u2014\u2014\u6559\u79d1\u4e66\u4e0a\u90fd\u6709\u5b9a\u4e49，\u4f46\u7406\u89e3\u5b83\u4eec\u7684\u5173\u952e\u5728\u4e8e\u7528\u4ee3\u7801\u76f4\u89c9\u53bb\u7ffb\u8bd1\u3002<\/p>\n
\u6700\u4f18\u5b50\u7ed3\u6784\u7ffb\u8bd1\u6210\u4ee3\u7801\u76f4\u89c9：\u5982\u679c\u4f60\u80fd\u7528\u4e00\u4e2a\u9012\u5f52\u51fd\u6570 f(state) \u8868\u793a\u4ece state \u51fa\u53d1\u7684\u6700\u4f18\u89e3，\u4e14 f \u7684\u8ba1\u7b97\u53ea\u4f9d\u8d56\u66f4\u5c0f\u7684\u5b50\u95ee\u9898\u7684 f \u503c，\u90a3\u4e48\u8fd9\u4e2a\u95ee\u9898\u5c31\u6709\u6700\u4f18\u5b50\u7ed3\u6784\u3002\u53cd\u4f8b：\u6c42\u56fe\u4e2d\u7684\u6700\u957f\u7b80\u5355\u8def\u5f84（\u6ca1\u6709\u6700\u4f18\u5b50\u7ed3\u6784，\u56e0\u4e3a\u5b50\u8def\u5f84\u7684\u6700\u4f18\u4e0d\u4e00\u5b9a\u7ec4\u6210\u5168\u5c40\u6700\u4f18）\u3002<\/p>\n
\u91cd\u53e0\u5b50\u95ee\u9898\u7ffb\u8bd1\u6210\u4ee3\u7801\u76f4\u89c9：\u5982\u679c\u4f60\u753b\u51fa\u9012\u5f52\u6811，\u53d1\u73b0\u5f88\u591a\u8282\u70b9\u7684\u72b6\u6001\u53c2\u6570\u4e00\u6a21\u4e00\u6837，\u90a3\u5c31\u4e0d\u7528\u72b9\u8c6b，\u4e0a\u8bb0\u5fc6\u5316\u641c\u7d22\u6216 DP \u8868\u3002\u5982\u679c\u9012\u5f52\u6811\u7684\u6bcf\u4e2a\u8282\u70b9\u72b6\u6001\u90fd\u4e0d\u540c（\u5982\u5feb\u901f\u6392\u5e8f），\u90a3 DP \u5c31\u4e0d\u9002\u7528\u3002<\/p>\n
\u65e0\u540e\u6548\u6027\u7ffb\u8bd1\u6210\u4ee3\u7801\u76f4\u89c9：\u72b6\u6001\u5b9a\u4e49\u4e4b\u540e，\u4ece\u8be5\u72b6\u6001\u5230\u7ec8\u70b9\u7684\u6700\u4f18\u51b3\u7b56，\u4e0e"\u600e\u4e48\u5230\u8fbe\u8fd9\u4e2a\u72b6\u6001"\u65e0\u5173\u3002\u6362\u53e5\u8bdd\u8bf4，\u72b6\u6001\u672c\u8eab\u5305\u542b\u4e86\u505a\u540e\u7eed\u51b3\u7b56\u6240\u9700\u7684\u5168\u90e8\u4fe1\u606f\u3002<\/p>\n
\u8fd9\u4e09\u4e2a\u6761\u4ef6\u6ee1\u8db3\u65f6，DP \u7684\u89e3\u9898\u6846\u67b6\u5c31\u56fa\u5b9a\u4e0b\u6765\u4e86：\u5b9a\u4e49\u72b6\u6001 \u2192 \u627e\u72b6\u6001\u8f6c\u79fb \u2192 \u786e\u5b9a\u521d\u59cb\u5316 \u2192 \u51b3\u5b9a\u904d\u5386\u987a\u5e8f \u2192 \u8fd4\u56de\u76ee\u6807\u72b6\u6001\u3002<\/p>\n
"""
\nDP \u9898\u578b\u5206\u7c7b\u6a21\u677f\u5e93
\n\u6bcf\u7c7b\u9898\u578b\u5305\u542b：\u8bc6\u522b\u7279\u5f81 + \u72b6\u6001\u5b9a\u4e49 + \u8f6c\u79fb\u65b9\u7a0b + \u590d\u6742\u5ea6\u5206\u6790 + \u5de5\u7a0b\u7ea7\u4ee3\u7801
\n\u6240\u6709\u6ce8\u91ca\u89e3\u91ca"\u4e3a\u4ec0\u4e48\u8fd9\u6837\u8bbe\u8ba1"\u800c\u975e"\u8fd9\u884c\u4ee3\u7801\u505a\u4ec0\u4e48"
\n"""
\nfrom typing import List<\/p>\n
# ========== \u7c7b\u578b\u4e00：\u7ebf\u6027 DP（\u4ee5\u6253\u5bb6\u52ab\u820d II \u4e3a\u4f8b） ==========
\ndef rob_circle(nums: List[int]) -> int:
\n """
\n LeetCode 213：\u6253\u5bb6\u52ab\u820d II（\u73af\u5f62\u6570\u7ec4）
\n \u65f6\u95f4\u590d\u6742\u5ea6：O(n)，\u904d\u5386\u4e24\u6b21\u6570\u7ec4
\n \u7a7a\u95f4\u590d\u6742\u5ea6：O(1)，\u53ea\u7528 3 \u4e2a\u53d8\u91cf\u6eda\u52a8\u66f4\u65b0<\/p>\n
\u73af\u5f62\u95ee\u9898\u7684\u901a\u7528\u5904\u7406\u65b9\u5f0f：\u5206\u6210"\u9009\u5934\u4e0d\u9009\u5c3e"\u548c"\u9009\u5c3e\u4e0d\u9009\u5934"\u4e24\u4e2a\u5b50\u95ee\u9898
\n \u4e3a\u4ec0\u4e48\u4e0d\u9009\u62e9\u66f4\u591a\u5206\u5272？\u56e0\u4e3a\u73af\u53ea\u6709\u4e00\u4e2a\u65ad\u70b9，\u4e24\u79cd\u5212\u5206\u5c31\u80fd\u8986\u76d6\u6240\u6709\u53ef\u80fd
\n """
\n if len(nums) == 1:
\n return nums[0]<\/p>\n
def rob_linear(arr: List[int]) -> int:
\n """\u7ebf\u6027\u7248\u672c\u7684\u6253\u5bb6\u52ab\u820d \u2014\u2014 \u7a7a\u95f4\u4f18\u5316\u7684\u5173\u952e\u662f\u53ea\u4fdd\u7559\u524d\u4e24\u4e2a\u72b6\u6001"""
\n prev2 = prev1 = 0 # prev2 = dp[i-2]，prev1 = dp[i-1]
\n for val in arr:
\n # dp[i] = max(dp[i-1], dp[i-2] + val)
\n # \u5f53\u524d\u4e0d\u5077（\u7ee7\u627f\u524d\u4e00\u4e2a）vs \u5077\u5f53\u524d（\u52a0\u4e0a\u524d\u524d\u4e2a）
\n current = max(prev1, prev2 + val)
\n prev2, prev1 = prev1, current
\n return prev1<\/p>\n
return max(
\n rob_linear(nums[:-1]), # case1：\u4e0d\u5077\u6700\u540e\u4e00\u95f4
\n rob_linear(nums[1:]), # case2：\u4e0d\u5077\u7b2c\u4e00\u95f4
\n )<\/p>\n
# ========== \u7c7b\u578b\u4e8c：0-1 \u80cc\u5305 ==========
\ndef can_partition(nums: List[int]) -> bool:
\n """
\n LeetCode 416：\u5206\u5272\u7b49\u548c\u5b50\u96c6（0-1 \u80cc\u5305\u53d8\u79cd）
\n \u65f6\u95f4\u590d\u6742\u5ea6：O(n * sum\/2)，n \u4e3a\u6570\u7ec4\u957f\u5ea6
\n \u7a7a\u95f4\u590d\u6742\u5ea6：O(sum\/2)，\u4f7f\u7528\u4e00\u7ef4 DP \u4f18\u5316，\u5012\u5e8f\u904d\u5386\u907f\u514d\u8986\u76d6<\/p>\n
\u4e3a\u4ec0\u4e48\u5012\u5e8f？\u56e0\u4e3a 0-1 \u80cc\u5305\u6bcf\u4e2a\u7269\u54c1\u53ea\u80fd\u7528\u4e00\u6b21，
\n \u6b63\u5e8f\u904d\u5386\u4f1a\u5bfc\u81f4\u540c\u4e00\u4e2a\u7269\u54c1\u88ab\u91cd\u590d\u4f7f\u7528（\u53d8\u6210\u5b8c\u5168\u80cc\u5305）
\n """
\n total = sum(nums)
\n if total % 2 != 0:
\n return False # \u603b\u548c\u4e3a\u5947\u6570，\u4e0d\u53ef\u80fd\u7b49\u5206<\/p>\n
target = total \/\/ 2
\n # dp[j] \u8868\u793a\u80fd\u5426\u9009\u51fa\u548c\u4e3a j \u7684\u5b50\u96c6
\n dp = [False] * (target + 1)
\n dp[0] = True # \u7a7a\u5b50\u96c6\u548c\u4e3a 0<\/p>\n
for num in nums:
\n # \u5012\u5e8f\u904d\u5386：\u4fdd\u8bc1\u6bcf\u4e2a num \u53ea\u7528\u4e00\u6b21
\n for j in range(target, num – 1, -1):
\n dp[j] = dp[j] or dp[j – num]<\/p>\n
return dp[target]<\/p>\n
# ========== \u7c7b\u578b\u4e09：\u533a\u95f4 DP ==========
\ndef max_coins(nums: List[int]) -> int:
\n """
\n LeetCode 312：\u6233\u6c14\u7403
\n \u65f6\u95f4\u590d\u6742\u5ea6：O(n\u00b3)，\u4e09\u91cd\u5faa\u73af
\n \u7a7a\u95f4\u590d\u6742\u5ea6：O(n\u00b2)，\u533a\u95f4 DP \u7684 dp \u8868<\/p>\n
\u533a\u95f4 DP \u7684\u5173\u952e\u6d1e\u5bdf：\u5b9a\u4e49 dp[i][j] \u4e3a\u533a\u95f4 (i, j) \u7684\u6c14\u7403\u88ab\u6233\u5b8c\u540e\u7684\u6700\u5927\u5f97\u5206
\n \u4e3a\u4ec0\u4e48\u8981\u7a7a\u533a\u95f4？\u56e0\u4e3a\u8fd9\u6837\u8fb9\u754c\u6761\u4ef6\u5c31\u662f dp[i][i+1] = 0（\u533a\u95f4\u5185\u6ca1\u6709\u6c14\u7403）
\n \u6700\u540e\u4e00\u4e2a\u88ab\u6233\u7684\u6c14\u7403\u628a\u95ee\u9898\u5206\u6210\u4e86\u4e24\u4e2a\u72ec\u7acb\u7684\u5b50\u533a\u95f4
\n """
\n # \u5728\u9996\u5c3e\u6dfb\u52a0 1，\u5904\u7406\u8fb9\u754c（\u7b2c\u4e00\u4e2a\u548c\u6700\u540e\u4e00\u4e2a\u6c14\u7403\u88ab\u6233\u65f6\u7684\u5f97\u5206\u8ba1\u7b97）
\n nums = [1] + nums + [1]
\n n = len(nums)
\n dp = [[0] * n for _ in range(n)]<\/p>\n
# length \u4ece 2 \u5f00\u59cb（\u81f3\u5c11\u5305\u542b\u4e00\u4e2a\u6c14\u7403，\u5373\u4e00\u4e2a nums \u5143\u7d20\u5728\u533a\u95f4\u4e2d）
\n for length in range(2, n):
\n for left in range(n – length):
\n right = left + length
\n # \u679a\u4e3e\u533a\u95f4\u5185\u6700\u540e\u4e00\u4e2a\u88ab\u6233\u7684\u6c14\u7403\u4f4d\u7f6e
\n for k in range(left + 1, right):
\n # \u5728\u533a\u95f4 [left, right] \u4e2d，k \u662f\u6700\u540e\u4e00\u4e2a\u88ab\u6233\u7684
\n # \u6233 k \u65f6，\u5b83\u7684\u90bb\u5c45\u662f left \u548c right（\u56e0\u4e3a\u533a\u95f4\u5185\u5176\u4ed6\u6c14\u7403\u5df2\u88ab\u6233\u5b8c）
\n coins = nums[left] * nums[k] * nums[right]
\n dp[left][right] = max(
\n dp[left][right],
\n dp[left][k] + dp[k][right] + coins, # \u5de6\u5b50\u533a\u95f4 + \u53f3\u5b50\u533a\u95f4 + \u6233 k \u5f97\u5206
\n )<\/p>\n
# dp[0][n-1] \u8868\u793a\u533a\u95f4 (0, n-1)，\u5373\u5168\u90e8\u6c14\u7403
\n return dp[0][n – 1]<\/p>\n
# ========== \u7c7b\u578b\u56db：\u72b6\u6001\u538b\u7f29 DP ==========
\ndef min_cost_tsp(graph: List[List[int]]) -> int:
\n """
\n \u65c5\u884c\u5546\u95ee\u9898（TSP）\u7684\u72b6\u6001\u538b\u7f29 DP \u89e3\u6cd5
\n \u65f6\u95f4\u590d\u6742\u5ea6：O(n\u00b2 * 2\u207f)
\n \u7a7a\u95f4\u590d\u6742\u5ea6：O(n * 2\u207f)<\/p>\n
\u72b6\u6001\u538b\u7f29\u7684\u9002\u7528\u573a\u666f：n \u5f88\u5c0f（\u901a\u5e38 n \u2264 20），\u4e14\u72b6\u6001\u9700\u8981\u8bb0\u5f55"\u54ea\u4e9b\u5143\u7d20\u5df2\u88ab\u4f7f\u7528"
\n \u4f7f\u7528 bitmask \u8868\u793a\u96c6\u5408：\u7b2c i \u4f4d\u4e3a 1 \u8868\u793a\u8282\u70b9 i \u5df2\u88ab\u8bbf\u95ee
\n dp[mask][i] \u8868\u793a\u8bbf\u95ee\u4e86 mask \u8868\u793a\u7684\u8282\u70b9\u96c6\u5408，\u5f53\u524d\u5728\u8282\u70b9 i \u7684\u6700\u5c0f\u4ee3\u4ef7
\n """
\n n = len(graph)
\n INF = float("inf")
\n # dp[mask][i]：mask \u662f\u4f4d\u63a9\u7801\u96c6\u5408，i \u662f\u5f53\u524d\u6240\u5728\u8282\u70b9
\n dp = [[INF] * n for _ in range(1 << n)]
\n dp[1][0] = 0 # \u4ece\u8282\u70b9 0 \u51fa\u53d1，mask=1（\u53ea\u6709\u8282\u70b9 0 \u88ab\u8bbf\u95ee）<\/p>\n
for mask in range(1 << n):
\n for i in range(n):
\n if dp[mask][i] == INF:
\n continue # \u5f53\u524d\u72b6\u6001\u4e0d\u53ef\u8fbe，\u8df3\u8fc7
\n for j in range(n):
\n if mask & (1 << j): # \u8282\u70b9 j \u5df2\u5728\u96c6\u5408\u4e2d
\n continue
\n new_mask = mask | (1 << j) # \u52a0\u5165\u8282\u70b9 j
\n dp[new_mask][j] = min(
\n dp[new_mask][j],
\n dp[mask][i] + graph[i][j],
\n )<\/p>\n
# \u56de\u5230\u8d77\u70b9 0 \u7684\u6700\u5c0f\u4ee3\u4ef7
\n full_mask = (1 << n) – 1
\n return int(min(dp[full_mask][i] + graph[i][0] for i in range(n)))<\/p>\n
\u6bcf\u7c7b DP \u7684\u6838\u5fc3\u5dee\u5f02\u4e0d\u5728\u4ee3\u7801\u91cf，\u800c\u5728\u72b6\u6001\u5b9a\u4e49\u7684\u7ef4\u5ea6\u3002\u7ebf\u6027 DP \u7684\u72b6\u6001\u662f\u4e00\u7ef4\u4e0b\u6807，\u80cc\u5305 DP \u7684\u72b6\u6001\u662f\u4e00\u7ef4\u5bb9\u91cf，\u533a\u95f4 DP \u7684\u72b6\u6001\u662f\u4e8c\u7ef4\u533a\u95f4\u7aef\u70b9，\u72b6\u6001\u538b\u7f29 DP \u7684\u72b6\u6001\u662f\u4f4d\u63a9\u7801\u3002\u638c\u63e1\u4e86\u8fd9\u4e2a\u7ef4\u5ea6\u89c4\u5f8b，\u770b\u5230\u65b0\u9898\u5c31\u80fd\u5feb\u901f\u5f52\u7c7b\u3002<\/p>\n
DP \u4e0d\u662f\u4e07\u80fd\u7684，\u5b83\u6709\u4e09\u4e2a\u66ff\u4ee3\u65b9\u6848\u9700\u8981\u6743\u8861：<\/p>\n
\u8d2a\u5fc3：\u5f53\u95ee\u9898\u6ee1\u8db3"\u8d2a\u5fc3\u9009\u62e9\u6027\u8d28"（\u5c40\u90e8\u6700\u4f18\u80fd\u63a8\u5bfc\u5168\u5c40\u6700\u4f18）\u65f6，\u8d2a\u5fc3\u6bd4 DP \u66f4\u9ad8\u6548\u3002\u4f8b\u5982\u6d3b\u52a8\u9009\u62e9\u95ee\u9898，DP \u662f O(n\u00b2)，\u8d2a\u5fc3\u662f O(n log n)\u3002\u8bc6\u522b\u65b9\u6cd5：\u770b\u80fd\u5426\u6784\u9020\u53cd\u4f8b\u3002\u5982\u679c\u80fd\u60f3\u5230\u4e00\u4e2a\u53cd\u4f8b\u8bc1\u660e"\u9009\u5f53\u524d\u6700\u4f18\u4e0d\u4e00\u5b9a\u662f\u5168\u5c40\u6700\u4f18"，\u90a3\u5c31\u4e0d\u80fd\u7528\u8d2a\u5fc3\u3002<\/p>\n
\u56de\u6eaf（DFS + \u526a\u679d）：\u5f53 n \u5f88\u5c0f\u4e14\u72b6\u6001\u8f6c\u79fb\u5f88\u96be\u7528 DP \u8868\u8fbe\u65f6，\u56de\u6eaf\u66f4\u5408\u9002\u3002\u6bd4\u5982"N \u7687\u540e"\u95ee\u9898，\u6bcf\u4e00\u6b65\u7684\u51b3\u7b56\u4f9d\u8d56\u524d\u51e0\u6b65\u7684\u5177\u4f53\u5e03\u5c40\u800c\u975e\u72b6\u6001\u6458\u8981，DP \u5f88\u96be\u5efa\u6a21，\u56de\u6eaf\u53cd\u800c\u76f4\u63a5\u3002<\/p>\n
\u8bb0\u5fc6\u5316\u641c\u7d22：\u8fd9\u662f DP \u81ea\u9876\u5411\u4e0b\u7684\u5b9e\u73b0\u65b9\u5f0f，\u6bd4\u586b\u8868\u6cd5\u66f4\u76f4\u89c2，\u4f46\u53ef\u80fd\u6709\u9012\u5f52\u6808\u6ea2\u51fa\u98ce\u9669\u3002\u5f53\u72b6\u6001\u8f6c\u79fb\u65b9\u5411\u4e0d\u660e\u786e（\u6bd4\u5982\u56fe DP）\u65f6，\u8bb0\u5fc6\u5316\u641c\u7d22\u66f4\u81ea\u7136\u3002<\/p>\n
\u9009\u62e9 DP \u7684\u573a\u666f\u662f：\u72b6\u6001\u7ef4\u5ea6\u53ef\u63a7（\u4e0d\u7206\u8868），\u8f6c\u79fb\u89c4\u5219\u6e05\u6670（\u80fd\u5199\u6210\u65b9\u7a0b），\u95ee\u9898\u89c4\u6a21\u8db3\u591f\u5927（\u56de\u6eaf\u4f1a\u8d85\u65f6）\u3002\u4e09\u8005\u540c\u65f6\u6ee1\u8db3，DP \u5c31\u662f\u7b2c\u4e00\u9009\u62e9\u3002<\/p>\n
DP \u7684\u96be\u70b9\u4e0d\u5728\u4e8e\u67d0\u9053\u9898\u7684\u4ee3\u7801\u5199\u4e0d\u51fa\u6765，\u800c\u5728\u4e8e"\u8fd9\u9053\u9898\u5c5e\u4e8e\u54ea\u4e00\u79cd DP"\u2014\u2014\u8fd9\u4e2a\u5224\u65ad，\u51b3\u5b9a\u4e86\u4f60\u4ece\u54ea\u4e2a\u89d2\u5ea6\u5207\u5165\u30027 \u6708\u901a\u8fc7\u5206\u7c7b\u8bad\u7ec3，\u6211\u5efa\u7acb\u4e86\u4e00\u4e2a\u4ece"\u770b\u5230\u9898\u5c31\u53d1\u61f5"\u5230"\u5148\u5206\u7c7b\u518d\u5efa\u6a21"\u7684\u601d\u7ef4\u8f6c\u53d8\u3002<\/p>\n
\u5c06 DP \u9898\u5f52\u7c7b\u540e，\u6bcf\u4e00\u7c7b\u90fd\u6709\u56fa\u5b9a\u7684\u72b6\u6001\u5b9a\u4e49\u6a21\u5f0f\u548c\u8f6c\u79fb\u5957\u8def\u30020-1 \u80cc\u5305\u7684"\u9009\u6216\u4e0d\u9009"\u3001\u533a\u95f4 DP \u7684"\u679a\u4e3e\u5206\u5272\u70b9"\u3001\u72b6\u6001\u538b\u7f29 DP \u7684"\u4f4d\u63a9\u7801\u96c6\u5408"\u2014\u2014\u8fd9\u4e9b\u90fd\u662f\u53ef\u590d\u7528\u7684\u601d\u7ef4\u6a21\u5757\u3002\u5269\u4e0b\u7684\u5de5\u4f5c\u5c31\u662f\u5728\u6a21\u677f\u57fa\u7840\u4e0a\u9002\u914d\u9898\u76ee\u7ec6\u8282\u3002<\/p>\n
\u7ec3 DP，\u4e0d\u9700\u8981\u6c42\u591a，\u9700\u8981\u6c42\u901a\u3002\u628a\u6bcf\u4e00\u7c7b DP \u7684\u7ecf\u5178\u9898\u505a\u5230\u80fd\u5728\u767d\u677f\u4e0a\u4ece\u5934\u63a8\u5bfc，\u6bd4\u5237 100 \u9053\u6742\u9898\u66f4\u6709\u610f\u4e49\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u52a8\u6001\u89c4\u5212\u9898\u578b\u5206\u7c7b\u4e0e\u89e3\u9898\u5957\u8def\u603b\u7ed3：\u4ece\u5165\u95e8\u5230\u5de5\u7a0b\u601d\u7ef4\u7684\u8dc3\u8fc1
\n\u4e00\u3001\u6df1\u5ea6\u5f15\u8a00\u4e0e\u573a\u666f\u75db\u70b9：\u4e3a\u4ec0\u4e48 DP \u9898\u4e00\u770b\u5c31\u4f1a，\u4e00\u5199\u5c31\u5e9f
\n\u52a8\u6001\u89c4\u5212\u662f\u7b97\u6cd5\u9762\u8bd5\u7684\\”\u8fc7\u6ee4\u5668\\”\u3002\u51e0\u4e4e\u6240\u6709\u5927\u5382\u7684\u9762\u8bd5，DP \u9898\u7684\u51fa\u73b0\u9891\u7387\u4ec5\u6b21\u4e8e\u6570\u636e\u7ed3\u6784\u7684\u5e94\u7528\u9898\u3002\u4f46 DP \u53c8\u662f\u6700\u8ba9\u4eba\u6709\u632b\u8d25\u611f\u7684\u65b9\u5411\u2014\u2014\u770b\u9898\u89e3\u89c9\u5f97\u903b\u8f91\u901a\u7545，\u81ea\u5df1\u5199\u603b\u662f\u5728\u72b6\u6001\u5b9a\u4e49\u6216\u8f6c\u79fb\u65b9\u7a0b\u4e0a\u5361\u58f3\u3002
\n7 \u6708\u6211\u628a LeetCode \u4e0a\u7684 DP \u9898\u6309\u9898\u578b\u505a\u4e86\u7cfb\u7edf\u5206\u7c7b\u548c\u96c6\u4e2d\u8bad\u7ec3\u3002\u4e00\u4e2a\u5173\u952e\u53d1\u73b0\u662f：<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[2692,4323,427],"topic":[],"class_list":["post-86169","post","type-post","status-publish","format-standard","hentry","category-server","tag-leetcode","tag-4323","tag-427"],"yoast_head":"\n