??為了準(zhǔn)備三月份藍(lán)橋杯的比賽和提高下自己數(shù)據(jù)結(jié)構(gòu)和算法方面的水平，所以開始在leetcode上刷起了題励幼。剛剛開始刷題的模式還是和之前一樣，一道一道的按順序的做過去掏湾，從easy到medium竹勉，但是發(fā)現(xiàn)這樣的效率很低飞盆，因為每道題的考的知識點思路都不一樣，很難去總結(jié)出相應(yīng)數(shù)據(jù)結(jié)構(gòu)和算法的知識體系和框架次乓。因此我去網(wǎng)上查了下如何刷leetcode效率會比較高吓歇，發(fā)現(xiàn)很多人都推薦剛開始按標(biāo)簽刷會比較好，因為標(biāo)簽下面包含的是同一類算法或數(shù)據(jù)結(jié)構(gòu)的題型票腰，做起來方便總結(jié)相關(guān)知識城看。我想了下的確是這樣，所以選擇了動態(tài)規(guī)劃這個標(biāo)簽開始刷起丧慈。動態(tài)規(guī)劃我也只是之前有所聽聞析命，直到開始刷題才開始慢慢了解其內(nèi)容主卫，題也刷了十幾道，下面就回顧下這些題的做法和解題思想鹃愤，也算是對動態(tài)規(guī)劃一個小小總結(jié)吧簇搅，畢竟溫故而知新嘛。
動態(tài)規(guī)劃
??在開始之前软吐，先介紹下什么是動態(tài)規(guī)劃瘩将、動態(tài)規(guī)劃主要解決什么問題以及動態(tài)規(guī)劃的步驟。
什么是動態(tài)規(guī)劃凹耙？動態(tài)規(guī)劃解決什么問題?
??動態(tài)規(guī)劃算法通常用于求解具有某種最優(yōu)性質(zhì)的問題姿现。在這類問題中，可能會有許多可行解肖抱。每一個解都對應(yīng)于一個值备典，我們希望找到具有最優(yōu)值的解。動態(tài)規(guī)劃算法與分治法類似意述，其基本思想也是將待求解問題分解成若干個子問題提佣，先求解子問題，然后從這些子問題的解得到原問題的解荤崇。與分治法不同的是拌屏，適合于用動態(tài)規(guī)劃求解的問題，經(jīng)分解得到子問題往往不是互相獨立的术荤。若用分治法來解這類問題倚喂，則分解得到的子問題數(shù)目太多，有些子問題被重復(fù)計算了很多次瓣戚。如果我們能夠保存已解決的子問題的答案端圈，而在需要時再找出已求得的答案，這樣就可以避免大量的重復(fù)計算带兜，節(jié)省時間枫笛。我們可以用一個表來記錄所有已解的子問題的答案。不管該子問題以后是否被用到刚照，只要它被計算過刑巧，就將其結(jié)果填入表中。這就是動態(tài)規(guī)劃法的基本思路无畔。（來自百度百科）
動態(tài)規(guī)劃步驟
1啊楚、拆分問題：看看問題是否能拆分成若干個子問題，從而通過解決子問題得到整個問題的解浑彰。（自頂向下）
2恭理、找出子問題間的的關(guān)聯(lián)，從而將其狀態(tài)轉(zhuǎn)移方程確定（自底向上郭变，最難的一步）
3颜价、解決問題（用數(shù)組或變量將其狀態(tài)存儲涯保，并進(jìn)行遞歸求解）
空談?wù)`國，實干興邦周伦。下面開始對題目進(jìn)行分析和總結(jié)夕春，從中了解動態(tài)規(guī)劃的奧妙。
Leetcode動態(tài)規(guī)劃習(xí)題分析和總結(jié)
5.最長回文子串（medium）
這道題是開始刷的第一道題专挪，開始真是一點思路都沒有及志，只有用暴力解將其子串一個個求出并將其子串進(jìn)行回文判斷，若是回文則將其大小輸出并與當(dāng)時maxSize進(jìn)行比較寨腔。暴力解的時間復(fù)雜度應(yīng)該達(dá)到了O(n^3),因超出時間現(xiàn)在無法通過速侈。
class Solution {
public:
string longestPalindrome(string s) {
string res, temp;
int size = 0;
for(int i = 0; i < s.size(); i++)
{
if(s.size() - i <= size)
{
break;
}
for(int j = i; j < s.size(); j++)
{
temp +=s[j];
int tSize = isPalindrome(temp);
if(tSize > size)
{
res = temp;
size = tSize;
}
}
temp.clear();
}
return res;
}
int isPalindrome(string s)
{
int size = s.size();
for(int i = 0, j = size - 1; i <= j; i++, j--)
{
if(s[i] != s[j])
{
return -1;
}
}
return size;
}
};
之后看了官方題解，可以利用動態(tài)規(guī)劃的思想可以對暴力解進(jìn)行改進(jìn)迫卢∫邪幔看到該方法不禁感嘆，感覺打開了新世界的大門啊簡直是靖避。這題解也說明了潭枣，動態(tài)規(guī)劃其一目的是避免不必要的重復(fù)計算。
動態(tài)規(guī)劃采用了二維數(shù)組來表示子串的回文狀態(tài)幻捏，例如dp[i][j]表示字符串第i個字母到第j個字母組成的子串是否是回文，是則為true命咐，否則為false篡九。dp[i][j]是否為回文與dp[i+1][j-1]狀態(tài)有關(guān)，由此也可以推導(dǎo)出狀態(tài)轉(zhuǎn)移方程醋奠。而需先初始化一字母回文和二字母回文是為單數(shù)字符串和雙數(shù)字符串做鋪墊榛臼。
class Solution {
public:
string longestPalindrome(string s) {
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
int max = 1;
int fj = 0;
for(int i = 0; i < s.size(); i++) //初始化一字母和二字母回文
{
dp[i][i] = true;
if(i+1 != s.size())
{
if(s[i] == s[i+1])
{
dp[i][i+1] = true;
max = 2;
fj = i;
}
}
}
for(int i = 2; i < s.size(); i++) //輸出的矩陣應(yīng)為一個上三角矩陣
{
for(int j = 0; j < i-1; j++)
{
if(dp[j+1][i-1] && s[i] == s[j])
{
dp[j][i] = true;
int tempSize = i - j + 1;
if(tempSize > max)
{
max = tempSize;
fj = j;
}
}
}
}
return s.substr(fj, max);
}
因需遍歷一個上三角矩陣，故動態(tài)規(guī)劃方法的時間復(fù)雜度為O(n^2)窜司。
解決這個問題還有一個方法就是中心擴(kuò)展算法沛善，他是以一個或兩個字母為中心向兩邊進(jìn)行擴(kuò)展進(jìn)而判斷回文，該較為簡單塞祈，看官方題解即可金刁。
class Solution {
public:
string longestPalindrome(string s) {
int start = 0, end = 0;
int maxSize = 0;
string res;
for(int i = 0; i < s.size(); i++) //以每個字母為中心進(jìn)行遍歷
{
int len1 = expendCenter(s, i, i); //單數(shù)字符串長度回文判斷
int len2 = expendCenter(s, i, i+1);//雙數(shù)字符串長度回文判斷
int maxlen = max(len1, len2);
if(maxlen > maxSize)
{
maxSize = maxlen;
start = i - ((maxlen - 1) /2);
end = i + (maxlen/2);
}
}
for(int i = start; i <= end; i++)//此處可用string方法中substr代替
{
res += s[i];
}
return res;
}
int expendCenter(string s, int left, int right)
{
while(left >= 0 && right < s.size() && s[left] == s[right])
{
left--;
right++;
}
return right - left - 1;
}
};
時間復(fù)雜度O(n^2)。
53.最大子序和（easy）
用動態(tài)規(guī)劃思想定義一個概念议薪，f(k)表示以當(dāng)前元素結(jié)尾的子數(shù)組的最大值尤蛮，其實這f(k)里面包含了兩種狀態(tài)，一種是連續(xù)狀態(tài)斯议，一種是不連續(xù)狀態(tài)（即重新計算字?jǐn)?shù)組最大值）产捞，取這兩種狀態(tài)的最大值作為f(k)的值，故則f(k)應(yīng)該等于max(num[k],f(k-1)+num[k])哼御。代碼如下
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int dp_1 = nums[0];
int res = dp_1;
for(int i = 1; i < nums.size(); i++)
{
dp_1 = max(dp_1+nums[i], nums[i]);
res = max(dp_1,res);
}
return res;
}
};
62.不同路徑（medium）
由題意可以知道到達(dá)一個格子只有兩種路以可以選擇坯临，向下或者向右焊唬，由此我們可以得出dp[i][j] = dp[i-1][j] + dp[i][j-1],即到達(dá)坐標(biāo)為（i，j)格子的路徑數(shù)量等于到達(dá)坐標(biāo)（i-1看靠，j)(目標(biāo)各格子左邊的格子）的路徑數(shù)量加上到達(dá)坐標(biāo)（i赶促，j-1)(目標(biāo)各格子左邊的格子）的路徑數(shù)量。顯然第一行和第一列的路徑數(shù)量為1衷笋，所以需將網(wǎng)格到達(dá)第一行和第一列的路徑數(shù)量全部初始化為1芳杏。
class Solution {
public:
int uniquePaths(int m, int n) {
int steps[100][100] = {-1};
for(int i = 0; i < 100; i++)
{
steps[0][i] = 1;
steps[i][0] = 1;
}
for(int i = 1; i < m; i++)
{
for(int j = 1; j < n; j++)
{
steps[i][j] = steps[i-1][j] + steps[i][j-1]; //狀態(tài)轉(zhuǎn)移
}
}
return steps[m-1][n-1];
}
};
時間復(fù)雜度為O(n^2)。
63.不同路徑II(medium)
思路和不同路徑一樣辟宗，只不過注意處理一些特殊情況即可
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
long steps[100][100] = {0};
for(int i = 0; i < obstacleGrid.size(); i++)
{
if(obstacleGrid[i][0] == 1)
{
break;
}
steps[i][0] = 1;
}
for(int i = 0; i < obstacleGrid[0].size(); i++)
{
if(obstacleGrid[0][i] == 1)
{
break;
}
steps[0][i] = 1;
}
for(int i = 1; i < obstacleGrid.size(); i++)
{
for(int j = 1; j < obstacleGrid[0].size(); j++)
{
if(obstacleGrid[i][j] == 1)
{
continue;
}
if(obstacleGrid[i-1][j] == 1 && obstacleGrid[i][j-1] == 1)
{
steps[i][j] = 0;
}
if(obstacleGrid[i][j-1] == 1 && obstacleGrid[i-1][j] != 1)
{
steps[i][j] = steps[i-1][j];
}
if(obstacleGrid[i-1][j] ==1 && obstacleGrid[i][j-1] != 1)
{
steps[i][j] = steps[i][j-1];
}
if(obstacleGrid[i-1][j] == 0 && obstacleGrid[i][j-1] == 0)
{
steps[i][j] = steps[i-1][j] + steps[i][j-1];
}
}
}
return steps[obstacleGrid.size()-1][obstacleGrid[0].size()-1];
}
};
時間復(fù)雜度為O(M*N)爵赵。
64.最小路徑和（medium）
思路和前面兩道題差不多，只不過狀態(tài)轉(zhuǎn)移方程需要修改一下,該題的狀態(tài)轉(zhuǎn)移方程為grid[i][j] += min(grid[i-1][j], grid[i][j-1])泊脐，即坐標(biāo)(i,j)最小路徑等于坐標(biāo)（i-1空幻，j)和坐標(biāo)（i,j-1)中較小的值加上當(dāng)前網(wǎng)格的值。該題有個精選題解講的比較好容客，截圖記錄一下秕铛。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
for(int i = 1; i < grid.size(); i++)
{
grid[i][0] += grid[i-1][0];
}
for(int i = 1; i < grid[0].size(); i++)
{
grid[0][i] += grid[0][i-1];
}
for(int i = 1; i < grid.size(); i++)
{
for(int j = 1; j < grid[0].size(); j++)
{
grid[i][j] += grid[i-1][j] > grid[i][j-1] ? grid[i][j-1] : grid[i-1][j];
}
}
return grid[grid.size()-1][grid[0].size()-1];
}
};
時間復(fù)雜度為O(n^2)
91.解碼方法（medium）
因為一共有26個字母，對應(yīng)的編碼為126缩挑，所以有兩種解碼方法但两。第一種解碼方法是單個數(shù)字解碼為一個字母(19，0除外）供置，第二種是兩個數(shù)字組合一同解碼為一個字母(10~26）。所以求長度為n的編碼的解碼方法可以將其拆解為求長度為n-1的編碼的解碼方法（單個數(shù)字解碼）和長度為n-2的編碼方法（兩個數(shù)字組合解碼）芥丧。故狀體轉(zhuǎn)移方程dp[i] = dp[i-1]+dp[i-2]紧阔。當(dāng)然，針對一些邊界情況和特殊情況還得做一些處理续担，具體可以看代碼擅耽。該題可利用字符’1‘，’2‘物遇，’0‘巧妙去判斷邊界和數(shù)字組合情況乖仇，無需轉(zhuǎn)成整數(shù)在做相關(guān)判斷。
class Solution {
public:
int numDecodings(string s) {
if(s[0] == '0') return 0;
int ppre = 1, pre = 1; //n-2, n-1數(shù)量值挎挖，初始化為1
for(int i = 1; i < s.size(); i++)
{
int temp = pre;
if(s[i] == '0')//n為0
{
if(s[i-1] == '1' || s[i-1] == '2')//查看n-1是否是’1‘或’2‘这敬，不是則無法被解碼。是則為兩個數(shù)字組合解碼蕉朵。
{
pre = ppre;
}
else
{
return 0;
}
}
else
{
if((s[i-1] == '1') || (s[i-1] == '2' && (s[i]>'0' && s[i]<'7'))) //保證字符在可被解碼范圍內(nèi)
{
pre = pre + ppre;
}
}
ppre = temp;
}
return pre;
}
};
顯然崔涂，時間復(fù)雜度為O(n)。
96.不同的二叉搜索樹（medium）
該題官方題解寫的挺詳細(xì)的始衅，故直接搬運過來冷蚂。當(dāng)時看完題解真的是有茅塞頓開的感覺缭保，沒想到可以利用長度去做函數(shù)用于狀態(tài)轉(zhuǎn)換。
95.不同的二叉樹搜索樹II（medium）
這題其實思路和上面那道題是一樣的蝙茶，不過這題多了個需要構(gòu)建樹的步驟艺骂。在構(gòu)建樹的過程中注意，左子樹可以被重復(fù)利用隆夯，而右子樹則需復(fù)制后每個節(jié)點加上節(jié)點值即完成右子樹每個節(jié)點數(shù)值的偏移钳恕。
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
vector<vector<TreeNode*>> trees(n+1);
if(n!=0)
{
trees[0].emplace_back(static_cast<TreeNode*>(NULL));
trees[1].emplace_back(new TreeNode(1)) ;
}
for(int i = 2; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
for(TreeNode* leftTree : trees[j-1])
{
for(TreeNode* rightTree : trees[i-j])
{
TreeNode* root = new TreeNode(j);
root->left = leftTree;
root->right = cloneRightTree(j, rightTree);
trees[i].push_back(root);
}
}
}
}
return trees[n];
}
//選用遞歸的方式進(jìn)行樹的復(fù)制
TreeNode* cloneRightTree(int offset, TreeNode* original)
{
if(original == NULL)
{
return NULL;
}
TreeNode* clone = new TreeNode(original->val+offset);
if(original->left != NULL)
{
clone->left = cloneRightTree(offset, original->left);
}
if(original->right != NULL)
{
clone->right = cloneRightTree(offset, original->right);
}
return clone;
}
};
120.三角形最小三角路徑和（medium）
感覺這題狀態(tài)轉(zhuǎn)移方程挺容易看出來的。第i蹄衷，j點可以有兩種路徑到達(dá)忧额，故dp[i][j]表示三角矩陣總第i行第j個數(shù)，狀態(tài)轉(zhuǎn)移方程為dp[i][j] = min(dp[i-1][j-1]+dp[i][j], dp[i-1][j]+dp[i][j]),即選擇最小路徑為dp[i][j]的值愧口。該思路對三角形來說是自頂向下睦番，所以需做下邊界處理
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
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][0] + triangle[i][j];
}
else if(j == triangle[i].size()-1) //右邊界處理
{
triangle[i][j] = triangle[i-1][triangle[i-1].size()-1] + triangle[i][j];
}
else
{
triangle[i][j] = (triangle[i-1][j-1] + triangle[i][j]) < \
(triangle[i-1][j] + triangle[i][j]) ? \
(triangle[i-1][j-1] + triangle[i][j]) :
(triangle[i-1][j] + triangle[i][j]);
}
}
}
int min = 99999;
for(int i = 0; i < triangle[triangle.size()-1].size(); i++) //在最下方找出最小值
{
if(min > triangle[triangle.size()-1][i])
{
min = triangle[triangle.size()-1][i];
}
}
return min;
}
};
時間復(fù)雜度顯然O(n^2)。
139.單詞拆分（medium）
剛開始想到的是比較暴力的解法耍属，剛做的寫出來的時候還覺得用了動態(tài)規(guī)劃的思想托嚣，現(xiàn)在回看發(fā)現(xiàn)并沒有用到，只是單純的暴力解而已厚骗。這個暴力解思路是這樣的示启，先找出從字符串起始位置開始包含在字典里面的單詞，找到后便將其下標(biāo)數(shù)組置1表示其為第一次尋找到字典中的單詞下標(biāo)位置领舰。之后便開始遍歷下標(biāo)數(shù)組丑搔，當(dāng)尋找到下標(biāo)數(shù)組不為0的下標(biāo)位置i時，便從字符串中提取[i+1,n]范圍內(nèi)以i+1為起始下標(biāo)的連續(xù)的子串提揍，并逐次在字典中尋找是否有相同的子串。以此類推煮仇，當(dāng)下標(biāo)數(shù)組最后一位不為0時劳跃，則說明該字符串可以拆分，反之則不能浙垫。有點類似BFS的方法刨仑。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
vector<int> wordIndex(s.size(), 0);
string cmpstr = "";
for(int i = 0; i < s.size(); i++) //找出第一次字典中含有的單詞
{
cmpstr += s[i];
for(int j = 0; j < wordDict.size(); j++)
{
if(cmpstr.compare(wordDict[j]) == 0)
{
wordIndex[i] = 1;
}
}
}
for(int i = 0; i < wordIndex.size(); i++) //遍歷下標(biāo)數(shù)組
{
cmpstr = "";
if(wordIndex[i] != 0)
{
for(int j = i+1; j < s.size(); j++)//遍歷子串
{
cmpstr += s[j];
for(int k = 0; k < wordDict.size(); k++)//與字典中比對
{
if(cmpstr.compare(wordDict[k]) == 0)
{
if(j == wordIndex.size()-1)
{
return true;
}
wordIndex[j] = wordIndex[i]+1;
}
}
}
}
}
if(wordIndex[wordIndex.size()-1] != 0)
{
return true;
}
return false;
}
};
若使用動態(tài)規(guī)劃的思想則處理起來則相對比較簡單，當(dāng)時也是看了題解后才知道怎么才正確使用動態(tài)規(guī)劃去做夹姥。下面是動態(tài)規(guī)劃的官方題解杉武，講的比較詳細(xì)，也將其如何拆分子問題的思路寫了出來辙售。動態(tài)規(guī)劃給我的感覺就是逐個枚舉轻抱，往后遞推的過程。
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> works;
vector<bool> dp(s.size()+1, false);
dp[0] = true; //相當(dāng)于空字符串旦部，這個處理很妙祈搜，解決了子串全長檢查的問題
for(int i = 0; i < wordDict.size(); i++)
{
works.insert(wordDict[i]);
}
for(int i = 1; i <= s.size(); i++)
{
for(int j = 0; j < i; j++)
{
if(dp[j] && (works.find(s.substr(j, i-j)) != works.end())) //dp[j]表示（0较店，j),已經(jīng)在前面遍歷中檢查過，檢查j到i是否在字典中符合容燕，有則可拆分
{
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};
這題將字典可將字典中的單詞加進(jìn)哈希表中梁呈，哈希表查找的時間復(fù)雜度為O(1),此題解時間復(fù)雜度為O(n^2)。
152.乘積最大子序列（medium）
這個應(yīng)該還是比較容易想到思路的蘸秘，主要是正數(shù)乘負(fù)數(shù)官卡，負(fù)數(shù)乘正數(shù)時，最大會變最小醋虏，最小會變最大寻咒，所以要針對這個情況進(jìn)行處理。令imax為當(dāng)前最大值灰粮，則imax = max(imax * nums[i], nums[i]), 并且由于有上述情況出現(xiàn)仔涩，所以還要維護(hù)一個最小值的變量，并當(dāng)nums[i]是負(fù)數(shù)是粘舟，交換最大和最小值再進(jìn)行計算熔脂。
class Solution {
public:
int maxProduct(vector<int>& nums) {
int max = nums[0], imin = nums[0], imax = nums[0];
for(int i = 1; i < nums.size(); i++)
{
if(nums[i] < 0)
{
int sw = imax;
imax = imin;
imin = sw;
}
imax = imax*nums[i] > nums[i] ? imax*nums[i] : nums[i];
imin = imin*nums[i] < nums[i] ? imin*nums[i] : nums[i];
max = imax > max ? imax : max;
}
return max;
}
};
時間復(fù)雜度為O(n)
198.打家劫舍（easy）
當(dāng)小偷在第i間房間時，其實他有兩種狀態(tài)柑肴，偷或者不偷霞揉，當(dāng)他選擇偷時，他肯定沒有偷上一間房子晰骑，當(dāng)他選擇不偷時适秩，他當(dāng)前的錢和在上一間屋子時一樣，所以設(shè)f(k)為重前k個房屋中能搶到的最大數(shù)額硕舆，則狀態(tài)轉(zhuǎn)移方程為f(k) = max(f(k-1), f(k-2)+當(dāng)前屋子的錢）秽荞。
class Solution {
public:
int rob(vector<int>& nums) {
int preMax = 0; // k-2
int curMax = 0;// k-1
for(int num : nums)
{
int temp = curMax;
curMax = max(preMax+num, curMax);
preMax = temp;
}
return curMax;
}
};
時間復(fù)雜度為O(n)。
213.打家劫舍II(medium)
此題跟上一題不同之處在于抚官，其房屋是循環(huán)的扬跋，即首尾相連。我們可以從題意得知凌节，偷得了第一家就無法偷最后一家钦听，偷最后一家就無法偷第一家。所以當(dāng)我們偷第一家時倍奢，就將最后一家去掉朴上，此時得解法和上一題一模一樣。偷最后一家也同理可得卒煞。最后比較這兩種情況得大小選最優(yōu)的那個即可得出答案痪宰。
class Solution {
public:
int rob(vector<int>& nums) {
if(nums.size()==0) return 0;
if(nums.size()==1) return nums[0];
int maxs[4] = {0};
for(int i = 0; i < nums.size()-1; i++)
{
int temp = maxs[1];
maxs[1] = max(maxs[0]+nums[i], maxs[1]);
maxs[0] = temp;
}
for(int i = 1; i < nums.size(); i++)
{
int temp = maxs[3];
maxs[3] = max(maxs[2]+nums[i], maxs[3]);
maxs[2] = temp;
}
return max(maxs[1], maxs[3]);
}
};
時間復(fù)雜度為O(n)。
221.最大正方形(medium)
這道題剛開始選擇了滑動窗口這種比較暴力的解法,滑動窗口逐漸變大，并且在矩陣內(nèi)滑動并判斷是否為正方形酵镜。當(dāng)時根本沒有動態(tài)規(guī)劃做法的思路碉碉。
//滑動窗口暴力解法
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size()==0) return 0;
int minSize = matrix.size() < matrix[0].size() ? matrix.size() : matrix[0].size();
int flag;
int max = 0;
for(int i = 0; i < minSize; i++)
{
for(int j = 0; j+i < matrix.size(); j++)
{
for(int k = 0; k+i < matrix[0].size(); k++)
{
flag = 0;
for(int q = j; q <= j+i; q++)
{
for(int p = k; p <= k+i; p++)
{
if(matrix[q][p]!='1')
{
flag = 1;
break;
}
}
if(flag == 1)
{
break;
}
}
if(flag == 0 && i >= max)
{
max = i+1;
}
}
}
}
return max*max;
}
};
這題動態(tài)規(guī)劃我也不太懂怎么去將其解釋清楚，力扣里面有個題解講解的挺清楚的：https://leetcode-cn.com/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/淮韭。這個題解里面將狀態(tài)轉(zhuǎn)移方程解釋的比較清楚
若某格子值為 1 垢粮，則以此為右下角的正方形的、最大邊長為：上面的正方形靠粪、左面的正方形或左上的正方形中蜡吧，最小的那個，再加上此格占键。
而其圖解也清楚的解釋了取最小值的原因
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size()==0)return 0;
int col = matrix[0].size();
int pre = 0;
int max = 0;
vector<int> dp(col+1, 0);
for(int i = 0; i < matrix.size(); i++)
{
pre = 0;
for(int j = 1; j <= col; j++)
{
if(matrix[i][j-1] == '1')
{
int temp = dp[j];
dp[j] = min(min(dp[j-1], dp[j]), pre)+1;
pre = temp;
if(dp[j] > max)
{
max = dp[j];
}
}
else
{
dp[j] = 0;
}
}
}
return max*max;
}
};
時間復(fù)雜度為O(n^2)昔善。
264.丑數(shù)（medium)
這里先說下丑數(shù)的定義先，只包含質(zhì)因子2畔乙，3和5的數(shù)稱作丑數(shù)（Ugly Number）君仆。例如6是丑數(shù)，因為它可以分解成2*3牲距。由此定義我們可以知道位置在后面的丑數(shù)可以由位置在前的丑數(shù)得出（升序）返咱。一開始我得解法是將前一個丑數(shù)分別乘以2，3牍鞠，5咖摹，然后將其結(jié)果放入有序集合中，因為有序集合中得元素唯一且每次插入時會自動排序难述，故放入元素后選取最小的元素（即第一個元素）當(dāng)作第n個丑數(shù)萤晴。
class Solution {
public:
int nthUglyNumber(int n) {
set<long> uglyNums;
long nums[1691];
nums[1] = 1;
for(int i = 2; i <= n; i++)
{
long mulTwo = nums[i-1]*2;
long mulThree = nums[i-1]*3;
long mulFive = nums[i-1]*5;
uglyNums.insert({mulTwo, mulThree, mulFive});
auto it = uglyNums.begin();
nums[i] = *it;
uglyNums.erase(it);
}
return nums[n];
}
};
這個可以利用三指針進(jìn)一步去優(yōu)化，也是利用動態(tài)規(guī)劃的思想胁后，不過指針是否前進(jìn)跟當(dāng)前的丑數(shù)有關(guān)店读，該方法利用三指針做到了提前排序，實在是秒芭市尽两入！
class Solution {
public:
int nthUglyNumber(int n) {
long nums[1691] = {0};
nums[1] = {1};
int p2 = 1, p3 = 1, p5 = 1;
for(int i = 2; i <= n; i++)
{
nums[i] = min(nums[p2]*2,min(nums[p3]*3, nums[p5]*5));
if(nums[i] == nums[p2]*2) p2++;
if(nums[i] == nums[p3]*3) p3++;
if(nums[i] == nums[p5]*5) p5++;
}
return nums[n];
}
};
時間復(fù)雜度為O(n^2)
279.完全平方數(shù)（medium）
該題比較簡單，思路也比較容易想到敲才。設(shè)f(n)表示湊成n需要完全平方數(shù)的最小個數(shù)，所以可以得出狀態(tài)轉(zhuǎn)移方程為f(n) = min({f(n-完全平方數(shù)}）+ 1择葡。
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n+1, 0);
dp[1] = 1;
for(int i = 2; i <= n; i++)
{
int Min = 99999;
for(int j = 1; i-j*j >= 0; j++)
{
Min = min(dp[i-j*j], Min);
}
dp[i] = Min + 1;
}
return dp[n];
}
};
時間復(fù)雜度O(n^2)
300.最長上升子序列（medium）
這個應(yīng)該算是比較經(jīng)典動態(tài)規(guī)劃的題目了紧武，剛開始學(xué)習(xí)動態(tài)規(guī)劃的時侯網(wǎng)上那些博客，答案都是用它來舉例的敏储，可是當(dāng)我真正上手做這道題的時候還真的沒想出來阻星。其實現(xiàn)在回想一下也不算太復(fù)雜，力扣中krahets的題解對此題講解的比較清楚。
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if(nums.size() == 0) return 0;
vector<int> dp(nums.size(), 1);
int Max = 1;
for(int i = 1; i < nums.size(); i++)
{
for(int j = 0; j < i; j++)
{
if(nums[i] > nums[j])
{
dp[i] = max(dp[i], dp[j]+1);
}
}
if(dp[i] > Max)
{
Max = dp[i];
}
}
return Max;
}
};
時間復(fù)雜度為O(n^2)妥箕。
304.二維區(qū)域和檢索-矩陣不可變（medium）
求矩陣中子矩陣的面積滥酥，我們定義dp[i][j]為左上角(0,0)到(i,j)的面積，所以（row1, clo1)到(row2,col2)的面積為S = dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1]畦幢。
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix)
{
if(matrix.size() == 0) return;
dp = vector<vector<int>>(matrix.size()+1, vector<int>(matrix[0].size()+1, 0));
for(int i = 0; i < matrix.size(); i++)
{
for(int j = 0; j < matrix[0].size(); j++)
{
dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] + matrix[i][j] - dp[i][j];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int res = dp[row2+1][col2+1] - dp[row1][col2+1] - dp[row2+1][col1] + dp[row1][col1];
return res;
}
vector<vector<int>> dp;
};
309.最佳買賣股票時機(jī)含冷凍期(medium)
這題我覺得是最能體現(xiàn)動態(tài)規(guī)劃中狀態(tài)這一概念的題了坎吻，力扣中l(wèi)abuladong的題解對這個題的狀態(tài)講的十分清楚，直接參考題解并加以思考即可感受到動態(tài)規(guī)劃的妙處所在宇葱。
labuladong最佳買賣股票時機(jī)的題解
class Solution {
public:
int maxProfit(vector<int>& prices) {
int dp_i_0 = 0, dp_i_1 = INT_MIN, dp_pre_0 = 0; //相當(dāng)于第0天
for(int i = 0; i < prices.size(); i++)
{
int temp = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1+prices[i]);
dp_i_1 = max(dp_i_1, dp_pre_0-prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
}
};
時間復(fù)雜度O(n^2)
小結(jié)
回頭看了總結(jié)下做過的關(guān)于動態(tài)規(guī)劃的題瘦真，覺得動態(tài)規(guī)劃還是個挺有趣的思想∈蚯疲可能這東西聽起來感覺挺復(fù)雜的诸尽，但其實動態(tài)規(guī)劃就是一個窮舉的過程，將所以可能列舉出來印颤，從中選擇最優(yōu)您机。最關(guān)鍵一步還是在于狀態(tài)的選取和其轉(zhuǎn)移方程，搞定這兩步年局，接下來的問題也就迎刃而解了际看。所以動態(tài)規(guī)劃問題主要有這幾步：
1、拆分問題某宪，確定狀態(tài)仿村，并用代碼的形式表示狀態(tài)
2混移、確定狀態(tài)轉(zhuǎn)移方程
3淹办、求解問題。
求解動態(tài)規(guī)劃問題步驟也可以參考一下該問題下王焱的題解映凳。
該文章中圖片均來自于力扣題解中衣迷，若有侵權(quán)請聯(lián)系本人刪除
