前端程式員學好演算法系列（十）動態規劃-有解無憂

動態規劃整體思路是用遞回問題求解，然后對遞回程序中存在的大量重疊子問題進行優化，自頂向下的求解的思路為記憶化搜索，自底向上的解決問題的思想就是動態規劃，自頂向下的求解通常更好理解，我們理解后在改成自底向上的動態規劃求解；

劍指 Offer 10- I. 斐波那契數列
寫一個函式，輸入 n ，求斐波那契（Fibonacci）數列的第 n 項，斐波那契數列的定義如下：

F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契數列由 0 和 1 開始，之后的斐波那契數就是由之前的兩數相加而得出，

答案需要取模 1e9+7（1000000007），如計算初始結果為：1000000008，請回傳 1，

示例 1：

輸入：n = 2
輸出：1

示例 2：

輸入：n = 5
輸出：5

1.斐波那契的思想，就是我們求fib(n) 的解轉化為我們求 fib(n-1)+fib(n-2) ,fib(n-1) 我們可以轉化為 fib(n-1-1) + fib(n-2-1) ，隨著遞回進行，我們最后會得到n=1和 n=0的時候，同時我們知道 n=0時fib(0) 等于0 fib(1)等于1，

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n==0){
      return 0 
    }
    if(n==1){
       return 1
    }
    return fib(n-1) +fib(n-2)
};

2，上述代碼實作了一個斐波那契數列，但是對于斐波那契數列數列的時間復雜度是o的n次方的，因為我們求解的時候存在大量的重復求解，在上面的基礎上運用cache 快取計算結果 cache[n] 存在時直接求解，防止重復計算，

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) { 
    const cache = {
        0:0n,
        1:1n,
    };
    return Fibonacci(n) % 1000000007n;
    function Fibonacci(n){
        if(cache[n]!==undefined) {
            return cache[n]
        }
        cache[n] = Fibonacci(n - 1) + Fibonacci(n - 2)
        return cache[n];
    }
    
};

3.我們改造成動態規劃的求解方式，自下向上的解決問題，fibonacci = 0 時 fib(0) 為0 fibonacci 為1時fib(1) =1 fibonacci[2] = fibonacci[2-1] + fibonacci[2-2] ，我們求n的解只需求解 fibonacci[n]

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let fibonacci = [0,1];
    for(let i = 2; i <= n; i ++) {
        fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % (1e9 +7);
    }
    return fibonacci[n];

};

我們再看一個典型的斐波那契問題

70. 爬樓梯
假設你正在爬樓梯，需要 n 階你才能到達樓頂，

每次你可以爬 1 或 2 個臺階，你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數，

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂，
1. 1 階 + 1 階
2. 2 階

解題：該題和上題思路相同，我們就不深入講解了，我們使用記憶結果時可以使用物件，也可以使用陣列
1.自頂向下求解

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n,map={1:1,2:2}) {
    if (map[n]) return map[n];
    else map[n]=map[n-1]+map[n-2];
    return climbStairs(n - 1,map) + climbStairs(n - 2,map);
};

2. 自底向上求解

/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function (n) {
      let catche = [1,1]
      for(let i=2;i<=n;i++){
         catche[i] = catche[i-1] +catche[i-2] 
      }
      return catche[n]
};

343. 整數拆分
給定一個正整數 n，將其拆分為至少兩個正整數的和，并使這些整數的乘積最大化，回傳你可以獲得的最大乘積，

示例 1:

輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1，
示例 2:

輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36，

解題：

1.我們求分割n獲得的最大乘積，需要求把n分成 1和n-1的成績 2和n-2 的成績到n-1和1的最大成績，在這個結果中取最大值，
2.每次n可以選擇當前值，或者i*(n-i) 不在分割n，和i* 繼續分割n-i的結果i*d(n-i)

3.我們定義dp物件快取n的最大值的結果，防止重復求解

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {
     // 定義dp快取已求解的n的最大值 
     const dp = {}
     function d(n){
          if(n==1){
             return 1
          }
          if(dp[n]!==undefined){
               return dp[n]
          }
          let res = -1
          for(let i =1;i<n;i++){
            res = Math.max(res,i*(n-i),i*d(n-i))
            
          }
          dp[n] = res  
          return dp[n]
     }
     return d(n)
};

解題二

狀態陣列dp[i]表示：數字 i 拆分為至少兩個正整數之和的最大乘積，為了方便計算，dp 的長度是 n + 1，值初始化為 1，

顯然dp[2]等于 1，外層回圈從 3 開始遍歷，一直到 n 停止，內層回圈 j 從 1 開始遍歷，一直到 i 之前停止，它代表著數字 i 可以拆分成 j + (i - j)，但 j * (i - j)不一定是最大乘積，因為i-j不一定大于dp[i - j]（數字i-j拆分成整數之和的最大乘積），這里要選擇最大的值作為 dp[i] 的結果，

空間復雜度是 O(N)O(N)，時間復雜度是 O(N^2)O(N的2次方）

/**
 * @param {number} n
 * @return {number}
 */
var integerBreak = function(n) {

    const dp = new Array(n + 1).fill(1);
    for (let i = 3; i <= n; ++i) {
        for (let j = 1; j < i; ++j) {
            // 每次嘗試將n分割為 j+(i-j)的值
            dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
        }
    }
    return dp[n];

};

198. 打家劫舍
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房內都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警，

給定一個代表每個房屋存放金額的非負整數陣列，計算你不觸動警報裝置的情況下，一夜之內能夠偷竊到的最高金額，

示例 1：

輸入：[1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)，
偷竊到的最高金額 = 1 + 3 = 4 ，

解題：

1. 對于一個房間我們可以選擇偷取也可以選擇不偷取，如果偷取的話我們下次選擇需要選擇n+2的房間來嘗試偷取，結果取最大值

2. 我們求解的值是不考慮偷取當前房間和考慮偷取當前房間的最大值，res = Math.max(res,nums[i]+room(nums,i+2)) ，因為i+2 可能越界，因此當nums.length<=index時我們直接return 0

3.我們用tests 儲存是否已經偷過該房間，如果tests訪問過直接回傳值，如果沒有訪問過，我們把求解的n的值儲存在tests中

/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function(nums) {
     let tests = new Array(nums.length).fill(-1)
     
     function room(nums,index){
         if(nums.length<=index){
             return 0
         }
         if(tests[index]!==-1){
            return tests[index]
         }
         let res = 0
         for(let i =index;i<nums.length;i++){
             res = Math.max(res,nums[i]+room(nums,i+2))
         }
         tests[index] = res
         return tests[index]
 
     }
     
     return room(nums,0)
    
};

解法2

動態規劃方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )
由于不可以在相鄰的房屋闖入，所以在當前位置 n 房屋可盜竊的最大值，要么就是 n-1 房屋可盜竊的最大值，要么就是 n-2 房屋可盜竊的最大值加上當前房屋的值，二者之間取最大值
舉例來說：1 號房間可盜竊最大值為 33 即為 dp[1]=3，2 號房間可盜竊最大值為 44 即為 dp[2]=4，3 號房間自身的值為 22 即為 num=2，那么 dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5，3 號房間可盜竊最大值為 55
時間復雜度：O(n)O(n)，nn 為陣列長度

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

轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/25020.html

標籤：JavaScript

上一篇：vue父組件促發子組件中的方法

下一篇：父組件監聽子組件的生命周期