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