學(xué)會(huì)動(dòng)態(tài)規(guī)劃調(diào)整學(xué)習(xí)策略

匯報(bào)人:XX2024-01-17學(xué)會(huì)動(dòng)態(tài)規(guī)劃調(diào)整學(xué)習(xí)策略目錄CONTENCT動(dòng)態(tài)規(guī)劃基本概念動(dòng)態(tài)規(guī)劃常用方法典型案例分析與實(shí)現(xiàn)學(xué)習(xí)策略調(diào)整方法論述實(shí)戰(zhàn)演練：編程實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法總結(jié)回顧與展望未來01動(dòng)態(tài)規(guī)劃基本概念定義特點(diǎn)動(dòng)態(tài)規(guī)劃定義與特點(diǎn)動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的，通過把原問題分解為相對(duì)簡(jiǎn)單的子問題的方式來求解復(fù)雜問題的方法。動(dòng)態(tài)規(guī)劃不是一種特定的算法，而是一種解決問題的思想。它將問題分解為若干個(gè)子問題，通過求解子問題的解，最終得到原問題的解。動(dòng)態(tài)規(guī)劃通常用于優(yōu)化重疊子問題的計(jì)算，以避免重復(fù)計(jì)算，從而提高算法效率。適用范圍及問題類型適用范圍動(dòng)態(tài)規(guī)劃適用于具有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題。這類問題通?？梢苑纸鉃槿舾蓚€(gè)子問題，子問題的解可以被重復(fù)利用來求解原問題。問題類型動(dòng)態(tài)規(guī)劃可應(yīng)用于多種類型的問題，如背包問題、最長(zhǎng)公共子序列、最短路徑問題等。這些問題都可以通過動(dòng)態(tài)規(guī)劃的思想進(jìn)行求解，以達(dá)到優(yōu)化計(jì)算的目的。算法思想：動(dòng)態(tài)規(guī)劃的基本思想是將待求解的問題分解成若干個(gè)相互聯(lián)系的子問題，并逐個(gè)求解，最終得到原問題的解。在求解過程中，動(dòng)態(tài)規(guī)劃會(huì)記錄下已經(jīng)求解過的子問題的解，以便在后續(xù)計(jì)算中直接利用，避免重復(fù)計(jì)算。算法思想及核心步驟010203核心步驟：動(dòng)態(tài)規(guī)劃的核心步驟包括以下幾個(gè)方面1.描述問題的最優(yōu)解的結(jié)構(gòu)特征；2.遞歸地定義最優(yōu)解的值；算法思想及核心步驟算法思想及核心步驟3.計(jì)算最優(yōu)解的值，通常采用自底向上的方法；4.利用計(jì)算出的信息構(gòu)造一個(gè)最優(yōu)解。02動(dòng)態(tài)規(guī)劃常用方法01020304狀態(tài)定義狀態(tài)轉(zhuǎn)移方程邊界條件求解過程線性動(dòng)態(tài)規(guī)劃確定問題的邊界條件，即初始狀態(tài)和終止?fàn)顟B(tài)。根據(jù)狀態(tài)之間的關(guān)系，建立狀態(tài)轉(zhuǎn)移方程，用于描述如何從前一個(gè)狀態(tài)轉(zhuǎn)移到后一個(gè)狀態(tài)。將問題劃分為一系列狀態(tài)，每個(gè)狀態(tài)表示一個(gè)子問題的解。從初始狀態(tài)開始，根據(jù)狀態(tài)轉(zhuǎn)移方程逐步求解，直到達(dá)到終止?fàn)顟B(tài)。區(qū)域劃分區(qū)域內(nèi)部決策區(qū)域間決策求解過程區(qū)域動(dòng)態(tài)規(guī)劃將問題劃分為多個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)子問題。在每個(gè)區(qū)域內(nèi)部進(jìn)行決策，確定該區(qū)域的狀態(tài)?？紤]區(qū)域之間的相互影響，進(jìn)行區(qū)域間的決策。通過迭代或遞歸的方式，逐步求解各個(gè)區(qū)域的狀態(tài)，最終得到問題的解。ABCD樹形動(dòng)態(tài)規(guī)劃樹形結(jié)構(gòu)將問題建模為樹形結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)表示一個(gè)子問題的解。狀態(tài)轉(zhuǎn)移方程根據(jù)樹形結(jié)構(gòu)的特點(diǎn)，建立狀態(tài)轉(zhuǎn)移方程，描述父節(jié)點(diǎn)與子節(jié)點(diǎn)之間的狀態(tài)轉(zhuǎn)移關(guān)系。狀態(tài)定義在樹形結(jié)構(gòu)中定義狀態(tài)，表示從根節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑上的決策結(jié)果。求解過程從根節(jié)點(diǎn)開始，根據(jù)狀態(tài)轉(zhuǎn)移方程逐步求解各個(gè)節(jié)點(diǎn)的狀態(tài)，最終得到問題的解。01背包問題給定一組物品和一個(gè)背包，每個(gè)物品有一定的重量和價(jià)值，求解將哪些物品裝入背包可使價(jià)值最大。多重背包問題給定一組物品和一個(gè)背包，每個(gè)物品有一定的重量、價(jià)值和數(shù)量限制，求解將哪些物品裝入背包可使價(jià)值最大。完全背包問題與01背包問題類似，但每個(gè)物品可以多次選取。分組背包問題給定一組物品和一個(gè)背包，物品被劃分為若干組，每組內(nèi)的物品互斥，求解將哪些物品裝入背包可使價(jià)值最大。背包問題及其變形03典型案例分析與實(shí)現(xiàn)給定一個(gè)無序的整數(shù)數(shù)組，找到其中最長(zhǎng)上升子序列的長(zhǎng)度。問題描述定義一個(gè)dp數(shù)組，dp[i]表示以第i個(gè)元素為結(jié)尾的最長(zhǎng)上升子序列的長(zhǎng)度。遍歷數(shù)組，對(duì)于每個(gè)元素，向前搜索比它小的元素，并更新dp值。動(dòng)態(tài)規(guī)劃思路最長(zhǎng)上升子序列問題最長(zhǎng)上升子序列問題01實(shí)現(xiàn)步驟021.初始化dp數(shù)組，長(zhǎng)度為n，所有元素為1。032.遍歷數(shù)組nums，對(duì)于每個(gè)元素nums[i]，再遍歷它之前的所有元素nums[j]，如果nums[i]>nums[j]，則更新dp[i]=max(dp[i],dp[j]+1)。043.遍歷dp數(shù)組，找到最大值即為最長(zhǎng)上升子序列的長(zhǎng)度。問題描述給定一個(gè)整數(shù)數(shù)組nums，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和。動(dòng)態(tài)規(guī)劃思路定義兩個(gè)變量，cur表示當(dāng)前子段和，max表示歷史最大子段和。遍歷數(shù)組，對(duì)于每個(gè)元素，更新cur=max(cur+nums[i],nums[i])，并更新max=max(max,cur)。最大子段和問題011.初始化cur和max為數(shù)組的第一個(gè)元素。2.從數(shù)組的第二個(gè)元素開始遍歷，對(duì)于每個(gè)元素nums[i]，更新cur=max(cur+nums[i],nums[i])和max=max(max,cur)。3.遍歷結(jié)束后，max即為最大子段和。實(shí)現(xiàn)步驟020304最大子段和問題旅行商問題（TSP）給定一個(gè)列表ofcities和一個(gè)距離矩陣distances，其中distances[i][j]是從城市i到城市j的距離。返回從起點(diǎn)城市開始并返回起點(diǎn)城市的最短可能距離。問題描述定義一個(gè)dp數(shù)組，dp[state][i]表示在狀態(tài)state下，從起點(diǎn)城市到城市i的最短距離。狀態(tài)state是一個(gè)二進(jìn)制數(shù)，表示已經(jīng)訪問過的城市集合。遍歷所有狀態(tài)和城市，更新dp值。動(dòng)態(tài)規(guī)劃思路實(shí)現(xiàn)步驟2.對(duì)于起點(diǎn)城市s，設(shè)置dp[1<<s][s]=0。1.初始化dp數(shù)組為一個(gè)較大的值。旅行商問題（TSP）3.遍歷所有狀態(tài)state和城市i，如果state的第i位為0（表示城市i尚未訪問），則遍歷所有已經(jīng)訪問過的城市j，更新dp[state|(1<<i)][i]=min(dp[state|(1<<i)][i],dp[state][j]+distances[j][i])。4.遍歷所有包含起點(diǎn)城市的狀態(tài)state，找到dp[state][s]的最小值，即為從起點(diǎn)城市開始并返回起點(diǎn)城市的最短可能距離。旅行商問題（TSP）問題描述：給定一組物品和一個(gè)背包的容量，每個(gè)物品都有自己的重量和價(jià)值。求解將哪些物品裝入背包可使價(jià)值總和最大。動(dòng)態(tài)規(guī)劃思路：定義一個(gè)dp數(shù)組，dp[i][j]表示前i個(gè)物品中，總體積不超過j的情況下，能達(dá)到的最大價(jià)值。遍歷物品和體積，更新dp值。實(shí)現(xiàn)步驟1.初始化dp數(shù)組為0。2.遍歷每個(gè)物品i，對(duì)于每個(gè)物品，再遍歷背包的容量j。如果j<weights[i]，則dp[i][j]=dp[i-1][j]；否則dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+values[i])。3.遍歷結(jié)束后，dp[n][m]即為前n個(gè)物品中，總體積不超過m的情況下，能達(dá)到的最大價(jià)值。0-1背包問題求解過程演示04學(xué)習(xí)策略調(diào)整方法論述80%80%100%明確學(xué)習(xí)目標(biāo)和計(jì)劃安排根據(jù)學(xué)習(xí)內(nèi)容和自身情況，設(shè)定具體、可衡量的學(xué)習(xí)目標(biāo)。根據(jù)目標(biāo)制定詳細(xì)的學(xué)習(xí)計(jì)劃，包括學(xué)習(xí)時(shí)間、內(nèi)容、方法等。根據(jù)學(xué)習(xí)進(jìn)度和反饋情況，及時(shí)調(diào)整學(xué)習(xí)計(jì)劃，確保學(xué)習(xí)目標(biāo)的順利實(shí)現(xiàn)。設(shè)定明確目標(biāo)制定學(xué)習(xí)計(jì)劃調(diào)整計(jì)劃安排分析問題類型選擇合適方法靈活運(yùn)用方法針對(duì)不同類型問題選擇合適方法根據(jù)問題類型選擇相應(yīng)的學(xué)習(xí)方法，如記憶法、理解法、實(shí)踐法等。在學(xué)習(xí)過程中，根據(jù)實(shí)際情況靈活調(diào)整學(xué)習(xí)方法，提高學(xué)習(xí)效率。識(shí)別問題的類型和特點(diǎn)，如記憶類、理解類、應(yīng)用類等。激發(fā)創(chuàng)新思維鼓勵(lì)自己從不同角度思考問題，提出新的觀點(diǎn)和解決方案。拓寬知識(shí)視野廣泛涉獵相關(guān)領(lǐng)域的知識(shí)和信息，豐富自己的知識(shí)庫和視野。借鑒他人經(jīng)驗(yàn)學(xué)習(xí)他人的成功經(jīng)驗(yàn)和解題思路，為自己的學(xué)習(xí)提供新的啟示和借鑒。多角度思考，拓寬解題思路定期回顧自己的學(xué)習(xí)進(jìn)度和成果，了解自己的學(xué)習(xí)狀況。關(guān)注學(xué)習(xí)進(jìn)度主動(dòng)向他人請(qǐng)教和尋求反饋，了解自己的不足和需要改進(jìn)的地方。尋求他人反饋根據(jù)反饋情況及時(shí)調(diào)整學(xué)習(xí)方法和策略，不斷提高自己的學(xué)習(xí)能力和水平。持續(xù)改進(jìn)提高及時(shí)反饋，持續(xù)改進(jìn)提高05實(shí)戰(zhàn)演練：編程實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃算法安裝Python解釋器Python編程環(huán)境搭建與基礎(chǔ)語法回顧下載并安裝合適版本的Python解釋器，配置環(huán)境變量。選擇合適的IDE根據(jù)個(gè)人喜好選擇一款合適的集成開發(fā)環(huán)境（IDE），如PyCharm、VisualStudioCode等。復(fù)習(xí)Python基礎(chǔ)語法，包括變量、數(shù)據(jù)類型、控制流、函數(shù)等?；A(chǔ)語法回顧問題描述給定一個(gè)數(shù)組nums，求該數(shù)組的最長(zhǎng)遞增子序列的長(zhǎng)度。要點(diǎn)一要點(diǎn)二算法思路定義一個(gè)dp數(shù)組，dp[i]表示以nums[i]結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度。遍歷數(shù)組nums，對(duì)于每個(gè)元素nums[i]，在其之前的所有元素nums[j](j<i)中找到比它小的元素nums[j]，并更新dp[i]=max(dp[i],dp[j]+1)。最終dp數(shù)組中的最大值即為最長(zhǎng)遞增子序列的長(zhǎng)度。線性動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例線性動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例010203```pythondeflengthOfLIS(nums)Python代碼實(shí)現(xiàn)線性動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例01ifnotnums02return0dp=[1]*len(nums)03線性動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例foriinrange(len(nums))010203forjinrange(i)ifnums[i]>nums[j]dp[i]=max(dp[i],dp[j]+1)線性動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例returnmax(dp)```線性動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例問題描述給定一個(gè)mxn的二維網(wǎng)格grid和一個(gè)整數(shù)k，求網(wǎng)格中最大的k個(gè)矩形區(qū)域的面積之和。算法思路首先使用前綴和技巧預(yù)處理出每個(gè)位置(i,j)的上方、左方和左上方的矩形區(qū)域的面積。然后遍歷所有可能的矩形區(qū)域，計(jì)算面積并維護(hù)一個(gè)大小為k的最大堆，堆中保存面積最大的k個(gè)矩形區(qū)域。最終堆中元素之和即為所求。區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例Python代碼實(shí)現(xiàn)```pythonimportheapqdefmaxAreaSum(grid,k)m,n=len(grid),len(grid[0])區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例VS計(jì)算前綴和prefix_sum=[[0]*(n+1)for_inrange(m+1)]區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例01foriinrange(1,m+1)02forjinrange(1,n+1)03prefix_sum[i][j]=prefix_sum[i-1][j]+prefix_sum[i][j-1]-prefix_sum[i-1][j-1]+grid[i-1][j-1]區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例定義計(jì)算矩形面積的函數(shù)02defarea(x1,y1,x2,y2)03returnprefix_sum[x2][y2]-prefix_sum[x1-1][y2]-prefix_sum[x2][y1-1]+prefix_sum[x1-1][y1-1]01區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例使用最大堆保存面積最大的k個(gè)矩形區(qū)域heap=[]foriinrange(m)forjinrange(n)區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例forxinrange(i+1,m+1)foryinrange(j+1,n+1)區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例iflen(heap)<kheapq.heappush(heap,(area(i+1,j+1,x,y),i+1,j+1,x,y))區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例ifarea(i+1,j+1,x,y)>heap[0][0]heapq.heapreplace(heap,(area(i+1,j+1,x,y),i+1,j+1,x,y))else區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例returnsum([h[0]forhinheap])```區(qū)域動(dòng)態(tài)規(guī)劃算法實(shí)現(xiàn)示例給定一個(gè)背包的容量W和n個(gè)物品，每個(gè)物品有重量w[i]和價(jià)值v[i]，求在不超過背包容量的情況下，如何選擇物品使得背包內(nèi)物品的總價(jià)值最大。定義一個(gè)二維數(shù)組dp，其中dp[i][j]表示前i個(gè)物品中選擇總重量不超過j的情況下能得到的最大價(jià)值。根據(jù)狀態(tài)轉(zhuǎn)移方程dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])(當(dāng)j>=w[i]時(shí))，以及初始條件dp[0][j]=0和問題描述算法思路背包問題算法實(shí)現(xiàn)示例06總結(jié)回顧與展望未來動(dòng)態(tài)規(guī)劃基本概念動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)、計(jì)算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使