[leetcode]494. Target Sum -- JavaScript动态规划求解

快来打我* 2022-06-18 02:18 221阅读 0赞

先上代码：

var findTargetSumWays = function(nums, S) { 
        var sum = 0;
        nums.forEach(function(num){ 
            sum += num;
        });
        if(S>sum || S<-sum) return 0;
        var dp = [];
        dp[0+sum] = 1;
        var maxIndex = sum*2+1;
        nums.forEach(function(num){ 
            var tmp = [];
            for(var k=0;k<maxIndex;k++){
                if(dp[k] !== undefined && dp[k] !== 0){
                    if(tmp[k+num] === undefined){
                        tmp[k+num] = dp[k];
                    }else{
                        tmp[k+num] += dp[k];
                    }
    
                    if(tmp[k-num] === undefined){
                        tmp[k-num] = dp[k];
                    }else{
                        tmp[k-num] += dp[k];
                    }
                }
            }
            dp = tmp;
        });
        return dp[S+sum]===undefined?0:dp[S+sum];
    };

这道题一开始我是用递归的方式求解，但是会超时，因此就改用了动态规划。

下面说一下对于这道题我的理解，动态规划我也不是很熟悉，仅作为参考吧，欢迎指正。

首先说一下这道题主要的思路。

第一，在我们对数组的访问过程中，动态规划数组dp，是不断变化的。

第二，动态数组dp的含义：当我们对数据访问到某个阶段m的时候，dp\[n\]的含义就表示，在阶段m这一刻时，到达n的可选方式有dp\[n\]种。  
针对本道题来说，就是当我对数组访问到第m个的时候，那么这前m-1个数字所能组合成结果n的方式有dp\[n\]种。

第三，初始条件dp\[0+sum\] = 0的含义：当我们没有对数组进行任何访问的时候，我们可以获得总和0的选择有且只有一种，那就是数组中的数我们一个都不选。

发表评论取消回复

表情：

评论列表（有 0 条评论，221人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|动态规划No.21】leetcode494. 目标和

【算法|动态规划No.21】leetcode494. 目标和

素颜马尾好姑娘i/ 2024年04月27日 06:36/ 0 赞/ 76 阅读

相关 494 目标和（动态规划）

1. 问题描述：给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：例如

妖狐艹你老母/ 2023年01月24日 02:12/ 0 赞/ 60 阅读

相关 leetcode 377 Combination Sum IV 动态规划

377. Combination Sum IV Question Editorial Solution [My Submissions][] Total Acc

末蓝、/ 2022年09月24日 13:19/ 0 赞/ 2 阅读

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

题目 [https://leetcode.com/problems/target-sum/][https_leetcode.com_problems_target-sum

「爱情、让人受尽委屈。」/ 2022年09月10日 14:24/ 0 赞/ 166 阅读

相关 [leetcode]494. Target Sum -- JavaScript动态规划求解

先上代码： var findTargetSumWays = function(nums, S) { var sum = 0; num

快来打我*/ 2022年06月18日 02:18/ 0 赞/ 222 阅读

相关 leetcode 64. Minimum Path Sum DP动态规划

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

逃离我推掉我的手/ 2022年06月09日 11:42/ 0 赞/ 173 阅读

相关 leetcode 494. Target Sum目标和+背包问题+动态规划DP

You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you h

傷城~/ 2022年06月03日 00:56/ 0 赞/ 151 阅读

相关 LeetCode：494. Target Sum（计算目标数）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

比眉伴天荒/ 2022年04月13日 14:52/ 0 赞/ 146 阅读

相关【Leetcode】64. Minimum Path Sum（动态规划）

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom

「爱情、让人受尽委屈。」/ 2022年02月27日 13:34/ 0 赞/ 189 阅读

相关 LeetCode : 494. Target Sum 改变整数正负号求和

试题 You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now

迷南。/ 2021年06月24日 16:10/ 0 赞/ 335 阅读