Target Sum（C++目标和）

谁践踏了优雅 2022-09-08 11:44 171阅读 0赞

(1) dp

  1. class Solution {
  2. public:
  3.     int findTargetSumWays(vector<int>& nums, int t) {
  4.         int sum=0;
  5.         for(int i=0;i<nums.size();i++) {
  6.             sum+=nums[i];
  7.         }
  8.         int target=sum-t;
  9.         if(target<0 || target%2==1) return 0;
  11.         target/=2;
  12.         vector<vector<int>> v(target+1,vector<int>(nums.size()+1,0));
  13.         v[0][0]=1;
  14.         for(int i=0;i<target+1;i++) {
  15.             for(int j=1;j<nums.size()+1;j++) {
  16.                 if(i>=nums[j-1]) {
  17.                     v[i][j]=v[i][j-1]+v[i-nums[j-1]][j-1];
  18.                 } else v[i][j]=v[i][j-1];
  19.             }
  20.         }
  21.         return v[target][nums.size()];
  22.     }
  23. };

发表评论

表情：
评论列表 （有 0 条评论，171人围观）

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

相关阅读

    相关 494.目标和

    ![在这里插入图片描述][67f4b8e3f6ed4ccd9f395c038504f144.png] 1. 回溯算法 这题和之前做的那些排列、组合的回溯稍微有些不同，你

    旧城等待，旧城等待，/ 0 赞/ 118 阅读

    相关 目标和

    一、前言 动态规划相关问题。 问题来源LeetCode 494 问题链接：[https://leetcode-cn.com/problems/target-sum][

    悠悠悠悠/ 0 赞/ 195 阅读

    相关 494. 目标和

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

    向右看齐向右看齐/ 0 赞/ 205 阅读