瑞客論壇戀上數(shù)據(jù)結構與算法第二季帶24集

動態(tài)規(guī)劃（Dynamic@M了個 實 教育 動態(tài)規(guī)劃（Dynamic動態(tài)規(guī)劃，簡稱通常的使用套路（一步一步優(yōu)化 遞歸（自頂向下，出現(xiàn) 化搜索（自頂向下③遞推（自底向上①定義狀態(tài)（狀態(tài)是原問題、子問題的解dp(i)②設置初始狀態(tài)（邊界dp(0)dp(i)dp(i1) DynamicProgrammingisamethodforsolvingacomplexproblembybreakingitdownintoacollectionofsimplersubproblems,solvingeachofthosesubproblemsjustonce,andstoringtheir②每個子問題僅僅解決1某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響（未來與過去無關(0,(i,(i–1,(0,(i,(i–1,(i,(4,dp(i,j（0,0）走到（i,j）dp(i,0)=dp(0j)=dp(i,j)=dp(i,j–1)+dp(i–1,dp(i,jdp(i,j1)、dp(i1,jdp(i,j1)、dp(i1,j(0,(i,(i–1,(i,(0,(i,(i–1,(i,(4,dp(i,j1)、dp(i1,j練習1 此前用貪心策略得到的并非是最優(yōu)解（5dp(n)n125dp(n)dp(n25)120dp(n)dp(n20)15dp(n)dp(n511dp(n)dp(n1)所以dp(n)mindp(n–25dp(n–20dp(n–5dp(n–1)找零錢 找零錢 練習2n2、1、–3、4、–1、2、1、–5、441)21dp(i)nums[i（nums是整個序列nums[0–22dp(0nums[111，dp(1nums[2–31、–3dp(2dp(1–3以nums[3]4結尾的最大連續(xù)子序列是 所以dp(3)=nums[4–14、–1dp(4dp(3–1nums[524、–1、2，dp(5dp(42以nums[6]1結尾的最大連續(xù)子序列是4、–1、 1，所以dp(6)=dp(5)+1=nums[7–54、–1、2、1、–5dp(7dp(6–5nums[844、–1、2、1、–5、4dp(8dp(74

dp(i1)0，dp(i)=dp(i1)0dp(i)dp(i1)dp(0)dp(i)maxdp(i)i[0,練習3最長上升子序列（最長遞增子序列，LongestIncreasingleetcode_300_最長上升子序列： 給定一個無序的整數(shù)序列，求出它最長上升子序列的長度（要求嚴格上升[10,2251710118][2,5,7101]、[2,5,718]nums，[10,2,2,5,1,7,101,dp(inums[i]結尾的最長上升子序列的長度，i[0,nums[01010，dp(0nums[122，dp(1nums[222，dp(2nums[352、5dp(3dp(11dp(21nums[411，dp(4nums[572、5、7dp(5dp(31以nums[6]101結尾的最長上升子序列是 5、7、101，所以dp(6)=dp(5)+1=nums[7182、5、7、18dp(7dp(51dp(imaxdp(ii[0,j∈[0,

nums[inumsnums[inumsjdp(jdp(jdp(i)=max{dp(i),dp(j)+1nums[inumsnums[inumsjdp(0)=dp(i)2251722517 將它壓在（從左邊數(shù)過來）22122157思路（nums，也就是最初的牌數(shù)組top[i]ilen遍歷每一張牌num最終要放入的牌堆位置numindextop[index]indexlen，相當于新建一個牌堆，牌堆數(shù)量+1，空間復雜度：O時間復雜度：O練習4最長公共子序列（LongestCommon 1,910]ABCBDABBDCABA4，ABCBDABBDCABAABCBDABBDCABAABCBDABBDCABAABCBDABBDCABAnums1[i–前inums1[i–前i1個元i∈[1,nums2[j–前nums2[j–前j1個元dp(ijnums1i個元素】與【nums2jdp(i0)、dp(0,jnums1[i–1]nums2j1]dp(ijdp(i–1j–1)nums1[i1nums2j1]dp(ijmaxdp(i–1jdp(ij1)前i1個元前i1個元前i1個元nums1[i–前i1個元前j1個元nums2[j–前j1個元前j1個元空間復雜度：Ok,k=min{n,m}，n、m是2個序列的長時間復雜度：O2n，當n=mlcs(8,lcs(8,lcs(7,lcs(7,lcs(7,lcs(7,lcs(7,lcs(8,lcs(8,lcs(6,空間復雜度：On?時間復雜度：O(n?dpAB DAB 01234567000000000B100111111D200111222C300122222A401122233B501223334A601223344可以空間復雜度優(yōu)化至Ok,k=min{n,練習5最長公共子串（LongestCommonABCBABABCAABC2str1、i∈[1,j∈[1,dp(ijstr1[i1]、str2j1]dp(i0)、dp(0,jstr1[i–1]str2j–1]dp(ijdp(i–1,j–1)str1[i1str2j1]dp(ijdp(ijmaxdp(ij空間復雜度：On?時間復雜度：O(ndpBABCA 0123450000000A1001001B2010200C3000030B4010100A5002001空間復雜度：Ok k=min{n,時間復雜度：O(n練習60-1有n件物品和一個最大承重為W的背包，每件物品的重量是??i、價值是W101valuesweightskvalues[kweights[k]，k[0,dp(ijj、i時的最大總價值，i∈[1,n]，j∈[1,dp(i0)、dp(0,jjweights[i–1]dp(ijdp(i–1,j≥weights[i–1]dp(ijmaxdp(i–1,jdp(i–1,j–weights[i–1values[i–1]0-10-1dpij0123456789000000000000v=6,100666666666v=3,200669999999v=5300669999v=4,40066999v=6,50066990-1dp(ijdp(i–1kii1kjj0-1觀察二維數(shù)組表，得出結論：j1weights[i0-1有n件物品和一個最大承重為W的