態(tài)規(guī)劃:跳臺(tái)階問題的遞推建模與 O(1) 空間解法)
CS-Notes 劍指 Offer 動(dòng)態(tài)規(guī)劃:跳臺(tái)階問題的遞推建模與 O(1) 空間解法【免費(fèi)下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識(shí)、Leetcode、計(jì)算機(jī)操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、系統(tǒng)設(shè)計(jì)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 倉(cāng)庫(kù)中「劍指 Offer」動(dòng)態(tài)規(guī)劃專題的跳臺(tái)階題解,圍繞青蛙每次跳 1 級(jí)或 2 級(jí)臺(tái)階,求跳上 n 級(jí)臺(tái)階的跳法總數(shù)這一問題展開:從遞推公式的推導(dǎo)、樸素遞歸的缺陷,到滾動(dòng)變量實(shí)現(xiàn)的空間優(yōu)化,完整給出可復(fù)現(xiàn)的 Java 解法,并串聯(lián)斐波那契數(shù)列、矩形覆蓋、變態(tài)跳臺(tái)階三道同型題目,幫助讀者掌握遞推建模范式與O(1) 空間動(dòng)態(tài)規(guī)劃兩類面試核心能力。一、問題定義一只青蛙一次可以跳上 1 級(jí)臺(tái)階,也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。這道題出自「劍指 Offer」經(jīng)典題庫(kù),在 CS-Notes 的劍指 Offer 題解目錄中被歸入「動(dòng)態(tài)規(guī)劃」專題,與 10.1 斐波那契數(shù)列、10.2 矩形覆蓋、10.4 變態(tài)跳臺(tái)階 組成一組同型題。二、遞推建模:從小規(guī)模實(shí)例中找規(guī)律先觀察兩個(gè)最小規(guī)模的邊界情況,它們是后續(xù)遞推公式的基石:n 1 時(shí),只有 1 種跳法:即跳 1 級(jí)。n 2 時(shí),有 2 種跳法:先跳 1 級(jí)再跳 1 級(jí),或者一次跳 2 級(jí)。關(guān)鍵在于最后一跳的狀態(tài)劃分:要跳上第 n 級(jí)臺(tái)階,青蛙倒數(shù)第一步只有兩種可能——從第 n-1 級(jí)跳 1 級(jí)上來(lái),那么前 n-1 級(jí)的跳法總數(shù)就是f(n-1);從第 n-2 級(jí)跳 2 級(jí)上來(lái),那么前 n-2 級(jí)的跳法總數(shù)就是f(n-2)。兩種情況互斥且窮盡,因此得到遞推公式(原文檔以圖片形式給出):用數(shù)學(xué)語(yǔ)言表述即:f(1) 1 f(2) 2 f(n) f(n-1) f(n-2), n 2從源碼結(jié)構(gòu)看,這個(gè)遞推關(guān)系與 CS-Notes 中 10.1 斐波那契數(shù)列 的f(n) f(n-1) f(n-2)完全同型,只是初始條件不同——跳臺(tái)階本質(zhì)上是偏移了一位、且從 1, 2 起步的斐波那契數(shù)列;10.2 矩形覆蓋(用 n 個(gè) 2×1 小矩形覆蓋 2×n 大矩形)的遞推公式也與之一字不差。三者共享同一套求解框架:確定初始條件 → 寫出狀態(tài)轉(zhuǎn)移方程 → 自底向上迭代。三、解法演進(jìn):從樸素遞歸到滾動(dòng)變量3.1 樸素遞歸:指數(shù)級(jí)開銷按遞推式直接寫遞歸,是最直覺的寫法:public int JumpFloor(int n) { if (n 2) return n; return JumpFloor(n - 1) JumpFloor(n - 2); }但正如 10.1 斐波那契數(shù)列 中所分析的那樣,遞歸會(huì)把子問題反復(fù)計(jì)算:計(jì)算f(5)需要計(jì)算f(4)和f(3),而f(4)內(nèi)部又要計(jì)算f(3)和f(2),f(3)被重復(fù)求解。調(diào)用樹近似呈二叉展開,時(shí)間復(fù)雜度為指數(shù)級(jí) O(2^n),n 稍大(如超過(guò) 40)就會(huì)超時(shí),面試中不可接受。3.2 自底向上動(dòng)態(tài)規(guī)劃:O(n) 時(shí)間用緩存子問題解的思路,自底向上填表:public int JumpFloor(int n) { if (n 2) return n; int[] dp new int[n 1]; dp[1] 1; dp[2] 2; for (int i 3; i n; i) dp[i] dp[i - 1] dp[i - 2]; return dp[n]; }時(shí)間復(fù)雜度降為 O(n)。但進(jìn)一步觀察可以發(fā)現(xiàn):dp[i]只依賴dp[i-1]與dp[i-2]兩個(gè)狀態(tài),歷史狀態(tài)一旦用完就不再需要。這正是原倉(cāng)庫(kù) 10.3 跳臺(tái)階 給出的優(yōu)化方向。3.3 滾動(dòng)變量:O(1) 空間(原文檔標(biāo)準(zhǔn)解法)原文檔給出的最終實(shí)現(xiàn)如下,僅用兩個(gè)變量pre2、pre1滾動(dòng)保存前兩項(xiàng):public int JumpFloor(int n) { if (n 2) return n; int pre2 1, pre1 2; int result 0; for (int i 2; i n; i) { result pre2 pre1; pre2 pre1; pre1 result; } return result; }逐行拆解這段代碼的參數(shù)含義與執(zhí)行過(guò)程:變量初始值含義pre21對(duì)應(yīng)f(1) 1pre12對(duì)應(yīng)f(2) 2result0存放當(dāng)前正在計(jì)算的f(i1)循環(huán)i 2; i n; i—從第 3 項(xiàng)開始,共滾動(dòng) n-2 次,結(jié)束時(shí)result恰為f(n)以 n 5 為例跟蹤循環(huán):輪次 iresult(即 f(i1))pre2pre123 f(3)2335 f(4)3548 f(5)58最終返回result 8,即跳 5 級(jí)臺(tái)階共 8 種跳法,時(shí)間復(fù)雜度 O(n)、空間復(fù)雜度 O(1)。這與 10.1 斐波那契數(shù)列 中考慮到第 i 項(xiàng)只與第 i-1 和第 i-2 項(xiàng)有關(guān),只需存儲(chǔ)前兩項(xiàng),將空間復(fù)雜度由 O(N) 降為 O(1)的優(yōu)化思想如出一轍。3.4 邊界與數(shù)值限制說(shuō)明結(jié)合原實(shí)現(xiàn)if (n 2) return n;的寫法,從源碼結(jié)構(gòu)看,該方法對(duì) n ≤ 0 的輸入會(huì)直接返回 n 本身(即 0 或負(fù)數(shù)),題目隱含 n 為正整數(shù)這一前提,實(shí)際調(diào)用前應(yīng)對(duì)輸入合法性做校驗(yàn)。另外,由于返回值是int,而跳臺(tái)階的解就是斐波那契數(shù)列,Fib(47) 已超過(guò) 32 位整數(shù)上限,因此 n 較大(約 46 以上)時(shí)該解法會(huì)發(fā)生整數(shù)溢出;若題目允許 n 更大,可改用long或取模運(yùn)算,這一點(diǎn)與 10.1 斐波那契數(shù)列 中n ≤ 39的取值約束是同一類考慮。四、同型題對(duì)照:一道題串起整個(gè) DP 專題在 CS-Notes 的動(dòng)態(tài)規(guī)劃分組中,跳臺(tái)階是承上啟下的一題,建議配合以下文檔橫向?qū)Ρ葘W(xué)習(xí):題目狀態(tài)轉(zhuǎn)移方程結(jié)果特征文檔10.1 斐波那契數(shù)列f(n) f(n-1) f(n-2)斐波那契數(shù)列本體,可用 O(1) 預(yù)計(jì)算notes/10.1 斐波那契數(shù)列.md10.2 矩形覆蓋f(n) f(n-1) f(n-2)與跳臺(tái)階同方程同解法notes/10.2 矩形覆蓋.md10.3 跳臺(tái)階f(n) f(n-1) f(n-2)本文主題,O(n) 時(shí)間 O(1) 空間notes/10.3 跳臺(tái)階.md10.4 變態(tài)跳臺(tái)階f(n) f(n-1) ... f(0)化為等比數(shù)列f(n) 2^(n-1)notes/10.4 變態(tài)跳臺(tái)階.md其中 10.4 變態(tài)跳臺(tái)階 是最有價(jià)值的變式:若青蛙可以跳 1 級(jí)到 n 級(jí),則狀態(tài)轉(zhuǎn)移變成求和式f(n) f(n-1) f(n-2) ... f(0)。由相鄰兩式相減可得f(n) 2 * f(n-1),即 f(n) 是等比數(shù)列,最終解為:public int JumpFloorII(int target) { return (int) Math.pow(2, target - 1); }對(duì)比之下可以清晰看出:「跳臺(tái)階」的 O(n) 迭代與「變態(tài)跳臺(tái)階」的 O(1) 公式解,差異完全來(lái)自狀態(tài)轉(zhuǎn)移方程的形態(tài)。面試中被追問如果青蛙可以跳任意級(jí)怎么解,正是靠這種對(duì)比能力得分。五、小結(jié)與面試表達(dá)要點(diǎn)回顧 10.3 跳臺(tái)階 的完整解題脈絡(luò),面試作答可按以下邏輯鏈組織:建模:按最后一跳劃分狀態(tài),得到f(n) f(n-1) f(n-2),初始條件f(1) 1、f(2) 2;排除:樸素遞歸存在大量重疊子問題,時(shí)間復(fù)雜度指數(shù)級(jí),不可取;實(shí)現(xiàn):自底向上迭代,且利用狀態(tài)只依賴前兩項(xiàng)這一性質(zhì),用pre2/pre1滾動(dòng)變量把空間壓到 O(1);延伸:主動(dòng)提及矩形覆蓋(同方程)、斐波那契(同型遞推)、變態(tài)跳臺(tái)階(等比數(shù)列化簡(jiǎn)2^(n-1))三道關(guān)聯(lián)題,展示對(duì)整個(gè) DP 專題的把握。這套劃分最后一步 → 寫出轉(zhuǎn)移方程 → 迭代滾動(dòng)優(yōu)化的三步法,可直接遷移到絕大多數(shù)一維遞推類面試題,是 CS-Notes 動(dòng)態(tài)規(guī)劃專題最具復(fù)用價(jià)值的方法論?！久赓M(fèi)下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識(shí)、Leetcode、計(jì)算機(jī)操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、系統(tǒng)設(shè)計(jì)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考 CS-Notes 劍指 Offer 動(dòng)態(tài)規(guī)劃:跳臺(tái)階問題的遞推建模與 O(1) 空間解法
CS-Notes 劍指 Offer 動(dòng)態(tài)規(guī)劃:跳臺(tái)階問題的遞推建模與 O(1) 空間解法【免費(fèi)下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識(shí)、Leetcode、計(jì)算機(jī)操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、系統(tǒng)設(shè)計(jì)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes本文基于 CS-Notes 倉(cāng)庫(kù)中「劍指 Offer」動(dòng)態(tài)規(guī)劃專題的跳臺(tái)階題解,圍繞青蛙每次跳 1 級(jí)或 2 級(jí)臺(tái)階,求跳上 n 級(jí)臺(tái)階的跳法總數(shù)這一問題展開:從遞推公式的推導(dǎo)、樸素遞歸的缺陷,到滾動(dòng)變量實(shí)現(xiàn)的空間優(yōu)化,完整給出可復(fù)現(xiàn)的 Java 解法,并串聯(lián)斐波那契數(shù)列、矩形覆蓋、變態(tài)跳臺(tái)階三道同型題目,幫助讀者掌握遞推建模范式與O(1) 空間動(dòng)態(tài)規(guī)劃兩類面試核心能力。一、問題定義一只青蛙一次可以跳上 1 級(jí)臺(tái)階,也可以跳上 2 級(jí)。求該青蛙跳上一個(gè) n 級(jí)的臺(tái)階總共有多少種跳法。這道題出自「劍指 Offer」經(jīng)典題庫(kù),在 CS-Notes 的劍指 Offer 題解目錄中被歸入「動(dòng)態(tài)規(guī)劃」專題,與 10.1 斐波那契數(shù)列、10.2 矩形覆蓋、10.4 變態(tài)跳臺(tái)階 組成一組同型題。二、遞推建模:從小規(guī)模實(shí)例中找規(guī)律先觀察兩個(gè)最小規(guī)模的邊界情況,它們是后續(xù)遞推公式的基石:n 1 時(shí),只有 1 種跳法:即跳 1 級(jí)。n 2 時(shí),有 2 種跳法:先跳 1 級(jí)再跳 1 級(jí),或者一次跳 2 級(jí)。關(guān)鍵在于最后一跳的狀態(tài)劃分:要跳上第 n 級(jí)臺(tái)階,青蛙倒數(shù)第一步只有兩種可能——從第 n-1 級(jí)跳 1 級(jí)上來(lái),那么前 n-1 級(jí)的跳法總數(shù)就是f(n-1);從第 n-2 級(jí)跳 2 級(jí)上來(lái),那么前 n-2 級(jí)的跳法總數(shù)就是f(n-2)。兩種情況互斥且窮盡,因此得到遞推公式(原文檔以圖片形式給出):用數(shù)學(xué)語(yǔ)言表述即:f(1) 1 f(2) 2 f(n) f(n-1) f(n-2), n 2從源碼結(jié)構(gòu)看,這個(gè)遞推關(guān)系與 CS-Notes 中 10.1 斐波那契數(shù)列 的f(n) f(n-1) f(n-2)完全同型,只是初始條件不同——跳臺(tái)階本質(zhì)上是偏移了一位、且從 1, 2 起步的斐波那契數(shù)列;10.2 矩形覆蓋(用 n 個(gè) 2×1 小矩形覆蓋 2×n 大矩形)的遞推公式也與之一字不差。三者共享同一套求解框架:確定初始條件 → 寫出狀態(tài)轉(zhuǎn)移方程 → 自底向上迭代。三、解法演進(jìn):從樸素遞歸到滾動(dòng)變量3.1 樸素遞歸:指數(shù)級(jí)開銷按遞推式直接寫遞歸,是最直覺的寫法:public int JumpFloor(int n) { if (n 2) return n; return JumpFloor(n - 1) JumpFloor(n - 2); }但正如 10.1 斐波那契數(shù)列 中所分析的那樣,遞歸會(huì)把子問題反復(fù)計(jì)算:計(jì)算f(5)需要計(jì)算f(4)和f(3),而f(4)內(nèi)部又要計(jì)算f(3)和f(2),f(3)被重復(fù)求解。調(diào)用樹近似呈二叉展開,時(shí)間復(fù)雜度為指數(shù)級(jí) O(2^n),n 稍大(如超過(guò) 40)就會(huì)超時(shí),面試中不可接受。3.2 自底向上動(dòng)態(tài)規(guī)劃:O(n) 時(shí)間用緩存子問題解的思路,自底向上填表:public int JumpFloor(int n) { if (n 2) return n; int[] dp new int[n 1]; dp[1] 1; dp[2] 2; for (int i 3; i n; i) dp[i] dp[i - 1] dp[i - 2]; return dp[n]; }時(shí)間復(fù)雜度降為 O(n)。但進(jìn)一步觀察可以發(fā)現(xiàn):dp[i]只依賴dp[i-1]與dp[i-2]兩個(gè)狀態(tài),歷史狀態(tài)一旦用完就不再需要。這正是原倉(cāng)庫(kù) 10.3 跳臺(tái)階 給出的優(yōu)化方向。3.3 滾動(dòng)變量:O(1) 空間(原文檔標(biāo)準(zhǔn)解法)原文檔給出的最終實(shí)現(xiàn)如下,僅用兩個(gè)變量pre2、pre1滾動(dòng)保存前兩項(xiàng):public int JumpFloor(int n) { if (n 2) return n; int pre2 1, pre1 2; int result 0; for (int i 2; i n; i) { result pre2 pre1; pre2 pre1; pre1 result; } return result; }逐行拆解這段代碼的參數(shù)含義與執(zhí)行過(guò)程:變量初始值含義pre21對(duì)應(yīng)f(1) 1pre12對(duì)應(yīng)f(2) 2result0存放當(dāng)前正在計(jì)算的f(i1)循環(huán)i 2; i n; i—從第 3 項(xiàng)開始,共滾動(dòng) n-2 次,結(jié)束時(shí)result恰為f(n)以 n 5 為例跟蹤循環(huán):輪次 iresult(即 f(i1))pre2pre123 f(3)2335 f(4)3548 f(5)58最終返回result 8,即跳 5 級(jí)臺(tái)階共 8 種跳法,時(shí)間復(fù)雜度 O(n)、空間復(fù)雜度 O(1)。這與 10.1 斐波那契數(shù)列 中考慮到第 i 項(xiàng)只與第 i-1 和第 i-2 項(xiàng)有關(guān),只需存儲(chǔ)前兩項(xiàng),將空間復(fù)雜度由 O(N) 降為 O(1)的優(yōu)化思想如出一轍。3.4 邊界與數(shù)值限制說(shuō)明結(jié)合原實(shí)現(xiàn)if (n 2) return n;的寫法,從源碼結(jié)構(gòu)看,該方法對(duì) n ≤ 0 的輸入會(huì)直接返回 n 本身(即 0 或負(fù)數(shù)),題目隱含 n 為正整數(shù)這一前提,實(shí)際調(diào)用前應(yīng)對(duì)輸入合法性做校驗(yàn)。另外,由于返回值是int,而跳臺(tái)階的解就是斐波那契數(shù)列,Fib(47) 已超過(guò) 32 位整數(shù)上限,因此 n 較大(約 46 以上)時(shí)該解法會(huì)發(fā)生整數(shù)溢出;若題目允許 n 更大,可改用long或取模運(yùn)算,這一點(diǎn)與 10.1 斐波那契數(shù)列 中n ≤ 39的取值約束是同一類考慮。四、同型題對(duì)照:一道題串起整個(gè) DP 專題在 CS-Notes 的動(dòng)態(tài)規(guī)劃分組中,跳臺(tái)階是承上啟下的一題,建議配合以下文檔橫向?qū)Ρ葘W(xué)習(xí):題目狀態(tài)轉(zhuǎn)移方程結(jié)果特征文檔10.1 斐波那契數(shù)列f(n) f(n-1) f(n-2)斐波那契數(shù)列本體,可用 O(1) 預(yù)計(jì)算notes/10.1 斐波那契數(shù)列.md10.2 矩形覆蓋f(n) f(n-1) f(n-2)與跳臺(tái)階同方程同解法notes/10.2 矩形覆蓋.md10.3 跳臺(tái)階f(n) f(n-1) f(n-2)本文主題,O(n) 時(shí)間 O(1) 空間notes/10.3 跳臺(tái)階.md10.4 變態(tài)跳臺(tái)階f(n) f(n-1) ... f(0)化為等比數(shù)列f(n) 2^(n-1)notes/10.4 變態(tài)跳臺(tái)階.md其中 10.4 變態(tài)跳臺(tái)階 是最有價(jià)值的變式:若青蛙可以跳 1 級(jí)到 n 級(jí),則狀態(tài)轉(zhuǎn)移變成求和式f(n) f(n-1) f(n-2) ... f(0)。由相鄰兩式相減可得f(n) 2 * f(n-1),即 f(n) 是等比數(shù)列,最終解為:public int JumpFloorII(int target) { return (int) Math.pow(2, target - 1); }對(duì)比之下可以清晰看出:「跳臺(tái)階」的 O(n) 迭代與「變態(tài)跳臺(tái)階」的 O(1) 公式解,差異完全來(lái)自狀態(tài)轉(zhuǎn)移方程的形態(tài)。面試中被追問如果青蛙可以跳任意級(jí)怎么解,正是靠這種對(duì)比能力得分。五、小結(jié)與面試表達(dá)要點(diǎn)回顧 10.3 跳臺(tái)階 的完整解題脈絡(luò),面試作答可按以下邏輯鏈組織:建模:按最后一跳劃分狀態(tài),得到f(n) f(n-1) f(n-2),初始條件f(1) 1、f(2) 2;排除:樸素遞歸存在大量重疊子問題,時(shí)間復(fù)雜度指數(shù)級(jí),不可取;實(shí)現(xiàn):自底向上迭代,且利用狀態(tài)只依賴前兩項(xiàng)這一性質(zhì),用pre2/pre1滾動(dòng)變量把空間壓到 O(1);延伸:主動(dòng)提及矩形覆蓋(同方程)、斐波那契(同型遞推)、變態(tài)跳臺(tái)階(等比數(shù)列化簡(jiǎn)2^(n-1))三道關(guān)聯(lián)題,展示對(duì)整個(gè) DP 專題的把握。這套劃分最后一步 → 寫出轉(zhuǎn)移方程 → 迭代滾動(dòng)優(yōu)化的三步法,可直接遷移到絕大多數(shù)一維遞推類面試題,是 CS-Notes 動(dòng)態(tài)規(guī)劃專題最具復(fù)用價(jià)值的方法論?！久赓M(fèi)下載鏈接】CS-Notes:books: 技術(shù)面試必備基礎(chǔ)知識(shí)、Leetcode、計(jì)算機(jī)操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)、系統(tǒng)設(shè)計(jì)項(xiàng)目地址: https://gitcode.com/GitHub_Trending/cs/CS-Notes創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考