【JavaScript】部分和を動的計画法で解く

またまたこの続き．

問題

n個の正の整数 a[0],a[1],…,a[n−1]a[0],a[1],…,a[n−1] と正の整数 AA が与えられる。これらの整数から何個かの整数を選んで総和が AA になるようにすることが可能か判定せよ。可能ならば "YES" と出力し、不可能ならば "NO" と出力せよ。

【制約】
・1≤n≤1001≤n≤100
・1≤a[i]≤10001≤a[i]≤1000
・1≤A≤100001≤A≤10000

【数値例】
　n=3n=3
　a=(7,5,3)a=(7,5,3)
　A=10A=10
　答え: YES (7 と 3 を選べばよい)

実装

結果がわかりやすいように出力を少しだけオリジナルに整形してます．

partialSum.js

const generate2DArray = (height, width) => {
    return [...Array(height)].map(() => Array(width).fill(0));
}

const partialSum = (numList, target) => {
    const dp = generate2DArray(numList.length + 1, target + 1); // 0行目・0列目を含む二次元配列を生成

    for (let col = 0; col < numList.length; col++) {
        for (let row = 0; row < target + 1; row++) {
            if (row >= numList[col]) {
                dp[col + 1][row] = Math.max(dp[col][row], dp[col][row - numList[col]] + numList[col])
            } else {
                dp[col + 1][row] = dp[col][row];
            }
        }
    }

    const result = dp[numList.length][target];
    return dp[numList.length][target] === target ? `YES:${result}` : `NO:${result}`;
}

const numList = [4, 6, 8];
console.log(partialSum(numList, 10)) // YES:10