第一章-動态規劃
動态規劃求解模式
動态規劃具備了一下三個特點：
1、把原來的問題分解成了幾個相似子問題
2、所有的子問題隻需要解決一次
3、儲存子問題的解
從以下四個角度考慮：
1、初始狀态定義
2、狀态間轉移方程
3、狀态的初始化
4、傳回結果
解決問題主要适用于：查找最優解，最大值/最小值，可不可行，是不是，方案個數
例1 斐波那契數列
牛客網:
https://www.nowcoder.com/questionTerminal/c6c7742f5ba7442aada113136ddea0c3
動态規劃解法
class Solution {
public:
int Fibonacci(int n) {
vector<int> ret(n + 1, 0);
//初始狀态
ret[1] = ret[2] = 1;
//遞推公式
//ret[i] = ret [i - 1] + ret[i - 2];
for(int i = 3; i <= n; i++)
{
ret[i] = ret[i - 1] + ret[i - 2];
}
return ret[n];
}
};
例2 變态青蛙跳台階
牛客網：
https://www.nowcoder.com/questionTerminal/22243d016f6b47f2a6928b4313c85387
問題分析
定義狀态
跳上i級台階的方法數
狀态轉移方程
分解：
一次跳1級台階：1， F(i - 1)
一次跳2級台階：2， F(i - 2)
…
推得狀态轉移方程：
F(i) = F(i - 1) + F(i - 2) + … + F(1)
F(i - 1) = F(i - 2) + F(i - 3) + … + F(1)
F(i) = F(i - 1) + F(i - 1) = 2 * F(i - 1);
初始狀态和最終狀态
F(1) = 1,求F(n)。
實作
class Solution {
public:
int jumpFloorII(int number) {
//初始狀态
int f1 = 1;
//狀态轉移方程：F(i) = 2 * F(i - 1)
for(int i = 2; i <= number; i++)
{
f1 = 2 * f1;
}
return f1;
}
};
優化
根據狀态轉移方程我們可以得知，
F(n) = 2 ^ (n - 1)
;是以可以得到優化：
class Solution {
public:
int jumpFloorII(int number) {
return (1 << (number - 1));
}
};
例3 求連續最大子數組的和
牛客網：
https://www.nowcoder.com/questionTerminal/459bd355da1549fa8a49e350bf3df484
分析
定義狀态
到此項為止前i項的連續子序列的最大和
狀态轉移方程
F(i) = max(F(i - 1) + a[i], a[i]);
初始狀态和最終狀态
初始狀态F[0] = a[0]。
最終結果max(F[i])。
實作
class Solution {
public:
int FindGreatestSumOfSubArray(vector<int> array) {
if(array.empty())
{
return 0;
}
vector<int> ret(array.size(), 0);
//初始狀态
ret[0] = array[0];
//狀态轉移
for(int i = 1; i < array.size(); i++)
{
ret[i] = max(array[i] + ret[i - 1], array[i]);
}
//求max(F[i])
int maxNum = ret[0];
for(int i = 0; i < ret.size(); i++)
{
maxNum = max(maxNum, ret[i]);
}
return maxNum;
}
};
例4 word-break(字元串分割)
牛客網：
https://www.nowcoder.com/questionTerminal/5f3b7bf611764c8ba7868f3ed40d6b2c
分析
定義狀态
F(i)：前i個字元能否被分割。
狀态轉移方程
F(i): F(i)能否被分割取決于前j項能否被分割和j + 1到第i項能否被分割。（此處j取0 ~ i - 1）
得遞推方程F(i) : F(j) && (j + 1 ~ i)能否被分割
初始狀态和最終狀态
初始狀态：F(0) = true。
最終狀态F(n)。
實作
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
if(s.empty() || dict.empty())
{
return false;
}
vector<bool> Fn(s.size() + 1, false);
//初始狀态
Fn[0] = true;
for(int i = 1; i <= s.size(); i++)
{
//狀态轉移
//F(i) = F(j) && (j + 1 ~ i), (0 <= j < i)能否被分割
for(int j = i - 1; j >= 0; j--)
{
if(Fn[j] && dict.find(s.substr(j, i - j)) != dict.end())
{
Fn[i] = true;
break;
}
}
}
//最終狀态
return Fn[s.size()];
}
};
例5 triangle(三角矩陣最短路)
牛客網：
https://www.nowcoder.com/questionTerminal/2b7995aa4f7949d99674d975489cb7da
分析
定義狀态
F[i][j]: 從(0, 0)到(i, j)的最短路徑和。
狀态轉移方程
一般情況下，走到每個位置的最短路徑都可以看作是上一行相鄰兩個位置的最短路徑+這個位置的路徑長度，數學描述：F[i][j]:min(F[i - 1][j], F[i - 1][j - 1]) + a[i][j]。
但要考慮邊界狀态：當在矩陣邊緣時隻有一種選擇的情況，即F[i][0] = F[i - 1][0];F[i][i] = F[i - 1][i - 1]。
初始狀态和最終狀态
初始狀态：F[0][0] = a[0][0]。
最終狀态：min(F[n - 1][j])，即最後一行中的最小值。
實作
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
if(triangle.empty())
{
return 0;
}
//初始狀态
vector<vector<int>> ret(triangle);
//狀态轉移
int row = ret.size();
for(int i = 1; i < row; ++i)
{
ret[i][0] = ret[i - 1][0] + triangle[i][0];
}
for(int i = 1; i < row; ++i)
{
ret[i][i] = ret[i - 1][i - 1] + triangle[i][i];
}
for(int i = 1; i < row; ++i)
{
for(int j = 1; j < i; ++j)
{
ret[i][j] = min(ret[i - 1][j], ret[i - 1][j - 1]) + triangle[i][j];
}
}
//最終狀态
int minSum = ret[row - 1][0];
for(int i = 1; i < row; i++)
{
minSum = min(minSum, ret[row - 1][i]);
}
return minSum;
}
};
例6 求路徑數量
牛客網：
https://www.nowcoder.com/questionTerminal/3cdf08dd4e974260921b712f0a5c8752
分析
狀态定義
F[i][j]：從左上角到達下标(i, j)的路徑總數
狀态轉移方程
if(a[i][j] == 1) F[i][j] = 0;
if(a[i][j] == 0) F[i][j] = F[i][j - 1] + F[i - 1][j]。
初始狀态和最終狀态
初始狀态：如果第一行第一列有障礙物表示這條路走不通則路徑數置0，否則隻有一條路徑，置一if(a[0][j]) == 1) F[0][j] = 0，if(a[i][0] == 1) F[i][0] = 0，這種情況下這條路走不通。
最終狀态：F[i][j]。
實作
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int> > &obstacleGrid) {
if(obstacleGrid.empty())
{
return 0;
}
if(obstacleGrid[0][0] == 1)
{
return 0;
}
int row = obstacleGrid.size();
int col = obstacleGrid[0].size();
vector<vector<int>> pathNum(row, vector<int>(col, 0));
for(int i = 0; i < row; i++)
{
if(obstacleGrid[i][0] == 1)
{
break;
}
else
{
pathNum[i][0] = 1;
}
}
for(int i = 0; i < col; i++)
{
if(obstacleGrid[0][i] == 1)
{
break;
}
else
{
pathNum[0][i] = 1;
}
}
for(int i = 1; i < row; i++)
{
for(int j = 1; j < col; j++)
{
if(obstacleGrid[i][j] == 1)
{
pathNum[i][j] = 0;
}
else
{
pathNum[i][j] = pathNum[i][j - 1] + pathNum[i - 1][j];
}
}
}
return pathNum[row - 1][col - 1];
}
};
例7 背包問題
lintcode：
https://www.lintcode.com/problem/backpack-ii/description
分析
背包問題是一類問題，主要是求解限制條件下的最優解問題。
狀态定義
F[i][j]：前i個商品，包的重量為j的最大價值。定義二維數組周遊所有商品，和到目前商品情況下背包容量從0 - max的所有情況下的最大值求解，周遊到最後則可得到n個全部商品情況下背包最大容量max下背包可拿的最大價值F[n][max]。
狀态轉移方程
目前商品空間大于包能承受的總空間，放不下直接跳過。數學描述：if(w[i] > j) F[i][j] = F[i - 1][j]。
目前商品空間小于等于包能承受總空間，可以選擇放可以選擇不放，如果不放入，則F[i][j] = F[i - 1][j]；如果放入，則目前重量等于周遊到的上一個商品并且空間還有w[i]這麼大的時候的價值+本商品的價值，最大價值F[i][j] = F[i - 1][j - w[i]] + v[i]，選擇放入或不放入商品情況中的最大值作為最優解。數學描述：if(w[i] <= j) max(F[i - 1][j], F[i - 1][j - w[i]] + v[i]);
初始狀态和最終狀态
初始狀态：沒有商品時，F[0][j] = 0,最大容量為0時F[i][0] = 0。
最終狀态：周遊完全部n個商品，并且背包總容量為最大值m時得到最大價值F[n][m]。
實作
class Solution {
public:
/**
* @param m: An integer m denotes the size of a backpack
* @param A: Given n items with size A[i]
* @param V: Given n items with value V[i]
* @return: The maximum value
*/
int backPackII(int m, vector<int> &A, vector<int> &V) {
if(A.empty())
{
return 0;
}
int row = A.size();
vector<vector<int>> maxValue(row + 1, vector<int>(m + 1, 0));
for(int i = 1; i <= row; ++i)
{
for(int j = 1; j <= m; ++j)
{
if(A[i - 1] > j)
{
maxValue[i][j] = maxValue[i - 1][j];
}
else
{
maxValue[i][j] = max(maxValue[i - 1][j], maxValue[i - 1][j - A[i - 1]] + V[i - 1]);
}
}
}
return maxValue[row][m];
}
};
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)