動態(tài)規(guī)劃（英語：Dynamic programming，DP）是一種在數(shù)學(xué)锹杈、計算機(jī)科學(xué)和經(jīng)濟(jì)學(xué)中使用的撵孤，通過把原問題分解為相對簡單的子問題的方式求解復(fù)雜問題的方法。 動態(tài)規(guī)劃常常適用于有重疊子問題和最優(yōu)子結(jié)構(gòu)性質(zhì)的問題竭望，動態(tài)規(guī)劃方法所耗時間往往遠(yuǎn)少于樸素解法邪码。
動態(tài)規(guī)劃背后的基本思想非常簡單撒轮。大致上只锭，若要解一個給定問題，我們需要解其不同部分（即子問題）翼闹，再合并子問題的解以得出原問題的解枫振。 通常許多子問題非常相似喻圃，為此動態(tài)規(guī)劃法試圖僅僅解決每個子問題一次，從而減少計算量： 一旦某個給定子問題的解已經(jīng)算出粪滤，則將其記憶化存儲，以便下次需要同一個子問題解之時直接查表杖小。 這種做法在重復(fù)子問題的數(shù)目關(guān)于輸入的規(guī)模呈指數(shù)增長時特別有用愚墓。
動態(tài)規(guī)劃問題滿足三大重要性質(zhì)
最優(yōu)子結(jié)構(gòu)性質(zhì)：如果問題的最優(yōu)解所包含的子問題的解也是最優(yōu)的昂勉，我們就稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)（即滿足最優(yōu)化原理）。最優(yōu)子結(jié)構(gòu)性質(zhì)為動態(tài)規(guī)劃算法解決問題提供了重要線索岗照。
子問題重疊性質(zhì)：子問題重疊性質(zhì)是指在用遞歸算法自頂向下對問題進(jìn)行求解時，每次產(chǎn)生的子問題并不總是新問題厚者，有些子問題會被重復(fù)計算多次。動態(tài)規(guī)劃算法正是利用了這種子問題的重疊性質(zhì)库菲，對每一個子問題只計算一次志膀，然后將其計算結(jié)果保存在一個表格中，當(dāng)再次需要計算已經(jīng)計算過的子問題時溉浙，只是在表格中簡單地查看一下結(jié)果，從而獲得較高的效率放航。
無后效性：將各階段按照一定的次序排列好之后，對于某個給定的階段狀態(tài)广鳍，它以前各階段的狀態(tài)無法直接影響它未來的決策，而只能通過當(dāng)前的這個狀態(tài)赊时。換句話說，每個狀態(tài)都是過去歷史的一個完整總結(jié)祖秒。這就是無后向性，又稱為無后效性房维。
簡單dp問題分類
1.簡單動態(tài)規(guī)劃算法咙俩，即狀態(tài)方程是用一個維度的變量的描述的，常見的問題如：斐波那契數(shù)列膜蛔，爬臺階問題等
爬臺階問題問題描述： 有一座高度是n級臺階的樓梯皂股，從下往上走命黔，每跨一步只能向上1級或者2級臺階。要求用程序來求出一共有多少種走法卵史。
狀態(tài)描述： 我們使用變量n表示臺階的級數(shù)，F(xiàn)(n)表示n級臺階一共有多少種走法
狀態(tài)轉(zhuǎn)移方程與問題分解： 根據(jù)每次能跨越的臺階數(shù)目：1級臺階或者2級臺階啄踊，因為走到N級臺階之前刁标，人一定是處于N-1級臺階或者N-2級臺階膀懈。F（n）的走法，一定是n-1級別的臺階的所有的走法和n-2級別臺階的所有走法之和硼控。
F(n） = F(n-1) + F(n-2);
int climbStairs(int n) {
vector<int>dp(n+1,0);
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++)
dp[i]=dp[i-1]+dp[i-2];
return dp.back();
}
2.最小路徑和問題牢撼，常見題型：矩陣最小路徑和熏版、三角形最小路徑和
leetcode64
給定一個包含非負(fù)整數(shù)的 m x n 網(wǎng)格撼短，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小曲横。
說明：每次只能向下或者向右移動一步胜榔。
示例:
輸入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小夭织。
int minPathSum(vector<vector<int>>& grid) {
int m=grid.size();
int n=grid[0].size();
int dp[m][n];
dp[0][0]=grid[0][0];
for(int i=1;i<m;i++)
{
dp[i][0]=dp[i-1][0]+grid[i][0];
}
for(int j=1;j<n;j++)
{
dp[0][j]=dp[0][j-1]+grid[0][j];
}
for(int i=1;i<m;i++)
{
for(int j=1;j<n;j++)
{
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
leetcode120
給定一個三角形，找出自頂向下的最小路徑和讲竿。每一步只能移動到下一行中相鄰的結(jié)點上题禀。
例如迈嘹，給定三角形：
自頂向下的最小路徑和為 11（即秀仲，2 + 3 + 5 + 1 = 11）
int minimumTotal(vector<vector<int>>& triangle) {
if(triangle.empty()||triangle[0].empty()) return 0;
for(int i=1;i<triangle.size();i++)
{
for(int j=0;j<triangle[i].size();j++)
{
if(j==0)
triangle[i][j]+=triangle[i-1][j];
else if(j==triangle[i].size()-1)
triangle[i][j]+=triangle[i-1][j-1];
else
triangle[i][j]+=min(triangle[i-1][j],triangle[i-1][j-1]);
}
}
return *min_element(triangle.back().begin(),triangle.back().end());
}
3.背包問題
一個背包有一定的承重cap神僵，有N件物品保礼，每件都有自己的價值炮障，記錄在數(shù)組v中鹦筹，也都有自己的重量，記錄在數(shù)組w中铐拐，每件物品只能選擇要裝入背包還是不裝入背包遍蟋，要求在不超過背包承重的前提下，選出物品的總價值最大它呀。
給定物品的重量w價值v及物品數(shù)n和承重cap下隧。請返回最大總價值谓媒。
測試樣例：
[1,2,3],[1,2,3],3,6
返回：6
int maxvalue(vector<int> &weight,vector<int> &value,int n,int m)
{
vector<int> f(weight.size()+1,0);
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (weight[i] <= j) {
f[j] = f[j] > f[j - weight[i]] + value[i] ? f[j] : f[j - weight[i]] + value[i];
}
}
}
}
leetcode 322
給定不同面額的硬幣 coins 和一個總金額 amount土辩。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)拷淘。如果沒有任何一種硬幣組合能組成總金額，返回 -1启涯。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:
輸入: coins = [2], amount = 3
輸出: -1
int coinChange(vector<int>& coins, int amount) {
int n=coins.size();
if(n<=0 || amount<0) return -1;
vector<int>dp(amount+1,amount+1);
dp[0]=0;
for(int i=1;i<=amount;i++)
{
for(int j=0;j<coins.size();j++ )
{
if(coins[j]<=i)
dp[i]=min(dp[i],dp[i-coins[j]]+1);
}
}
return (dp[amount]>amount) ?-1:dp[amount];
}
4.最長上升子序列問題
leetcode 300
給定一個無序的整數(shù)數(shù)組，找到其中最長上升子序列的長度。
示例:
輸入: [10,9,2,5,3,7,101,18]
輸出: 4
解釋: 最長的上升子序列是 [2,3,7,101]引几，它的長度是 4伟桅。
int lengthOfLIS(vector<int>& nums) {
if(nums.empty()) return 0;
vector<int> dp(nums.size(),1);
int res=0;
for(int i=0;i<nums.size();++i)
{
for(int j=0;j<i;j++)
{
if(nums[i]>nums[j])
dp[i]=max(dp[i],dp[j]+1);
}
res=max(res,dp[i]);
}
return res;
}
5.回文子串問題
leetcode5
給定一個字符串 s玖雁，找到 s 中最長的回文子串赫冬。你可以假設(shè) s 的最大長度為 1000溃列。
示例 1：
輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案听隐。
示例 2：
輸入: "cbbd"
輸出: "bb"
string longestPalindrome(string s) {
if(s.empty()) return "";
const int n=s.size();
int dp[n][n];
int left=0,right=0,len=0;;
for(int i=0;i<s.size();i++)
{
dp[i][i]=1;
for(int j=0;j<i;i++)
{
dp[j][i]= (s[i]==s[j]) &&(i-j<2 || dp[j+1][i-1])；
if(dp[j][i] && len<i-j+1)
{
len=i-j+1;
left=j;
right=i;
}
}
return s.substr(left,right-left+1);
}
}
6.最長上升子序列問題(LCS)
leetcode1143
給定兩個字符串 text1 和 text2咨跌，返回這兩個字符串的最長公共子序列硼婿。
一個字符串的 子序列 是指這樣一個新的字符串：它是由原字符串在不改變字符的相對順序的情況下刪除某些字符（也可以不刪除任何字符）后組成的新字符串加酵。
例如猪腕，"ace" 是 "abcde" 的子序列陋葡，但 "aec" 不是 "abcde" 的子序列。兩個字符串的「公共子序列」是這兩個字符串所共同擁有的子序列捌归。
若這兩個字符串沒有公共子序列，則返回 0剃浇。
示例 1:
輸入：text1 = "abcde", text2 = "ace"
輸出：3
解釋：最長公共子序列是 "ace"，它的長度為 3
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int m=text1.size()+1;
int n=text2.size()+1;
int dp[m][n]={};
for(int i=1;i<m;++i)
{
for(int j=1;j<n;++j)
{
if(text1[i-1]==text2[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;
}
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
};
