[21/10/04 KATA NINJA] Target Sum
コード#コード#
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var findTargetSumWays = function(nums, target) {
let count = 0;
DFS(0,0);
return count;
function DFS(current,level){
if(level === nums.length - 1){
if(target === current+nums[level]) count++;
if(target === current-nums[level]) count++;
}else{
if(validation(current+nums[level],level+1)) DFS(current+nums[level],level+1);
if(validation(current-nums[level],level+1)) DFS(current-nums[level],level+1);
}
}
function validation(next,start){
const sub = nums.slice(start).reduce((a,b)=>a+b)
return next-sub <= target && target <= next+sub
}
};
上のコードの性能は少し臭いです.23%のパフォーマンス.
アノテーションテンプレートを使用して改善します.
コードの改良
var findTargetSumWays = function(n, t) {
const memo = {};
return DFS(t);
function DFS(target, level = 0) {
const hash = `${level},${target}`
if(memo[hash]){
return memo[hash]
}
if(level === n.length - 1){
// 레벨이 마지막 인덱스라면
// 1. 마지막 인덱스 값이 0이면서 현재 값이 0이라면 -> 2번 늘려준다 (+,-) 해도 같으므로
// 2. 마지막 인덱스 값이 0이 아니면서 다음 값과 현재 타겟 값을 절대 비교해주었을 때 같으면 -> 1회
// 3. 아니라면 0을 리턴
if(n[level] === 0 && target === 0 ) return 2;
if(n[level] === target || n[level] === -target) return 1;
return 0;
}
const res = DFS(target - n[level],level+1) + DFS(target+n[level],level+1)
memo[hash] = res;
return res;
}
};
注記クリップが追加されましたが、速度が遅くなりました...?次のコードをコメントに変更する必要があります.
if(memo[hash]){
return memo[hash]
}
//if(memo[hash] !== undefined) return memo[hash] 로 바꾸어줘야함.
次の実行速度が表示されます.(why?)dpで解くのがもっと速い。
もう一度解いてみます.
var findTargetSumWays = function(nums, target) {
let total = nums.reduce((a,b)=>a+b);
const dp = [...new Array(nums.length+1)].map(()=>[...new Array(total*2+1)].map(()=>0));
// meaning : row -> 몇 개의 요소가 관여하였는가. column -> total을 기준으로 큰 index는 양수 작은 index는 음수이다. (관여된 요소의)총합을 의미한다.
if(total < Math.abs(target)){
// 다 더하거나 다 뺄때보다 오히려 타겟이 크면 찾을 수 없다.
return 0;
}
if(nums.length === 1 && Math.abs(total) === Math.abs(target)){
return 1;
}
if(nums.length === 1 && Math.abs(total) !== Math.abs(target)){
return 0;
}
dp[0][total] = 1; // what?
for(let r=0;r<nums.length;r++){
// dp 배열의 nums.length 로우에 값이 채워져있다. 종료되면
for(let c=0;c<dp[r].length;c++){
if(dp[r][c] !== 0){
// dp[r+1][c+nums[r]]가 몇개 나올수있는가
// dp[r][c]를 더 해준다.
// 이전까지 몇개가 나왔는지 더해준다.
dp[r+1][c+nums[r]] += dp[r][c];
dp[r+1][c-nums[r]] += dp[r][c];
}
}
}
return dp[nums.length][total + target];
};
Reference
この問題について([21/10/04 KATA NINJA] Target Sum), 我々は、より多くの情報をここで見つけました https://velog.io/@rat8397/211004-KATA-NINJA-Target-Sumテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol