前端程式員學好演算法系列(十)動態規劃

来源:https://www.cnblogs.com/kbnet/archive/2020/07/28/13390461.html

動態規劃整體思路是用遞歸問題求解,然後對遞歸過程中存在的大量重疊子問題進行優化, 自頂向下的求解的思路為記憶化搜索,自底向上的解決問題的思想就是動態規劃,自頂向下的求解通常更好理解,我們理解後在改成自底向上的動態規劃求解; 劍指 Offer 10- I. 斐波那契數列寫一個函數,輸入 n ,求斐波那 ...


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

劍指 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 階 + 12. 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];
};

 


您的分享是我們最大的動力!

更多相關文章
  • java JDBC資料庫連接池技術 為什麼使用資料庫連接池? 這個原因與為什麼使用線程池有點相似,都是為了提高資源的利用率,減少申請時間的浪費,提高程式的運行效率。 資料庫連接池的基本思想就是為資料庫連接建立一個“緩衝池”。預先在緩衝池中放入一定數量的連接,當需要建立數 據庫連接時,只需從“緩衝池” ...
  • 一、 體驗生命周期 xml中TextView用於顯示一行文字 載入佈局的函數setContentView() 代碼requestWindowFeature(Window.FEATURE_NO_TITLE)用於將活動的標題隱藏。 建立layout.xml,然後註冊到一個新建的活動類中,最後還得把活動類 ...
  • 最近有個需求,要實現列表的itemView拖拽後,交換位置。網上搜索了一番,發現RecyclerView來實現此方案很容易,RecyclerView的預設幾個api很強大,只需幾行代碼就可以實現簡單的拖拽需求。 有一篇文章值得推薦給大家,RecyclerView 擴展(二) - 手把手教你認識Ite ...
  • 現在的社交類App,聊天都是標配,此外在聊天的基礎上還衍生出了很多功能,如表情包,背景,氣泡等。 某一天測試給我提了一個bug,說,軟鍵盤彈起收攏的時候聊天背景圖會抖動。要解決下。我很納悶,這塊用的不是ImageView來實現的麽,Android的效果是咋樣,就是咋樣啊。我咋知道怎麼改呢? 向測試小 ...
  • WEB開發約定 文件命名 【√】小寫的英文字母、數字和下劃線的組合 【!】不得含漢字、空格和特殊字元 命名規範好處 ①方便團隊理解代碼開發的文件含義 ②使用“按名稱排例”的命令時,同類文件能夠排列在一起 以便查找、修改、替換、計算負載量等操作 (一)HTML的命名原則 |文件類型 |命名舉例(小寫) ...
  • jQuery操作數組主要有兩種方式: 普通數組 $.each(array,function(k,v){ //... }); 關聯數組,{"id":10,"name":"tom"} 索引數組,[1,2,3,4,5,6,7,8,9] k:如果是關聯是鍵名,如果是索引是下標(從0開始; vo:是元素值; ...
  • MVC 與 Vue 本文寫於 2020 年 7 月 27 日 首先有個問題:Vue 是 MVC 還是 MVVM 框架? 維基百科告訴我們:MVVM 是 PM 的變種,而 PM 又是 MVC 的變種。 所以一定程度上來說,三者的思想方向是一樣的。所以不管 Vue 是 MVC 還是 MVVM 或者都不是 ...
  • 如果父組件監聽到子組件掛載mounted做一些邏輯處理 1、使用on和emit 子組件emit觸發一個事件,父組件emit觸發一個事件,父組件on監聽相應事件。 // Parent.vue <Child @mounted="doSomething"/> // Child.vue mounted() ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...