動态規劃初識
本文所有内容來自對動态規劃相關内容的個人總結筆記，如果覺得這篇部落格講的不夠的話可以點選以下連結觀看視訊
【動态規劃專題班】ACM總冠軍、清華+斯坦福大神帶你入門動态規劃算法
動态規劃的解題思路
最後一步
顧名思義，這裡的最後一步就是要我們去找出題目的“最後一步”，在常見的走樓梯問題中，最後一步就是走完樓梯選擇的台階數，在找零問題中最後一步就是達到指令金額用的最後一個硬币。
轉移方程
轉移方程是用數學語言對于解題思路的總結，動态規劃的解題思路就是周遊比較，而周遊會存在邊界，是以需要設定邊界條件
邊界條件
邊界條件是最容易的，就是動态規劃的前一步或者前兩步的答案，一般稍加思考就能得出
動态規劃的基本問題
動态規劃一般是對一些求最優解、求方法數量，求存在性的問題的解決思路，比如最基礎的找零問題、走樓梯問題等等，這些問題都有着一定的共性，我将結合一些例題來講述我對動态規劃的了解。
爬樓梯問題
這裡引用力扣的兩道爬樓梯題來入門
例題1 爬樓梯
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？
在思考動态問題的時候，我們通常要發現其中存在的規律。
先假設爬到樓頂的方法為 f(n)（n為台階數）
最後一步
這裡的最後一步有可能是1個台階或者2個台階，那麼我們可以得出結論：爬上n-1階樓梯的方法數加上爬上n-2階樓梯的方法數等于爬到樓頂（即n階）的方法數
轉移方程
用數學語言表達出來就是 f(n)=f(n-1)+f(n-2)
邊界條件
有了這個式子，我們隻需要 f(1)和 f(2)，就可以往後遞推，求出對應任何台階數的值。
而 f(1)=1，f(2)=2
三個要素都有了，思路已經很清晰了，我們就可以開始寫代碼了
代碼實作如下：
class Solution {
public int climbStairs(int n) {
int[] dp=new int[n+1];
//因為需要定義邊界條件是以需要将邊界條件對應的答案排除，避免出現異常
if(n==1){
return 1;
}
if(n==2){
return 2;
}
dp[0]=0;
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++)
{
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
}
做完最簡單的，那我們來為這道題目加一點變化
例題2 使用最小花費爬樓梯
數組的每個下标作為一個階梯，第 i 個階梯對應着一個非負數的體力花費值 cost[i]（下标從 0 開始）。
每當你爬上一個階梯你都要花費對應的體力值，一旦支付了相應的體力值，你就可以選擇向上爬一個階梯或者爬兩個階梯。
請你找出達到樓層頂部的最低花費。在開始時，你可以選擇從下标為 0 或 1 的元素作為初始階梯。
細節如圖
先設爬到第n級階梯的最小值為f(n)
最後一步
跟上一道題有一些差別，上一道題是求方法數，這一題是求最大值，是以這一題的最後一步是
爬到上一級階梯的最小值加上體力花費值和上兩級階梯的最小值加上體力花費值之間的最小值
轉移方程
根據最後一步可以得出轉移方程為f(n)=min(f(n-2)+cost[i],f[n-1]+cost[i])
邊界條件
f(0)=cost[0],f(1)=min(cost[0],cost[1])
最終代碼實作如下：
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp=new int[cost.length+1];
dp[0]=dp[1]=0;
for(int i=2;i<=cost.length;i++)
{
dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[cost.length];
}
}
讓我們換一種題來做一下
打家劫舍
你是一個專業的小偷，計劃偷竊沿街的房屋。每間房内都藏有一定的現金，影響你偷竊的唯一制約因素就是相鄰的房屋裝有互相連通的防盜系統，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統會自動報警。
給定一個代表每個房屋存放金額的非負整數數組，計算你 不觸動警報裝置的情況下 ，一夜之内能夠偷竊到的最高金額。
最後一步
這裡因為不能偷相鄰的房，是以就是取偷到前一間房的最大值和偷到這間房的最大值之間的最大值
轉移方程
設偷到第n間房的最大值為f(n)
則轉移方程為f(n)=max(f(n-2)+nums[i]),f(n-1))
邊界條件
f(0)=nums[0],f(1)=max(nums[0],nums[1])
最終代碼如下
class Solution {
public int rob(int[] nums) {
int n=nums.length;
int[] dp=new int[n];
if(n==1)
{
return nums[0];
}
dp[0]=nums[0];
dp[1]=Math.max(nums[0],nums[1]);
for(int i=2;i<n;i++)
{
dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
}
return dp[n-1];
}
}
先寫這麼多，有些題還沒做，會有後續的。