文章目錄
- 動态規劃算法
-
- 算法核心
- 動态規劃的兩種形式
- 動态規劃的原理
- 動态規劃的經典模型
- 動态規劃可以處理的題目類型
- 題目
-
- 70.爬樓梯
-
- 題目大意
- 解題思路
- 代碼實作
- 198. 打家劫舍
-
- 題目大意
- 解題思路
- 代碼實作
- 213. 打家劫舍 II
-
- 題目大意
- 解題思路
- 代碼實作
動态規劃算法
算法核心
Those who cnnot remrember the past are condemned to repeat it.
動态規劃算法的核心就是記住已經解決過的子問題的解。
動态規劃的兩種形式
-
自頂向下的備忘錄法
以斐波那契數列為例子，備忘錄方法的思想就是建立一個
n+1
fib(n)
Memo
fib(n)
-
自底向上的動态規劃
備忘錄法還是利用了遞歸，備忘錄法在計算
fib(6)
fib(1)、fib(2)、fib(3)...
fib(1)、fib(2)、fib(3)...
，這就是動态規劃的核心，先解決子問題，再由子問題計算父問題。
自底向上方法也是利用數組儲存了先計算的值，為後面的調用服務。
一般來說由于備忘錄方式的動态規劃使用了遞歸，遞歸的時候會産生額外的開銷，使用自底向上的動态規劃要比備忘錄方法好。
動态規劃的原理
如果問題涉及到了重疊子問題和最優子結構，我們就使用動态規劃。
-
最優子結構
用動态規劃求解最優化問題的第一步就是刻畫最優解的結構。問題的最優解由相關子問題的最優解組合而成，而這些子問題可以獨立求解，就稱此問題具有最優子結構性質。是以，某個問題是否适用于動态規劃算法，就看他是否具有最優子結構的性質。使用動态規劃算法時，用子問題的最優解來構造原問題的最優解。是以必須考察最優解中用到的所有子問題。
-
重疊子問題
在斐波那契數列問題中，可以看到大量的重疊子問題，比如在求解
fib(6)
fib(2)
動态規劃的經典模型
最重要的是狀态轉移方程。
- 線性模型
- 區間模型
- 背包模型
動态規劃可以處理的題目類型
- 斐波那契數列問題
- 矩陣路徑問題
- 數組區間問題
- 分割整數問題
- 最長遞增子序列問題
- 最長公共子序列問題
- 0-1背包問題
- 股票交易問題
- 字元串編輯問題
題目
70.爬樓梯
題目大意
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
解題思路
注意出口值，當
i
等于1時，如果出現
dp[2]=2
就會出現數組下标越界的情況。
代碼實作
class Solution {
public int climbStairs(int n) {
//動态規劃
int[] dp=new int[n+1];
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
}
198. 打家劫舍
題目大意
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。
解題思路
當數組隻有一個元素的時候，如果用
dp
數組就會出現數組下标越界。
代碼實作
class Solution {
public int rob(int[] nums) {
//動态規劃
int n=nums.length;
int pre1=0,pre2=0,cur=0;
for(int i=0;i<n;i++){
cur=Math.max(pre2+nums[i],pre1);
pre2=pre1;
pre1=cur;
}
return cur;
}
}
213. 打家劫舍 II
題目大意
你是一個專業的小偷，計劃偷竊沿街的房屋，每間房内都藏有一定的現金。這個地方所有的房屋都 圍成一圈 ，這意味着第一個房屋和最後一個房屋是緊挨着的。同時，相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警 。
給定一個代表每個房屋存放金額的非負整數數組，計算你 在不觸動警報裝置的情況下 ，能夠偷竊到的最高金額。
在這裡插入圖檔描述
解題思路
環裝排列意味着第一個房子和最後一個房子隻能偷其中的一個，是以可以把環狀問題轉化為兩個單排列問題：
- 不偷第一個房子，偷最後一個房子
- 偷第一個房子，不偷最後一個房子
代碼實作
class Solution {
public int rob(int[] nums) {
int n=nums.length;
if(n==0){
return 0;
}
if(n==1){
return nums[0];
}
return Math.max(robHouse(nums,0,n-2),robHouse(nums,1,n-1));
}
public int robHouse(int[] nums,int l,int r){
int pre1=0,pre2=0,cur=0;
for(int i=l;i<=r;i++){
cur=Math.max(pre1+nums[i],pre2);
pre1=pre2;
pre2=cur;
}
return cur;
}
}