leetcode 494. Target Sum | 494. 目标和（动态规划）

「爱情、让人受尽委屈。」 2022-09-10 14:24 134阅读 0赞

## 题目 ##

[https://leetcode.com/problems/target-sum/][https_leetcode.com_problems_target-sum]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

经典 dp，直接看草稿：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

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];
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_target-sum]: https://leetcode.com/problems/target-sum/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/7398ccd3712d41709063e6ac533565ae.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/05bbcdd418dd453e9f1d3c53fd486877.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/44af7237d26345918f06e1e6901e9b3d.png