題目

https://leetcode.com/problems/target-sum/

題解

經典 dp，直接看草稿：

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int n : nums) {sum += n;}if (Math.abs(target) > sum) return 0;int[][] dp = new int[nums.length][2 * sum + 1];int OFFSET = sum;dp[0][-nums[0] + OFFSET] += 1;dp[0][+nums[0] + OFFSET] += 1; // 不能寫成=1，因為可能和上一行重合for (int i = 1; i < nums.length; i++) {for (int j = 0; j < 2 * sum + 1; j++) {int L = 0, R = 0;if (j - nums[i] >= 0) L = dp[i - 1][j - nums[i]];if (j + nums[i] < 2 * sum + 1) R = dp[i - 1][j + nums[i]];dp[i][j] = L + R;}}return dp[nums.length - 1][target + OFFSET];} }

總結

以上是生活随笔為你收集整理的leetcode 494. Target Sum | 494. 目标和（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。