這里寫目錄標題
- 題目分析：
- 狀態表示：
- 狀態轉移方程：
- 初始化：
- 填表順序：
- 返回值：
- 代碼呈現：
- 優化版本：
- 代碼呈現：
題目分析：
狀態表示：
狀態轉移方程：
初始化：
填表順序：
返回值：
返回最小質量的石頭
代碼呈現：
class Solution {public int lastStoneWeightII(int[] stones) {int n = stones.length; int sum = 0; for(int i = 0; i < n; i++) sum += stones[i];int aim = sum/2;int[][] dp = new int[n+1][aim+1];for(int i = 1; i <= n; i++)for(int j = 0; j <= aim; j++){dp[i][j] = dp[i-1][j];if(j >= stones[i-1])dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-stones[i-1]] + stones[i-1]);}return sum - 2 * dp[n][aim]; }
}
優化版本：
不知道怎么優化看前面：鏈接: 點擊
代碼呈現：
//空間優化：int n = stones.length; int sum = 0; for(int i = 0; i < n; i++) sum += stones[i];int aim = sum/2;int[] dp = new int[aim+1];for(int i = 1; i <= n; i++)for(int j = aim; j >= stones[i-1]; j--){dp[j] = Math.max(dp[j],dp[j-stones[i-1]] + stones[i-1]);}return sum - 2 * dp[aim];
)
)
