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

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

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

 


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

-Advertisement-
Play Games
更多相關文章
  • 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() ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...