Java【動(dòng)態(tài)規(guī)劃】斐波那契數(shù)列模型, 圖文思路詳解 + 代碼實(shí)現(xiàn)

這篇具有很好參考價(jià)值的文章主要介紹了Java【動(dòng)態(tài)規(guī)劃】斐波那契數(shù)列模型, 圖文思路詳解 + 代碼實(shí)現(xiàn)。希望對大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

本篇總結(jié)動(dòng)態(tài)規(guī)劃中的斐波那契數(shù)列模型的解法和思路

按照以下流程進(jìn)行分析題目和代碼編寫

思路分析步驟	代碼編寫步驟
1, 狀態(tài)表示	1, 構(gòu)造 dp 表
2, 狀態(tài)轉(zhuǎn)移方程	2, 初始化+邊界處理
3, 初始化	3, 填表(抄狀態(tài)轉(zhuǎn)移方程)
4, 填表順序	4, 返回結(jié)果
5, 返回值	/

一、第 N 個(gè)泰波那契數(shù)

1, 題目

OJ鏈接

題目分析: 第 N 個(gè)數(shù) = 第 N-1 個(gè)數(shù) + 第 N-2 個(gè)數(shù) + 第 N-3 個(gè)數(shù)

2, 思路分析

2.1, 狀態(tài)表示

根據(jù)題目要求, 要我們算出第 N 個(gè)數(shù)是多少, 我們要構(gòu)造一個(gè)dp表(數(shù)組), 表中的值就是第 N 個(gè)數(shù)的值

所以對于整個(gè)數(shù)列來說, 對于 i(任意數(shù)) 位置, 都可以表示成 dp[i]

狀態(tài)表示 : dp[i] 就是第 i 個(gè)泰波那契數(shù)

2.2, 狀態(tài)轉(zhuǎn)移方程

根據(jù) : 第 N 個(gè)數(shù) = 第 N-1 個(gè)數(shù) + 第 N-2 個(gè)數(shù) + 第 N-3 個(gè)數(shù) 可直接得出

狀態(tài)轉(zhuǎn)移方程 : dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

java 斐波那契,算法,java,動(dòng)態(tài)規(guī)劃,斐波那契數(shù)列模型

2.3, 初始化

初始化是為了填表的時(shí)候不越界訪問

根據(jù)狀態(tài)轉(zhuǎn)移方程可以分析出, dp[i] 依賴前三個(gè)數(shù)的值, 所以在表中前三個(gè)數(shù)的值必須手動(dòng)填, 從第四個(gè)數(shù)開始可以根據(jù)狀態(tài)轉(zhuǎn)移方程來填

題中已經(jīng)告訴我們 dp[0] = 0, dp[1] = dp[2] = 1

2.4, 填表順序

由于dp[i] 依賴前三個(gè)數(shù)的值, 所以在確定任意位置的值時(shí), 首先要知道前三個(gè)數(shù)的值, 所以填表順序是從左往右

2.5, 返回值

要我們求第 N 個(gè)數(shù)的值, 就是 dp[N]

要訪問 dp[N] , dp 表的長度是多少?

3, 代碼

在構(gòu)造 dp 表時(shí), int[] dp = new int[n];是錯(cuò)的, 長度為 n 的數(shù)組, 下標(biāo)是 0 ~ n-1, 要想訪問到 dp[n], dp 表的長度應(yīng)該是 n + 1

public int tribonacci(int n) {
        // 1, 構(gòu)造dp表
        int[] dp = new int[n + 1];
        // 2, 初始化 + 邊界條件判斷
        if(n == 0 || n == 1) {
            return n;
        }
        if(n == 2) {
            return 1;
        }
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        // 3, 填表(抄狀態(tài)轉(zhuǎn)移方程)
        for(int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];            
        }
        // 4, 返回值
        return dp[n];
    }

二、三步問題

1, 題目

OJ鏈接

分析題目得知, 在第 N 個(gè)臺(tái)階時(shí), 可以從第 N - 1 個(gè)臺(tái)階跳一個(gè)臺(tái)階上來, 可以從第 N - 2 個(gè)臺(tái)階跳兩個(gè)臺(tái)階上來, 可以從第 N - 3 個(gè)臺(tái)階跳三個(gè)臺(tái)階上來

2, 思路分析

2.1, 狀態(tài)表示

根據(jù)題目要求可知, 在 dp 表中的值就是到達(dá)某個(gè)臺(tái)階時(shí)的跳法總數(shù)

狀態(tài)表示 : dp[i] 就是到達(dá)第 i 個(gè)臺(tái)階時(shí), 跳法的總數(shù)

2.2, 狀態(tài)轉(zhuǎn)移方程

以 i 位置狀態(tài)的最近的?步，來分情況討論, 要求 dp[i], 已經(jīng)分析過有三種情況

在第 i - 1 個(gè)臺(tái)階時(shí), 有 ? 種跳法, 加一步即可
從第 i - 2 個(gè)臺(tái)階時(shí), 有 ? 種跳法, 加一步即可
從第 i - 3 個(gè)臺(tái)階時(shí), 有 ? 種跳法, 加一步即可

所以在第 i 個(gè)臺(tái)階時(shí)的跳法總數(shù)就是 : 上述三個(gè)狀態(tài)的跳法總數(shù)的和

狀態(tài)轉(zhuǎn)移方程 : dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

問 : 為什么不是 dp[i] = dp[i - 1] + 1 + dp[i - 2] + 1 + dp[i - 3] + 1 呢? 不是多跳了一步嗎?
答 : 是多跳了一步, 但只是在原有的跳法上多跳了一下, 并沒有產(chǎn)生新的跳法!!! 這一點(diǎn)一定要理解, 我們求的是有多少種跳法, 而不是跳了多少步!!

實(shí)在不理解可以帶入第二個(gè)臺(tái)階, 進(jìn)行分析

2.3, 初始化

初始化是為了填表的時(shí)候不越界訪問

可以簡單推導(dǎo)出 dp[1] = 1, dp[2] = 2, dp[3] = 4;

我們讓 0 號(hào)臺(tái)階表示地平線, 不需要給 dp[0] 賦值, 沒有意義

2.4, 填表順序

由于dp[i] 依賴前三個(gè)數(shù)的值, 所以在確定任意位置的值時(shí), 首先要知道前三個(gè)數(shù)的值, 所以填表順序是從左往右

2.5, 返回值

要我們求第 N 個(gè)數(shù)的值, 就是 dp[N]

要訪問 dp[N] , 初始化時(shí) dp 表的長度是多少?

3, 代碼

在構(gòu)造 dp 表時(shí), int[] dp = new int[n];是錯(cuò)的, 長度為 n 的數(shù)組, 下標(biāo)是 0 ~ n-1, 要想訪問到 dp[n], dp 表的長度應(yīng)該是 n + 1

	public int waysToStep(int n) {
        // 1, 構(gòu)造dp表
        int[] dp = new int[n + 1];
        // 2, 初始化+邊界條件處理
        if(n <= 2) {
            return n;
        }
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        // 3, 填表(抄狀態(tài)轉(zhuǎn)移方程)
        for(int i = 4; i <= n ; i++) {
            dp[i] = ((dp[i - 1]  + dp[i - 2]) % 1000000007 +  dp[i-3]) % 1000000007;
        }
        // 4, 返回值
        return dp[n];
    }

三、

1, 題目

OJ鏈接

分析題目得知, 要達(dá)第 N 個(gè)臺(tái)階, 可以從第 N-1個(gè)臺(tái)階過來, 也可以從第 N-2 個(gè)臺(tái)階過來, 如果 cost 數(shù)組的長度為 n , 臺(tái)階數(shù)為 n - 1, 因?yàn)?cost[0] 表示從地平線起跳要支付的費(fèi)用, 樓頂在 n 的位置

2, 思路分析

2.1, 狀態(tài)表示

我們需要構(gòu)造 dp 表, 要求到達(dá)樓頂?shù)淖钚』ㄙM(fèi), 需要先知道中途到達(dá)任意位置的最小花費(fèi)(劃分子問題), 所以 狀態(tài)表示 : dp[i] 就是以 i 為終點(diǎn), 到達(dá) i 位置的最小花費(fèi)

2.2, 狀態(tài)轉(zhuǎn)移方程

以 i 位置狀態(tài)的最近的?步，來分情況討論, 要求 dp[i](到達(dá) i 位置的最小花費(fèi)), 有兩種情況

從第 i - 1 位置上來 : 在此位置的最小花費(fèi) + 從此位置起跳要支付的費(fèi)用
從第 i - 2 位置上來 : 在此位置的最小花費(fèi) + 從此位置起跳要支付的費(fèi)用

要保證到達(dá) i 位置時(shí)花費(fèi)的錢最少, 就要對這兩種方式的費(fèi)用取較小值

注意題中給的 cost 數(shù)組和 dp 數(shù)組的關(guān)系 :
java 斐波那契,算法,java,動(dòng)態(tài)規(guī)劃,斐波那契數(shù)列模型

狀態(tài)轉(zhuǎn)移方程 : dp[i] = min (dp[i - 1] + cost[i- 1], dp[i - 2] + cost[i- 2])

2.3, 初始化

初始化是為了填表的時(shí)候不越界訪問

根據(jù)狀態(tài)轉(zhuǎn)移方程可知, 填 dp 表中的值, 依賴前兩個(gè)位置的值, 所以在 dp 表中, 0 下標(biāo)和 1 下標(biāo)必須初始化

題目已經(jīng)說明, 可以自由選擇從 0 號(hào)臺(tái)階或 1 號(hào)臺(tái)階起跳, 所以到達(dá) 0 號(hào)臺(tái)階或 1 號(hào)臺(tái)階的最小花費(fèi)為 0 元, 所以 : dp[0] = 0, dp[1] = 0;

2.4, 填表順序

dp[i] 的值依賴前兩個(gè)位置的值, 所以填表順序是從左往右

2.5, 返回值

cost 長度為 N, 則有 N - 1 個(gè)臺(tái)階, 樓頂在 N 位置, 所以返回 dp[N]

要訪問 dp[N] , 初始化時(shí) dp 表的長度是多少?

3, 代碼

在構(gòu)造 dp 表時(shí), int[] dp = new int[n];是錯(cuò)的, 長度為 n 的數(shù)組, 下標(biāo)是 0 ~ n-1, 要想訪問到 dp[n], dp 表的長度應(yīng)該是 n + 1

	public int minCostClimbingStairs(int[] cost) {
        // 構(gòu)造dp表
        int n = cost.length;
        int[] dp = new int[n + 1];
        // 初始化+邊界條件
        dp[0] = 0;
        dp[1] = 0;
        // 填表(抄狀態(tài)轉(zhuǎn)移方)
        for(int i = 2; i <= n ;i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i  -1], dp[i - 2] + cost[i - 2]) ;
        }
        // 返回值
        return dp[n];
    }

四、

1, 題目

OJ鏈接

2, 思路分析

2.1, 狀態(tài)表示

java 斐波那契,算法,java,動(dòng)態(tài)規(guī)劃,斐波那契數(shù)列模型

狀態(tài)表示 : dp[i] 就是以 i 位置為結(jié)尾, 編碼方法的總數(shù)

2.2, 狀態(tài)轉(zhuǎn)移方程

以 i 位置狀態(tài)的最近的?步，來分情況討論, 要求 dp[i], 有兩種方式 :

i 位置的數(shù)字單獨(dú)解碼, 如果解碼成功, dp[i] 加上 x , (從0 到 i - 1位置的所有解碼方法總數(shù))
i 位置的數(shù)字和 i - 1 位置的數(shù)字一起解碼, 如果解碼成功, dp[i] 加上 y , (從0 到 i - 2位置的所有解碼方法總數(shù))

結(jié)合狀態(tài)表示可知 : x = 從0 到 i - 1位置的所有解碼方法總數(shù) = dp[i- 1], y = 從0 到 i - 1位置的所有解碼方法總數(shù) = dp[i- 2]

所以狀態(tài)轉(zhuǎn)移方程 : 如果方案一成功, dp[i] += dp[i-1], 如果方案二成功, dp[i] += dp[i-2],

這里千萬要搞清楚, 無論哪種方式解碼, 都在只是增加了解碼的字符串長度, 而不是新增了一種解碼方式

無論哪種方式解碼, 一旦解碼失敗, dp[i] += 0 即可, 如果當(dāng)前位置的解碼方式為 0, 計(jì)算到下一個(gè)位置時(shí), 會(huì)依賴當(dāng)前位置的 dp 值, 所以后面 dp 表中的值都為 0, 最終返回結(jié)果為 0

2.3, 初始化

初始化是為了填表的時(shí)候不越界訪問

根據(jù)狀態(tài)轉(zhuǎn)移方程可知, 填表到某一位置時(shí), 依賴前兩個(gè)位置的值, 所以初始化dp表中 0 下標(biāo)和 1 下標(biāo)即可

2.4, 填表順序

填表順序是從左往右

2.5, 返回值

要求的是整個(gè)字符串的解碼方案總數(shù), 令字符串長度為 n, 返回dp[n - 1]文章來源地址http://www.zghlxwxcb.cn/news/detail-714287.html

3, 代碼

    public int numDecodings(String s) {
        // 構(gòu)造 dp 表
        int n = s.length();
        int[] dp = new int[n];
        char[] array = s.toCharArray();
        // 初始化+邊界條件
        if(array[0] != '0') {
            dp[0] = 1;
        }
        if(n == 1) {
            return dp[0];
        }
        if( array[1] != '0') {
            dp[1] += dp[0];
        }
        int num = (array[0] -'0') * 10 + (array[1]-'0');
        if( num >= 10 && num <= 26 ) {
            dp[1] += dp[0];
        }
        // 填表(抄狀態(tài)轉(zhuǎn)移方程)
        for(int i = 2; i < n; i++) {
            if(array[i] != '0') {
                dp[i] += dp[i - 1];
            }
            num = (array[i-1] -'0') * 10 + (array[i]-'0');
            if( num >= 10 && num <= 26 ) {
                dp[i] += dp[i - 2];
            }
        }
        // 返回值
        return dp[n - 1];
    }

到了這里，關(guān)于Java【動(dòng)態(tài)規(guī)劃】斐波那契數(shù)列模型, 圖文思路詳解 + 代碼實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！