前言
大家好，我是jiantaoyab，開始刷動態(tài)規(guī)劃的題目了，要特別注意初始化的時候給什么值。
動態(tài)規(guī)劃5個步驟
- 狀態(tài)表示 ：dp數(shù)組中每一個下標(biāo)對應(yīng)值的含義是什么->dp[i]表示什么
- 狀態(tài)轉(zhuǎn)移方程： dp[i] 等于什么
- 1 和 2 是動態(tài)規(guī)劃的核心步驟，第三步是初始化，保證填表的時候不越界
- 填表順序：為了保證填寫當(dāng)前狀態(tài)的時候，所需要的狀態(tài)已經(jīng)計算過
- 返回值
第 N 個泰波那契數(shù)
題目分析
我們用動態(tài)規(guī)劃來解決
- dp[i] : 表示第i個泰波那契數(shù)
- dp[i] = dp[i - 3] + dp[i - 2] + dp [i - 1]
- 初始化： dp[0] = 0; dp[1] = 1 ; dp[2] = 1;
- 填表順序：從左道右
- 返回值：dp[n]
代碼文章來源地址http://www.zghlxwxcb.cn/news/detail-850417.html
class Solution {
public:
int tribonacci(int n) {
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int dp[1000] = {0};
dp[0] = 0, dp[1] = 1, dp[2] = 1;
for(int i = 3; i <= n; i++)
{
dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
}
return dp[n];
}
};
優(yōu)化一下，可以看到只需要三個變量也能完成這個操作。
class Solution {
public:
int tribonacci(int n) {
if(n == 0) return 0;
if(n == 1 || n == 2) return 1;
int a = 0, b = 1, c = 1, d = 0;
for(int i = 3; i <= n; i++)
{
d = a + b + c;
a = b;
b = c;
c = d;
}
return d;
}
};
三步問題
題目分析
- dp[i] :表示去到當(dāng)前臺階有幾種方法
- dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
- 初始化 dp[1] = 1; dp[2] = 2; dp[3] = 4;
- 填表順序從左到右
- 返回值 d[n]
代碼
class Solution {
public:
int waysToStep(int n) {
vector<int>dp(n + 1);
if(n == 1 || n == 2) return n;
if(n == 3) return 4;
const int MOD = 1000000007;
dp[1] = 1; dp[2] = 2; dp[3] = 4;
for(int i = 4; i <= n; i++)
{
dp[i] = ((dp[i-3] + dp[i-2]) % MOD + dp[i-1]) % MOD;
}
return dp[n];
}
};
使用最小花費爬樓梯
題目分析
- dp[i]：到達 i位置的最小花費
- dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
- 初始化：dp[0] = dp[1] = 0;
- 填表順序:從左到右
- 返回值：dp[n]
代碼
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
vector<int> dp(n + 1);
dp[0] = dp[1] = 0;
for(int i = 2; i <= n; i++)
{
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]);
}
return dp[n];
}
};
解碼方法
題目分析
- dp[i]：是表示是 i 位置為結(jié)尾的解碼方法總數(shù)
- dp[i] = dp[i - 1] + dp [i - 2];
- 初始化：dp[0] = 0 / 1 dp[1] = 0/ 1/ 2
- 填表順序:從左到右
- 返回值：dp[n - 1]
代碼
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<int> dp (n);
//初始化
dp[0] = s[0] != '0';
if(n == 1) return dp[0];
if(s[0] != '0' && s[1] != '0') dp[1] += 1;
int tmp = (s[0] - '0') * 10 + (s[1] - '0');
if(tmp >= 10 && tmp <= 26) dp[1] += 1;
//處理剩下的
for(int i = 2; i < n; i++)
{
//單獨一個字符
if(s[i] != '0') dp[i] += dp[i - 1];
//2個字符
int tmp = (s[i - 1] - '0') * 10 + (s[i] - '0');
if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
}
return dp[n - 1];
}
};
優(yōu)化代碼
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<int> dp (n + 1);
//初始化
dp[0] = 1;
dp[1] = s[1 - 1] != '0';
//處理剩下的
for(int i = 2; i <= n; i++)
{
//單獨一個字符
if(s[i - 1] != '0') dp[i] += dp[i - 1];
//2個字符
int tmp = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
if(tmp >= 10 && tmp <= 26) dp[i] += dp[i - 2];
}
return dp[n];
}
};
不同路徑
題目分析
- dp[i] [j]：走到 i,j 位置有多少種方式
- dp[i] [j] = dp[i] [j - 1] + dp[i - 1] [j];
- 初始化：新增加一列和一行
- 填表順序:從上到下，左到右填表
- 返回值：dp[m] [n]
代碼
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m+1, vector<int>(n+1));
//初始化
dp[0][1] = 1;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
}
}
return dp[m][n];
}
};
不同路徑 II
題目分析
- dp [i] [j] : 到達i,j這個位置有多少種方法
- dp [i] [j] = dp[i - 1] [j] + dp [i] [j - 1]
- 初始化：dp[1] [0] = 1;
- 填表順序：從上到下，從左到右
- 返回值： dp[m] [n]
代碼
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size(), n = obstacleGrid[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//初始化
dp[1][0] = 1;
for(int i = 1; i <= m; i++)
{
for(int j = 1; j <= n; j++)
{
if(obstacleGrid[i - 1][j - 1] != 1)
dp[i][j] = dp[i - 1][j] + dp[i][j -1];
}
}
return dp[m][n];
}
};
珠寶的最高價值
題目分析
- dp [i] [j] : 到達i,j這個位置的最高價值
- dp [i] [j] =max(dp[i-1] [j], dp[i] [j-1]) + frame[i-1] [j-1];
- 初始化：默認都是0不用初始化
- 填表順序：從上到下，從左到右
- 返回值： dp[m] [n]
代碼
class Solution {
public:
int jewelleryValue(vector<vector<int>>& frame) {
int m = frame.size(), n = frame[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i-1][j-1];
}
return dp[m][n];
}
};
下降路徑最小和
題目分析
- dp[i] [j] : 到達i,j位置的最小下路徑
- dp[i] [j] : min(dp[i+1] [j-1], dp[i+1] [j+1], dp[i+1] [j]) + matrix[i-1] [j - 1]
- 初始化：多給1行 和2列
- 填表順序：從上到下，從左到右
- 返回值： 最后一行的最小值
代碼
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
for(int j = 0; j < n + 2; j++) dp[0][j] = 0;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
dp[i][j] = min(min(dp[i-1][j-1], dp[i-1][j]), dp[i-1][j+1]) + matrix[i-1][j-1];
}
}
//返回值
int ret = INT_MAX;
for(int j = 1; j <= n; j++)
{
ret = min(ret, dp[n][j]);
}
return ret;
}
};
最小路徑和
代碼
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
dp[1][0] = dp[0][1] = 0;
for(int i = 1; i <= m; i++)
for(int j = 1; j <= n; j++)
{
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
}
return dp[m][n];
}
};
地下城游戲（反著來）
題目分析
-
dp[i] [j] : 從i，j位置出發(fā)，到達終點所需要的最低
-
dp[i] [j] = min(dp[i] [j + 1], dp[i + 1] [j]) - dungeon[i] [j];
-
初始化 dp[m +1] [n -1] = dp [m - 1] [n + 1] = 1;
-
填表順序：從下到上，從右到左
-
返回值： dp[0] [0]文章來源：http://www.zghlxwxcb.cn/news/detail-850417.html
代碼
class Solution {
public:
int calculateMinimumHP(vector<vector<int>>& dungeon) {
int m = dungeon.size(), n = dungeon[0].size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
//初始化
dp[m][n -1] = dp [m - 1][n] = 1;
for(int i = m - 1; i >= 0; i--)
for(int j = n - 1; j >= 0; j--)
{
dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
dp[i][j] = max(1, dp[i][j]); //如果血包很大，會出現(xiàn)負數(shù)，這里取1就是最低血
}
return dp[0][0];
}
};
到了這里，關(guān)于刷題之動態(tài)規(guī)劃-路徑問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
