動的計画法とは何ですか？

動的計画法は、アルゴリズム設計におけるアプローチの1つです。

問題を重複する部分問題に分解し、その部分問題を繰り返し解くことによって解きます。元の問題を解くために

注：Divide and conquerは、互いに独立した部分問題への分解を重視します。

フィボナッチ数列

部分問題の定義： F(n) = F(n-1) + F(n-2)

繰り返し：2からnまでループし、上式を実行

応用1：階段の上り下り

問題解決のアイデア

• n段目に登るには、n-1段目で1段、n-2段目で2段登ります。
• F(n) = F(n-1) + F(n-2)
• 動的計画法の使用

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
 if(n < 2) {
 return 1;
 }
 let dp0 = 1;
 let dp1 = 1;
 for(let i= 2; i <= n; i++){
 let temp = dp0;
 dp0 = dp1;
 dp1 = dp0 + temp;
 }
 return dp1;
};
var climbStairs2 = function(n) {
 if(n < 2) {
 return 1;
 }
 let dp = [1, 1];
 for(let i= 2; i <= n; i++){
 dp[i] = dp[i-1] + dp[i-2];
 }
 return dp[n];
};

応用2：ハウスブレーキング

問題解決のアイデア

• f(k) = 最初のk部屋から盗める最大額
• Ak=k番目の家の資金数
• f(k) = max(f(k-2) + Ak, f(k-1))

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
 if(nums.length == 1){
 return nums[0];
 }
 if(nums.length == 0){
 return 0;
 }
 let dp0 = 0;
 let dp1= nums[0];
 for(let i=2; i <= nums.length; i++){
 const dp2 = Math.max(dp0 + nums[i-1], dp1);
 dp0 = dp1;
 dp1 = dp2;
 }
 return dp1;
};
var rob2 = function(nums) {
 if(nums.length == 1){
 return nums[0];
 }
 if(nums.length == 0){
 return 0;
 }
 let dp = [0, nums[0]];
 for(let i=2; i <= nums.length; i++){
 dp[i] = Math.max(dp[i-2]+ nums[i-1], dp[i-1]);
 }
 return dp[nums.length];
};

リングハウス213

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
 if(nums.length == 0){
 return 0;
 }
 if(nums.length == 1){
 return nums[0];
 }
 //最後の家を盗まない
 let res1 = rawRob(nums.slice(0, nums.length - 1));
 let res2 = rawRob(nums.slice(1));
 return Math.max(res1, res2);
};
function rawRob(nums){
 let dp0 = 0;
 let dp1 = nums[0];
 for(let i = 2; i <= nums.length; i++){
 const dp2 = Math.max(dp0 + nums[i-1], dp1);
 dp0 = dp1;
 dp1 = dp2;
 }
 return dp1;
}

知識ソース：