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