最近給別人補習算法課程時製作的動態規劃課件,分享給大家自學。(內容很多,全部使用了Matlab實現,建議大家收藏,以後有時間慢慢看)
function F = factorial(n)% 利用遞歸求正整數n的階乘 if n == 1 % 遞歸的出口 F = 1; else F = n * factorial(n-1); endendfunction F = fib_dg(n)% 利用遞歸求解斐波那契數列 if n == 0 % 遞歸的第一個出口 F = 0; elseif n == 1 %遞歸的第二個出口 F = 1; else F = fib_dg(n-1) + fib_dg(n-2); endendfunction F = fib_dg_memo(n) % 利用帶有備忘錄的遞歸求解斐波那契數列 global memo % 備忘錄定義成全局變量 if n == 1 || n == 2 % 兩個出口 F = 1; elseif memo(n) ~= -1 % 每次遇到一個子問題先去「備忘錄」裡查一查, % 如果發現之前已經解決過這個問題了,直接把答案拿出來用 F = memo(n); else % 每次算出某個子問題的答案後別急著返回,先記到「備忘錄」裡再返回 memo(n) = fib_dg_memo(n-1) + fib_dg_memo(n-2); F = memo(n); endendfunction F = fib_zdxs(n)% 利用自底向上的思想求解斐波那契數列 FF = ones(1,n); % 初始化保存中間結果的數組(向量)全為1 if n <= 2 F = 1; else for i = 3:n FF(i) = FF(i-1) + FF(i-2); end F = FF(n); endend%% 題目來源:力扣198. 打家劫舍 function f = house_robber1(M) % 輸入的M就是每間房子裡面的金額 n = length(M); % 一共多少間房子 if n == 1 % 只有第1間房子可以偷時,f應該等於這間房子的金額 f = M(1); elseif n == 2 % 只有前兩間房子可以偷時,f應該等於較大的金額 f = max(M(1),M(2)); else % 超過三間房可以偷 FF = zeros(1,n); % DP數組,保存f(k) FF(1) = M(1); % 邊界條件 FF(2) = max(M(1),M(2)); % 邊界條件 for i = 3:n % 利用狀態轉移方程循環計算 FF(i) = max(FF(i-1),FF(i-2)+M(i)); end f = FF(n); % 輸出FF中最後一個元素,也就是原問題的解 endend
%% 通過狀態壓縮來節省空間消耗function f = house_robber2(M) % 輸入的M就是每間房子裡面的金額 n = length(M); % 一共多少間房子 if n == 1 % 只有第1間房子可以偷時,f應該等於這間房子的金額 f = M(1); elseif n == 2 % 只有前兩間房子可以偷時,f應該等於較大的金額 f = max(M(1),M(2)); else pre2 = M(1); % 保存F(i-2)的值 pre1 = max(M(1),M(2)); % 保存F(i-1)的值 for i = 3:n cur = max(pre1,pre2+M(i)); % 即FF(i) = max(FF(i-1),FF(i-2)+M(i)); pre2 = pre1; % F(i-2)往前進1位變成F(i-1) pre1 = cur; % F(i-1)往前進1位變成F(i) end f = cur; % 輸出FF(i),此時i=n,也就是原問題的解 endend%% 怎麼輸出偷竊的房屋編號?% 注意:產生最大偷竊金額的方案不唯一,我們這裡只要求輸出任意一個方案即可。% 例如M=[1,3,2]就有兩種方案.function [f, IND] = house_robber3(M)% 輸入的M就是每間房子裡面的金額% f是能夠偷竊到的最高金額,IND是偷竊的房屋編號 n = length(M); % 一共多少間房子 if n == 1 % 只有一間房子 f = M(1); IND = 1; elseif n == 2 % 只有兩間房子 [f, IND] = max([M(1),M(2)]); % f是最大值,IND是最大值對應的下標 % 注意這裡的細節,我把M(1)和M(2)放在了中括號內構成了一個向量 % 相當於是計算向量中最大的元素,為什麼要這麼做呢? 因為我們要輸出最大值對應的下標 % 大家可以測試:[f, IND] = max([1,2]) 和 [f, IND] = max(1,2) % 後面這種寫法會報錯 else % 大於兩間房子的情況 FF = zeros(1,n); % DP數組,保存f(k) FF(1) = M(1); FF(2) = max(M(1),M(2)); for i = 3:n FF(i) = max(FF(i-1),FF(i-2)+M(i)); end f = FF(n); % FF中可以提取出盜竊的房屋信息(這裡的實現細節請看課件) IND = []; ind = find(FF == FF(end),1); IND = [IND,ind]; while FF(ind) > M(ind) ind = find(FF == (FF(ind) - M(ind)),1); IND = [IND,ind]; end IND = IND(end:-1:1); % 翻轉一下(變成從小到大) endend
% 題目來源:劍指 Offer 47: 禮物的最大價值function f = max_gift_value1(M) % 輸入的M就是棋盤中每個禮物的價值 [m,n] = size(M); % 棋盤m行n列 FF = M; % 初始化DP數組和M完全相同,用來保存f(i,j) % 計算FF的第一列 FF(:,1) = cumsum(M(:,1)); % cumsum函數用來計算累加和 % 計算FF的第一行 FF(1,:) = cumsum(M(1,:)); % 循環計算右下部分的元素 for i = 2:m for j = 2:n tem1 = FF(i,j-1) + M(i,j); % 從左邊來 tem2 = FF(i-1,j) + M(i,j); % 從上面來 FF(i,j) = max(tem1,tem2); end end f = FF(m,n);end%% 怎麼輸出所走的路線?function [f,path] = max_gift_value2(M) % 輸入的M就是棋盤中每個禮物的價值 [m,n] = size(M); % 棋盤m行n列 FF = M; % 初始化DP數組和M完全相同,用來保存f(i,j) % 計算FF的第一列 FF(:,1) = cumsum(M(:,1)); % cumsum函數用來計算累加和 % 計算FF的第一行 FF(1,:) = cumsum(M(1,:)); % 循環計算右下部分的元素 for i = 2:m for j = 2:n tem1 = FF(i,j-1) + M(i,j); % 從左邊來 tem2 = FF(i-1,j) + M(i,j); % 從上面來 FF(i,j) = max(tem1,tem2); end end f = FF(m,n); % 根據程序中得到的DP數組(FF)來推出對應的路徑path path = zeros(m,n); % path全為0和1組成,1表示經過該格子 i = m; j = n; while i ~= 1 || j ~= 1 % 只要沒有回到原點 path(i,j) = 1; % 把path矩陣的第i行第j列變成1(表示訪問了這個格子) if i == 1 % 如果到了第一行 path(1,1:j) = 1; % 剩餘的路徑沿著左邊一直走就可以了 break % 退出循環 end if j == 1 % 如果到了第一列 path(1:i,1) = 1; % 剩餘的路徑沿著上方一直走就可以了 break % 退出循環 end tmp1 = FF(i-1,j); % 上方單元格FF的值 tmp2 = FF(i,j-1); % 左邊單元格FF的值 ind = find([tmp1,tmp2] == (FF(i,j)-M(i,j)),1); % 看哪個值等於FF(i,j)-M(i,j) if ind == 1 % 如果上方單元格FF的值等於FF(i,j)-M(i,j) i = i-1; % 說明上一步沿著上方來的 else % 如果左邊單元格FF的值等於FF(i,j)-M(i,j) j = j-1; % 說明上一步沿著左邊來的 end end end%% 題目來源:零錢兌換(力扣 322)function f = coin_change1(coins, S) % coins:不同面值的硬幣,S:總金額 % f(x) = min{f(x-c_i) for every c_i in coins} + 1 % x<0時, f(x)=+inf; x=0時, f(x)=0. FF = +inf * ones(1,S+2); % 初始化DP數組全為正無窮 % 注意,這個DP數組長度為S+2,前面S個才是我們有用的 % FF(x)為湊成目標金額x(x≤S)所需的最少的硬幣個數 % 為什麼這裡還要在後面再加上兩個元素呢? % 後面大家就知道這樣做的妙處了~ FF(S+2) = 0; % 最後一個元素改為0 for x = 1:S % 注意,FF只需要更新前S個元素 tmp = x - coins; % 計算出 'x-c_i' for every c_i in coins tmp(tmp<0) = S+1; % FF下標為S+1的元素為+inf,所以我們把tmp<0的位置變成S+1 tmp(tmp==0) = S+2; % FF下標為S+2的元素為0,所以我們把tmp=0的位置變成S+2 FF(x) = min(FF(tmp))+1; % f(x) = min{f(x-c_i) for every c_i in coins} + 1 end if FF(S) < +inf f = FF(S); else f = -1; % 如果沒有任何一種硬幣組合能組成總金額S就返回-1 endend%% 怎麼得到具體的硬幣組合function [f, IND] = coin_change2(coins, S) FF = +inf * ones(1,S+2); FF(S+2) = 0; % 最後一個元素改為0 for x = 1:S tmp = x - coins; tmp(tmp<0) = S+1; tmp(tmp==0) = S+2; FF(x) = min(FF(tmp))+1; end % 利用FF來計算IND IND = []; % IND表示我們選擇的硬幣組合,初始化為空向量 if FF(S) < +inf % 存在能湊成S的組合 f = FF(S); ind = S; % ind先指向最後一個位置S while FF(ind) > 1 % 如果FF(ind) = 1時就不用尋找了 indd = ind; % 保存前一個位置 tmp = ind - coins; tmp(tmp<0) = S+1; % FF下標為S+1的元素為+inf tmp(tmp==0) = S+2; % FF最後一個元素為0 ind = tmp(find(FF(tmp) == (FF(ind) -1),1)); % 找到新的位置 IND = [IND,indd-ind]; % 兩個位置之差就是我們要添加的硬幣 end IND = [IND,ind]; % FF(ind) = 1時,把ind也放入到IND中 else % 如果沒有任何一種硬幣組合能組成總金額S就返回-1 f = -1; endend
%% 01背包問題(01 Knapsack problem)function f = knapsack01problem1(p,w,W) % 輸入:p:物品的利潤 w:物品的重量 W:背包的容量 % 為了編程方便,假設W是大於等於2的正整數;w中每個元素都是大於等於1的正整數 m = length(p); % 物品個數 FF = zeros(m,W); % 初始化DP數組 % FF(i,j):前i件物品選擇性的放入容量為j的背包中所能獲得的最大利潤 if w(1) <= W % 初始化第一行 FF(1,w(1):end) = p(1); end if w(1) == 1 % 初始化第一列 FF(1,1) = p(1); end % i,j>1的情況 for i = 2:m for j = 2:W if w(i) > j % 第i件物品的重量w(i)比背包的容量j還要大 FF(i,j) = FF(i-1,j) ; elseif w(i) == j % 第i件物品的重量w(i)等於背包的容量j FF(i,j) = max(FF(i-1,j), p(i)); % 不放進去和放進去取較大的值 else % 第i件物品的重量w(i)小於背包的容量j FF(i,j) = max(FF(i-1,j), p(i)+FF(i-1,j-w(i))); % 不放進去和放進去取較大的值 end end end f = FF(m,W);end%% 怎麼得到選擇的物品編號?function [f, IND] = knapsack01problem2(p,w,W) % 輸入:p:物品的利潤 w:物品的重量 W:背包的容量 % 為了編程方便,假設W是大於等於2的正整數;w中每個元素都是大於等於1的正整數 m = length(p); % 物品個數 FF = zeros(m,W); % 初始化DP數組 % FF(i,j):前i件物品選擇性的放入容量為j的背包中所能獲得的最大利潤 if w(1) <= W % 初始化第一行 FF(1,w(1):end) = p(1); end if w(1) == 1 % 初始化第一列 FF(1,1) = p(1); end % i,j>1的情況 for i = 2:m for j = 2:W if w(i) > j % 第i件物品的重量w(i)比背包的容量j還要大 FF(i,j) = FF(i-1,j) ; elseif w(i) == j % 第i件物品的重量w(i)等於背包的容量j FF(i,j) = max(FF(i-1,j), p(i)); % 不放進去和放進去取較大的值 else % 第i件物品的重量w(i)小於背包的容量j FF(i,j) = max(FF(i-1,j), p(i)+FF(i-1,j-w(i))); % 不放進去和放進去取較大的值 end end end f = FF(m,W); IND = []; % 選擇的物品編號IND初始化為空 if f > 0 % 只要有利潤,就可以利用FF來計算選擇的物品編號IND ww = W; % 初始化背包的剩餘容量為整個背包的容量W tmp = FF(:,ww); % 取出最後一列 while 1 % 不斷循環下去,後面通過條件判斷來退出循環 ind = find(tmp == max(tmp),1) ; % 找到裝入背包的那個物品 ww = ww - w(ind); % 更新背包的剩餘容量 IND = [IND,ind]; % 更新IND裡面的元素 if ind > 1 && ww>0 % 只要不是第一個物品或者背包容量為空 tmp = FF(1:ind-1,ww); % 重新取出剩餘容量的那一列(只保留前面的物品) else break % 跳出循環 end end IND = sort(IND); % 排序下,輸出好看點 endend%% 求硬幣兌換的方案數function [f, FF]= coin_change_numbers(coins, S)% 這裡也可以返回FF,FF就是DP數組,1992年國賽那一題有用 coins = sort(coins); % 先排個序 m = length(coins); % 一共m種硬幣 FF =zeros(m,S); % 初始化DP數組 % FF(i,j):只能使用前i種面值的硬幣來湊出總金額 j 的錢的方案數目 % 初始化第一行(只有第1種硬幣,需要湊出金額為j的錢) FF(1,: ) = (mod(1:S,coins(1))==0); % 初始化第一列(只能使用前i種面值的硬幣,需要湊出金額為1的錢的方法數) FF(:,1) = (coins(1) == 1); % i,j>1的情況 for i = 2:m % 使用了前i種面值的硬幣 for j = 2:S % 湊出金額為j的錢 if j-coins(i) < 0 % 如果第i個硬幣的面值比j還要大,那第i個硬幣沒起到作用 FF(i,j) = FF(i-1,j); elseif j-coins(i) == 0 % 如果第i個硬幣的面值等於j,那有了第i個硬幣後相當於多了1種方法 FF(i,j) = FF(i-1,j) + 1; else % 如果第i個硬幣的面值小於j,那就可以等價於兩部分之和: FF(i,j) = FF(i-1,j) + FF(i,j-coins(i)); end end end f = FF(m,S);end
%% 國賽1992年真題coins = [57,71,87,97,99,101,103,113,114,115,128,129,131,137,147,156,163,186][f, FF] = coin_change_numbers(coins, 1000);ff = FF(end,:); % 取出DP數組(FF)的最後一行(即分子量從X為1至1000時的方案數)ff(100:100:1000) % 每隔100輸出一次值plot(ff,'LineWidth',2) % 線的寬度取2,好看一點xlabel('分子量'); ylabel('方案數'); % x y軸的坐標軸標籤% 作業1:爬樓梯% 題目來源:力扣70. 爬樓梯 連結:https://leetcode-cn.com/problems/climbing-stairsfunction F = homework1(n) if n == 1 F = 1; elseif n == 2 F = 2; else FF = ones(1,n); % 初始化DP數組 FF(2) = 2; for i = 3:n FF(i) = FF(i-1) + FF(i-2); end F = FF(n); endend% 作業2:機器人走格子% 題目來源:力扣62. 不同路徑 連結:https://leetcode-cn.com/problems/unique-paths/function f = homework2(m,n) % 格子有m行n列 FF = ones(m,n); % 初始化DP數組全為1 % 循環計算右下部分的元素 for i = 2:m for j = 2:n tem1 = FF(i,j-1); % 左側過來 tem2 = FF(i-1,j); % 上面過來 FF(i,j) = tem1+tem2; end end f = FF(m,n);end% 作業3:機器人走有障礙的格子% 題目來源:力扣63. 不同路徑 II 連結:https://leetcode-cn.com/problems/unique-paths-ii/function f = homework3(obstacle) % obstacle是障礙物矩陣,全為0和1組成,1表示有障礙物 [m,n] = size(obstacle); FF = ones(m,n); % 初始化DP數組 % 處理第一列 for i = 1:m if obstacle(i,1) == 1 % 發現了障礙物 FF(i:end,1) = 0; % 障礙物所處的位置以及下方的位置對應的f(i,j)=0 break end end % 處理第一行 for j = 1:n if obstacle(1,j) == 1 FF(1,j:end) = 0; % 障礙物所處的位置以及右邊的位置對應的f(i,j)=0 break end end % 循環計算右下部分的元素 for i = 2:m for j = 2:n if obstacle(i,j) == 1 FF(i,j) = 0; else FF(i,j) = FF(i,j-1)+FF(i-1,j); end end end f = FF(m,n);end% 作業4:擲骰子的N種方法% 題目來源:力扣1155. 擲骰子的N種方法 連結:https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sumfunction f = homework4(m, f, S)% m個骰子,每個骰子f個面,需要擲出總點數為S FF = zeros(m,S); % 初始化DP數組 % 處理第一列 FF(1,1) = 1; % 第一個元素為1,其餘位置元素為0. % 處理第一行 for j = 1:S if j <= f FF(1,j) = 1; % 前f個元素(如果有的話)為1,其餘位置元素為0. end end % 循環計算右下部分的元素 for i = 2:m for j = 2:S for k = 1:f if j > k FF(i,j) = FF(i,j)+FF(i-1,j-k); else break end end end end f = FF(m,S);end% 作業5:編輯距離% 題目來源:力扣72. 編輯距離 連結:https://leetcode-cn.com/problems/edit-distance/function f = homework5(word1,word2) m = length(word1); n = length(word2); FF = ones(m,n); % 初始化DP數組% 處理第一行 ind = strfind(word2, word1(1)); % 在word2中找word1的第一個字母 for j = 1:n if isempty(ind) % word1的第1個字母不在word2中 FF(1,j)=j; % word1的第一個字母在word2中時, ind裡面可能有多個位置,我們只需要首次出現的位置 elseif ind(1)==1 % word1和word2的第1個字母相同 FF(1,j)=j-1; else % 如果位置不為1,那麼該位置之前的FF(1,j)=j,該位置以及該位置之後的FF(1,j)=j-1 if j < ind(1) FF(1,j)=j; else FF(1,j)=j-1; end end end% 處理第一列 ind = strfind(word1, word2(1)); % 在word1中找word2的第一個字母 for i = 1:m if isempty(ind) % word2的第1個字母不在word1中 FF(i,1)=i; % word2的第一個字母在word1中時, ind裡面可能有多個位置,我們只需要首次出現的位置 elseif ind(1)==1 % word1和word2的第1個字母相同 FF(i,1)=i-1; else % 如果位置不為1,那麼該位置之前的FF(i,1)=i,該位置以及該位置之後的FF(i,1)=i-1 if i < ind(1) FF(i,1)=i; else FF(i,1)=i-1; end end end % 循環計算右下部分的元素 for i = 2:m for j = 2:n tmp1 = FF(i-1,j-1) + (word1(i) ~= word2(j))*1; % 先把 word1[1..i-1] 變換到 word2[1..j-1],消耗掉FF(i-1,j-1)步, % 再把 word1[i] 改成 word2[j],就行了。 % 這裡分為兩種情況:如果 word1[i] == word2[j],什麼也不用做,一共消耗 FF(i-1,j-1) 步; % 否則需要替換最後一個字符,一共消耗 FF(i-1,j-1) + 1 步。 tmp2 = FF(i-1,j) + 1; % 先把 word1[1..i-1] 變換到 word2[1..j],消耗掉 FF(i-1,j) 步, % 再把 word1[i] 刪除,這樣word1[1..i] 就完全變成了 word2[1..j] 了, % 一共消耗FF(i-1,j)+ 1 步。 tmp3 = FF(i,j-1) + 1; % 先把 word1[1..i] 變換成 word2[1..j-1],消耗掉 FF(i,j-1) 步 % 接下來,再插入一個字符 word2[j], word1[1..i] 就完全變成了 word2[1..j] 了。 % 一共消耗FF(i,j-1)+ 1 步。 FF(i,j) = min([tmp1,tmp2,tmp3]); % 從上面三個問題來看,word1[1..i] 變換成 word2[1..j] 主要有三種操作 % 哪種操作步數最少就用哪種。 end end f =FF(m,n);end