322. 零钱兑换
518. 零钱兑换 II
474. 一和零
494. 目标和
思路
1、暴力枚举, DFS
2、动态规划
代码
/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
var findTargetSumWays = function(nums, S) {
const sum = nums.reduce((total, cur) => total + cur, 0);
const len = nums.length;
let ret = 0;
if (Math.abs(sum) < Math.abs(S)) return ret;
function dfs(idx, sum) {
if (idx === len) {
if (sum === S) {
ret ++
}
return;
} else {
dfs(idx + 1, sum + nums[idx])
dfs(idx + 1, sum - nums[idx])
}
}
dfs(0, 0);
return ret;
};
/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
var findTargetSumWays = function(nums, S) {
// 计算和
const sum = nums.reduce((total, cur) => total + cur, 0);
// 获取dp数组每一子项的长度为 sum*2+1
const len = nums.length, itemLen = sum * 2 + 1;
let ret = 0;
// 不可能存在
if (Math.abs(sum) < Math.abs(S)) return ret;
const dp = Array(len)
dp[0] = Array(itemLen).fill(0);
// 考虑到第一个数为0的情况,+0,-0 有2种
if (nums[0] === 0) {
dp[0][sum] = 2
} else {
// 将nums[0]用上能够出现的情况
dp[0][sum - nums[0]] = 1
dp[0][sum + nums[0]] = 1
}
for(let i = 1; i < len; i ++) {
let cur = nums[i];
// 初始化其他的dp数组
dp[i] = Array(itemLen).fill(0)
for(let j = 0; j < itemLen; j ++) {
// 边界,如果越界则表示不能满足条件
let left = (j - nums[i] >= 0) ? j - nums[i] : 0;
let right = (j + nums[i] < itemLen) ? j + nums[i] : 0;
dp[i][j] = dp[i-1][left] + dp[i-1][right]
}
}
// 返回目标值
return dp[len-1][S + sum]
};
/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
// 因为每一行只和前一行的状态有关系,所以可以缩小空间复杂度
var findTargetSumWays = function(nums, S) {
// 计算和
const sum = nums.reduce((total, cur) => total + cur, 0);
// 获取dp数组每一子项的长度为 sum*2+1
const len = nums.length, itemLen = sum * 2 + 1;
let ret = 0;
// 不可能存在
if (Math.abs(sum) < Math.abs(S)) return ret;
const dp = Array(len)
dp[0] = Array(itemLen).fill(0);
// 考虑到第一个数为0的情况,+0,-0 有2种
if (nums[0] === 0) {
dp[0][sum] = 2
} else {
// 将nums[0]用上能够出现的情况
dp[0][sum - nums[0]] = 1
dp[0][sum + nums[0]] = 1
}
for(let i = 1; i < len; i ++) {
let cur = nums[i];
// 创建临时数组用来存储当前行的情况
let tmp = Array(itemLen).fill(0)
for(let j = 0; j < itemLen; j ++) {
// 边界
let left = (j - nums[i] >= 0) ? j - nums[i] : 0;
let right = (j + nums[i] < itemLen) ? j + nums[i] : 0;
tmp[j] = dp[left] + dp[right]
}
// 将当前行计算完情况后重新赋值回去
dp = tmp;
}
// 返回
return dp[S + sum]
};
复杂度分析
时间复杂度 DFS:#card=math&code=O%282%5EN%29) DP: #card=math&code=O%28N%5E2%29) DP2: #card=math&code=O%28N%5E2%29)
空间复杂度 DFS: #card=math&code=O%28N%29) DP: #card=math&code=O%28N%5E2%29) DP2: #card=math&code=O%28N%29)