题解 | #目标和# [P3]

目标和

http://www.nowcoder.com/practice/7fc06e2162f048658252fac542fcb1e8

时间: O(maxSum*N)
空间: O(maxSum)

DP 定义:
  DP(i, j): # of ways num[0, i] can sum to j.
  DP(i, j) = DP(i-1, j + num[i]) + DP(i-1, j - num[i])
import java.util.*;

public class Solution {
    public int findTargetSumWays (int[] nums, int target) {
      if (nums.length == 0) return 0;

      // 0<=sum(nums[i])<=1000, so -1000 <= sum <= 1000
      int[] arrS = new int[2001];  
      // for arrS[j], j = sum + 1000;
      // for nums[0], sum = nums[0] or -nums[0]
      arrS[nums[0]+1000]++; arrS[-nums[0]+1000]++;
      
      for (int i = 1; i < nums.length; i++) {
        int tmp[] = new int[2001];
        int num = nums[i];
        // i-1的sum的范围是 [-1000+num, 1000-num]
        for (int sum = -1000+num; sum <= 1000-num; sum++) {
          int j = sum + 1000;       // j = sum + 1000;
          tmp[j+num] += arrS[j]; // +
          tmp[j-num] += arrS[j]; // -
        }
        // 为方便理解,若完全对照定义,上面的loop也可以写成:
        // int num = nums[i];
        // for (int sum = -1000; sum <= 1000; sum++) {
        //   int j = sum + 1000;
        //   if (j-num >= 0)
        //     tmp[j] += arrs[j-num];
        //   if (j+num <= 2000)
        //     tmp[j] += arrs[j+num];
        // }
        arrS = tmp;  // swap
      }
      
      return arrS[target + 1000];
    }
}
DP是真的烦 文章被收录于专栏

只是为了把DP的题集中一下方便自己复习

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 12:04
毕业生招你惹你了,问一个发薪日来一句别看网上乱七八糟的你看哪个工作没有固定发薪日扭头就取消了面试就问了一句公司都是这个态度吗还搞上人身攻击了...
程序员小白条:呃呃呃,都还没面试,我都不会问这么细,何况通不通过,去不去都另说,你没实力和学历的话,在外面就这样,说实话没直接已读不回就不错了,浪费时间基本上
点赞 评论 收藏
分享
06-19 19:06
门头沟学院 Java
码农索隆:别去东软,真学不到东西,真事
点赞 评论 收藏
分享
06-26 17:24
已编辑
宁波大学 golang
迷失西雅图:别给,纯kpi,别问我为什么知道
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务