[programmers]43165ターゲット番号

こんにちは!珂太での生存記録を開始した.
ブログでアルゴリズムの問題を公表しても、著作権の問題は気になりますが、プログラマーのQ&Aページから見ると、非商業的な用途でいいです.
白俊も問題のリンクをアップロードできると言っているので、負担なくアップロードしなければならない.

質問する

ソース:プログラマコードテスト練習
私たちはまず問題の構成を理解した.0から、配列に含まれる数値が加算され、減算されます.各depthには2^dノードのツリーがあります.
問題の上部にもヒントがあります.DFS/BFSと書いてありますコードを簡単に作成できます.

に答える

function solution(numbers, target) {
  let answer = 0;
  const willVisit = [[0, 0]];

  while (willVisit.length > 0) {
    const [value, depth] = willVisit.shift();

    if (depth === numbers.length && value === target) {
      answer++;
      continue;
    }

    if (depth < numbers.length) {
      willVisit.push([value + numbers[depth], depth + 1]);
      willVisit.push([value - numbers[depth], depth + 1]);
    }
  }

  return answer;
}

私は自信を持ってコードを提出しました.これは効率的に最悪です.途中で枝打ちの条件を入れたが、失敗した.
だからいっそ問題を考える方法を変えた.前のノードが次のノードに影響するので、DPを使って解放してもいいですか?
配列を操作する方法の呼び出しも少なくなったので、できるかもしれないと思います.

function solution(numbers, target) {
  const dp = Array.from(Array(numbers.length + 1), () => new Array());

  dp[0] = [0];

  for (let i = 0; i < numbers.length; i++) {
    for (const d of dp[i]) {
      dp[i + 1].push(d + numbers[i]);
      dp[i + 1].push(d - numbers[i]);
    }
  }

  return dp[numbers.length].filter((d) => d === target).length;
}

😀 幸い成功したしかし、コードを書くときに疑問が生じた.なぜダイナミックプログラミングと呼ぶのですか?だから制作者を探して「カッコよかったから起きたんだよ」誰かが...

🕶 ポスト

この問題では、2 D配列を宣言して値を保存する必要があります.

const dp = [];

for (let i = 0; i <= numbers.length; i++) {
	dp.push([]);
}

最初はこのように設定されていましたが、コードは少し醜く見えました.
Array.fromメソッド(MDN)
次のドキュメントを見るとArrayfrom()のパラメータで、1つ目は類似配列オブジェクトまたはiterableオブジェクト、2つ目はmapfnです.

const dp = Array.from(Array(numbers.length + 1), () => new Array());

2 D配列を直接作成できます.

DFSバージョン

function solution(numbers, target) {
  function DFS(value, depth) {
    if (depth === numbers.length) {
      if (value === target) return 1;
      else return 0;
    } else {
      return (
        DFS(value + numbers[depth], depth + 1) +
        DFS(value - numbers[depth], depth + 1)
      );
    }
  }

  return DFS(0, 0);
}

BFSもタイムアウトしたので、もちろんDFSもタイムアウトすると思います.しかし、より効率的な
アレイのアクセス方法と文の重複は、パフォーマンスの低下を招く可能性がありますが、機能が不足しているため、正確な判断ができません.