paizaラーニング レベルアップ問題集 DPメニュー JavaScript 最安値を達成するには 2

最安値を達成するには 2 (paizaランク B 相当)

解答例

とりあえず、うまくいかないところも含めて、最小値を求める。
dpの初期値は、n個以上買う時はn+5個で十分、最小値を求めるので、初期値は無限大。

うまくいかないところ、n個以上での最安値を埋めていく。
dp2を用意して、dpを元に作っていく。
最小値を求めるのに、dpのi以上をsliceしてreduceを用いた。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, a, b] = lines[0].split(" ").map(Number);
//とりあえず、うまくいかないところも含めて、最小値を求める。
const dp = Array(n + 5).fill(Infinity);//n個以上買う時はn+5個で十分、最小値を求めるので、初期値は無限大
dp[0] = 0;//0個の時は0円
for (let i = 1; i < n + 5; i++) {
  if (i >= 2) {
    dp[i] = Math.min(dp[i], dp[i - 2] + a);
  } 
  if(i >= 5){
    dp[i] = Math.min(dp[i], dp[i - 5] + b);
  }
}
//うまくいかないところ、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよい
const dp2 = Array(n + 5);// n 個以上のりんごを買うのに必要な金額の最小値の配列
for (let i = 1; i < n + 5; i++) {
  //dpのインデックスi以上での最小値
  dp2[i] = dp.slice(i).reduce((a, b) => Math.min(a, b));
}
console.log(dp2[n]);

dp2無しでも、dpを書き換える形でできる。前から変えていけば、後には影響が出ない。

//うまくいかないところ、n個以上での最安値を埋めていく
// n 個以上のりんごを買うのに必要な金額の最小値
for (let i = 1; i < n + 5; i++) {
  //dpのインデックスi以上での最小値
  dp[i] = dp.slice(i).reduce((a, b) => Math.min(a, b));
}
console.log(dp[n]);