摘要本文系統(tǒng)講解動(dòng)態(tài)規(guī)劃的核心思想并以經(jīng)典的01背包問題為例進(jìn)行手把手教學(xué)。文章從解法思路入手詳細(xì)拆解DP表格中每個(gè)格子的含義、填表順序以及選與不選兩種策略的推導(dǎo)過程配合完整的Java代碼實(shí)現(xiàn)幫助讀者直觀理解動(dòng)態(tài)規(guī)劃的填表邏輯。此外文章還結(jié)合力扣實(shí)戰(zhàn)刷題與軟考真題提供題目分析、解題思路與官方答案適合備考軟考及算法入門的讀者學(xué)習(xí)參考。核心思想選當(dāng)前物品最大價(jià)值 當(dāng)前選中的物品的價(jià)值 剩余背包容量去上一行發(fā)揮出的最大價(jià)值不選當(dāng)前物品最大價(jià)值 上方相鄰格子的價(jià)值每一個(gè)格子我們都需要考慮上方兩種情況并且取值 max策略1 策略2選價(jià)值最大的策略。目錄一、動(dòng)態(tài)規(guī)劃的基本思想二、動(dòng)態(tài)規(guī)劃的典型例子—01背包問題解法思路每個(gè)格子的值的含義填寫表格的順序兩個(gè)策略手把手全流程教學(xué)代碼實(shí)現(xiàn)力扣實(shí)戰(zhàn)刷題軟考真題2019—下半年—試題四①題目②問題③分析④官方答案2021—下半年—試題四①題目②問題③分析④官方答案一、動(dòng)態(tài)規(guī)劃的基本思想二、動(dòng)態(tài)規(guī)劃的典型例子—01背包問題①“01”的概念一個(gè)物品要么裝進(jìn)背包、要么不裝。解法思路要想解決原問題就先解決子問題這句話是動(dòng)態(tài)規(guī)劃的核心思想。大白話你不是要求物品數(shù)量是4嗎那我就先求出物品數(shù)量是3的最大價(jià)值、物品數(shù)量是2的最大價(jià)值、物品數(shù)量是1的最大價(jià)值、物品數(shù)量是0的最大價(jià)值。你不是要求背包容量是5嗎那我就先求出背包容量是4的最大價(jià)值、背包容量是3的最大價(jià)值、背包容量是2的最大價(jià)值、背包容量是1的最大價(jià)值、背包容量是0的最大價(jià)值。從上面兩個(gè)維度可以求出子問題然后通過子問題最終求解原問題。這就是動(dòng)態(tài)規(guī)劃的魅力。然后上述兩個(gè)維度的縮放可以畫成下面的一張二維數(shù)組表格。每個(gè)格子的值的含義每個(gè)格子的值就是對(duì)應(yīng)的情況的最大價(jià)值。舉例下圖紅框的值即2就是當(dāng)物品數(shù)量為1、背包容量為1時(shí)的最大價(jià)值。其他值也同理。填寫表格的順序從上到下一行一行的來。兩個(gè)策略選當(dāng)前物品最大價(jià)值 當(dāng)前選中的物品的價(jià)值 剩余背包容量去上一行發(fā)揮出的最大價(jià)值不選當(dāng)前物品最大價(jià)值 上方相鄰格子的價(jià)值每一個(gè)格子我們都需要考慮上方兩種情況并且取值 max策略1 策略2選價(jià)值最大的策略。手把手全流程教學(xué)第①步先處理邊界當(dāng)i0即物品數(shù)量為0此時(shí)沒物品可選所以最大價(jià)值為0故第一行全是0當(dāng)j0即背包容量為0此時(shí)啥都裝不下所以最大價(jià)值為0故第一列全是0第②步根據(jù)上面的策略選當(dāng)前物品/不選當(dāng)前物品哪個(gè)策略的價(jià)值大就填充哪個(gè)值代碼實(shí)現(xiàn)public class test01 { public static void main(String[] args) { //先定義題目描述的東西 int N 4;//原問題的物品數(shù)量4個(gè) int W 5;//原問題的背包容量5 int v[] {0, 2, 4, 5, 6};//第0~4個(gè)物品的價(jià)值 int w[] {0, 1, 2, 3, 4};//第0~4個(gè)物品的重量 //定義待填充的二維數(shù)組表格專業(yè)術(shù)語叫dp數(shù)組 int[][] f new int[N1][W1]; //開始循環(huán)填充DP數(shù)組二維表格 for(int i1; iN; i){ for(int j1; jW; j){ //每個(gè)格子都要考慮 選/不選 當(dāng)前物品并且取二者的價(jià)值較大者填入當(dāng)前格子 if(jw[i]){ f[i][j] Math.max(f[i-1][j], v[i]f[i-1][j-w[i]]); }else{ f[i][j] f[i-1][j]; } } } //輸出結(jié)果最大價(jià)值就是f[N][W]的值(即DP數(shù)組右下角的那個(gè)格子的值) System.out.println(最大價(jià)值f[N][W]); } }運(yùn)行結(jié)果可見此時(shí)沒問題。我們還可以將DP數(shù)組打印出來看看和我們之前手動(dòng)填充的表格一致嗎//打印出DP數(shù)組 for (int i 0; i N; i) { // 內(nèi)層循環(huán)控制列 (j)從 0 到 W for (int j 0; j W; j) { // 打印當(dāng)前格子的值使用 \t (制表符) 分隔使對(duì)齊更美觀 System.out.print(f[i][j] \t); } // 【關(guān)鍵】每一行打印完后輸出一個(gè)換行符 System.out.println(); }可見此時(shí)通過程序跑出的結(jié)果和我們之前手動(dòng)推導(dǎo)的一模一樣。力扣實(shí)戰(zhàn)刷題動(dòng)態(tài)規(guī)劃_01背包問題_攜帶研究材料-CSDN博客軟考真題2019—下半年—試題四①題目②問題③分析④官方答案2021—下半年—試題四①題目②問題③分析紅框解讀紅框這兩個(gè)for循環(huán)是在初始化dp數(shù)組具體含義此時(shí)含義是當(dāng)目前兩個(gè)字符相等那么無需任何操作步數(shù)不變即無需進(jìn)行增、刪、改如果這道題你不確定是str1[i-1] str2[j-1] 還是 str1[i] str2[j]的話此時(shí)我們要會(huì)靈活運(yùn)用題目給的線索可見此時(shí)肯定是i-1和j-1是正確的下標(biāo)。這個(gè)空其實(shí)題目也早就給了如下圖意思是當(dāng)目前兩個(gè)字符不相等時(shí)我們要將兩個(gè)字符串變成一致的策略就是采取增、刪、改三個(gè)操作中步數(shù)最小的那一個(gè)。所以用了min函數(shù)。其實(shí)這個(gè)空也非常簡(jiǎn)單我們所求的最終答案就是dp數(shù)組的右下角那個(gè)元素也即d[len1][len2]動(dòng)態(tài)規(guī)劃算法這很明顯了不多解釋。至于這個(gè)算法的時(shí)間復(fù)雜度分析如下由于算法的時(shí)間復(fù)雜度是取決于那個(gè)最長的循環(huán)所以該算法的時(shí)間復(fù)雜度為O(mn)將第一個(gè)字符串刪掉T、增加A、增加C、增加T。經(jīng)過上面的四步就能變成第二個(gè)字符串。所以編輯距離 4④官方答案以上就是本篇文章的全部內(nèi)容喜歡的話可以留個(gè)免費(fèi)的關(guān)注呦~~~