LeetCode 494. Target Sum【0 |
您所在的位置：网站首页 › leetcode494 › LeetCode 494. Target Sum【0 |
LeetCode 494. Target Sum【0
|
文章目录
题目描述知识点结果实现码前思考代码实现码后反思
二刷代码
题目描述
动态规划 结果
我这道题目没有想出来，直接看的题解，实在是想不出。 原来这道题目就是0-1背包，通过 dp数组保存前n个物品的所有可能和的方案数 ，从而避免了重复计算。避免了暴力的 O ( 2 n ) O(2^n) O(2n)； （我有想到暴力 O ( 2 n ) O(2^n) O(2n)，但是不知道怎么优化它，现在想来，当初0-1背包问题的提出也是为了优化 O ( 2 n ) O(2^n) O(2n)啊！！！） 代码实现 //这居然是一个0-1背包的变形问题 //恰好装满背包问题+求方案数 //dp[i][j]表示的含义是在选择前i个数字的前提下，等于j的方案数 class Solution { public: int findTargetSumWays(vector& nums, int S) { //由于总和最大为1000，那么最小就是-1000 int m = nums.size(); int n = 2010; if(S>1000 || S |
【本文地址】