funclastStoneWeightII(stones []int)int { sum := 0 for _, v := range stones { sum += v } n, m := len(stones), sum/2 dp := make([][]bool, n+1) for i := range dp { dp[i] = make([]bool, m+1) } dp[0][0] = true for i, weight := range stones { for j := 0; j <= m; j++ { if j < weight { dp[i+1][j] = dp[i][j] } else { dp[i+1][j] = dp[i][j] || dp[i][j-weight] } } } for j := m; ; j-- { if dp[n][j] { return sum - 2*j } } }
classSolution: deflastStoneWeightII(self, stones: List[int]) -> int: total = sum(stones) n, m = len(stones), total // 2 dp = [[False] * (m + 1) for _ inrange(n + 1)] dp[0][0] = True
for i inrange(n): for j inrange(m + 1): if j < stones[i]: dp[i + 1][j] = dp[i][j] else: dp[i + 1][j] = dp[i][j] or dp[i][j - stones[i]] ans = None for j inrange(m, -1, -1): if dp[n][j]: ans = total - 2 * j break return ans
publicclassSolution { publicintLastStoneWeightII(int[] stones) { int sum = 0; foreach (int weight in stones) { sum += weight; } int m = sum / 2; bool[] dp = newbool[m + 1]; dp[0] = true; foreach (int weight in stones) { for (int j = m; j >= weight; --j) { dp[j] = dp[j] || dp[j - weight]; } } for (int j = m;; --j) { if (dp[j]) { return sum - 2 * j; } } } }
[sol2-Golang]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
funclastStoneWeightII(stones []int)int { sum := 0 for _, v := range stones { sum += v } m := sum / 2 dp := make([]bool, m+1) dp[0] = true for _, weight := range stones { for j := m; j >= weight; j-- { dp[j] = dp[j] || dp[j-weight] } } for j := m; ; j-- { if dp[j] { return sum - 2*j } } }
[sol2-JavaScript]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
var lastStoneWeightII = function(stones) { let sum = 0; for (const weight of stones) { sum += weight; } const m = Math.floor(sum / 2); const dp = newArray(m + 1).fill(false); dp[0] = true; for (const weight of stones) { for (let j = m; j >= weight; --j) { dp[j] = dp[j] || dp[j - weight]; } } for (let j = m;; --j) { if (dp[j]) { return sum - 2 * j; } } };
[sol2-Python3]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution: deflastStoneWeightII(self, stones: List[int]) -> int: total = sum(stones) n, m = len(stones), total // 2 dp = [False] * (m + 1) dp[0] = True
for weight in stones: for j inrange(m, weight - 1, -1): dp[j] |= dp[j - weight] ans = None for j inrange(m, -1, -1): if dp[j]: ans = total - 2 * j break return ans
intlastStoneWeightII(int* stones, int stonesSize) { int sum = 0; for (int i = 0; i < stonesSize; i++) { sum += stones[i]; } int m = sum / 2; int dp[m + 1]; memset(dp, 0, sizeof(dp)); dp[0] = true; for (int i = 0; i < stonesSize; ++i) { for (int j = m; j >= stones[i]; --j) { dp[j] = dp[j] || dp[j - stones[i]]; } } for (int j = m;; --j) { if (dp[j]) { return sum - 2 * j; } } }
复杂度分析
时间复杂度:O(n\cdot \textit{sum})。其中 n 是数组 stones 的长度,sum 为 stones 所有元素之和。