leetcode Dynamic Programming

leetcode 494题

Posted by franki on February 6, 2021

leetcode 494题 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例1:

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

思路

1 递归搜索

2 动态规划

代码

// recursion
var findTargetSumWays = function (nums, S) {
  let n = 0;
  const loop = (idx, sum) => {
    if (nums.length > idx) {
      loop(idx + 1, sum + nums[idx]);
      loop(idx + 1, sum - nums[idx]);
    } else {
      sum === S && n++;
    }
  };
  loop(0, 0);
  return n;
}

// dynamic programming
var findTargetSumWays = function(nums, S) {
    if (nums == null || nums.length == 0) return 0;
    var sums = 0;
    nums.forEach(num => sums += num);
    if (sums < S || (S + sums) % 2 == 1) return 0;
    var p = (S + sums) >> 1;
    var dp = new Array(p + 1).fill(0);
    dp[0] = 1;
    nums.forEach(num => {
        for (var i = p; i >= num; i--) {
            dp[i] += dp[i - num];
        }
    })
    return dp[p];
};

复杂度分析

  • 时间复杂度: O(2^n)/O(n*m)
  • 空间复杂度: O(1)/O(n*m)
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS