【C++刷题】优选算法——动态规划第一辑

1.状态表示是什么？简答理解是dp表里的值所表示的含义怎么来的？题目要求经验+题目要求分析问题的过程中，发现重复子问题
2.状态转移方程dp[i]=......细节问题：3.初始化控制填表的时候不越界4.填表顺序控制在填写当前状态的时候，所需要的状态已经填写好了5.返回值题目要求+状态表示空间优化滚动数组

第 N 个泰波那契数

int tribonacci(int n)
{// 处理一些边界情况if(n < 3){if(n == 0) return 0;else return 1;}// 1.创建dp表vector<int> dp(n + 1);// 2.初始化dp[0] = 0, dp[1] = 1, dp[2] = 1;for(int i = 3; i <= n; ++i){// 3.填表dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];}// 4.返回值return dp[n];
}
// 空间优化版本
int tribonacci(int n)
{int arr[3] = { 0,1,1 };if(n < 3) return arr[n];int ret = 0;for(int i = 3; i <= n; ++i){ret = arr[0] + arr[1] + arr[2];arr[0] = arr[1], arr[1] = arr[2], arr[2] = ret;}return ret;
}

三步问题

状态表示:经验+题目要求：以i位置为结尾来入手dp[i]: 表示到达i位置，一共有多少种方法
状态转移方程:基于i位置状态，跨一步到i位置，来划分问题

int waysToStep(int n)
{if(1 == n) return 1;else if(2 == n) return 2;else if(3 == n) return 4;// 1.dp数组vector<int> dp(n + 1);// 2.初始化dp[1] = 1, dp[2] = 2, dp[3] = 4;for(int i = 4; i <= n; ++i){// 3.状态方程dp[i] = ((dp[i - 1] + dp[i - 2]) % 1000000007 + dp[i - 3]) % 1000000007;}// 4.返回值return dp[n];
}

使用最小花费爬楼梯

状态表示:经验+题目要求：以i位置为结尾来入手dp[i]: 表示i位置到下一步的最小花费
状态转移方程:dp[i] = min(dp[i-1], dp[i-2]) + cost[i]

int minCostClimbingStairs(vector<int>& cost)
{// 1.dp数组vector<int> dp(cost.size());// 2.初始化dp[0] = cost[0]; dp[1] = cost[1];for (int i = 2; i < dp.size(); ++i){// 3.状态转移方程dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];}// 4.返回值return min(dp[dp.size() - 1], dp[dp.size() - 2]);
}

解码方法

状态表示:经验+题目要求：以i位置为结尾来入手dp[i]: 表示以i位置为结尾时，解码方法的总数
状态转移方程:

在这里插入图片描述

int numDecodings(string s)
{// 0.边界情况if(s.size() < 2){if(s[0] == '0') return 0;else return 1;}// 1.dp数组vector<int> dp(s.size(), 0);// 2.初始化if (s[0] == '0') dp[0] = 0;else dp[0] = 1;if (s[0] != '0' && s[1] != '0') dp[1] += 1;if (10 <= stoi(s.substr(0, 2)) && stoi(s.substr(0, 2)) <= 26) dp[1] += 1;for(int i = 2; i < dp.size(); ++i){// 3.状态转移方程int num1 =0, num2 = 0;if(s[i] != '0') num1 = dp[i - 1];if(10 <= stoi(s.substr(i - 1, 2)) && stoi(s.substr(i - 1, 2)) <= 26) num2 = dp[i - 2];dp[i] = num1 + num2;}// 4.返回值return dp.back();
}

不同路径

状态表示:经验+题目要求：以[i,j]位置为结尾来入手dp[i][j]: 表示以[i,j]位置为finish时，从start出发的不同路径数
状态转移方程:dp[i][j] = dp[i-1][j] + dp[i][j-1]

int uniquePaths(int m, int n)
{// 1.dp数组vector<vector<int>> dp(m, vector<int>(n));// 2.初始化for (int i = 0; i < m; ++i){dp[i][0] = 1;}for (int i = 0; i < n; ++i){dp[0][i] = 1;}// 3.状态转移方程for (int row = 1; row < m; ++row){for (int col = 1; col < n; ++col){dp[row][col] = dp[row - 1][col] + dp[row][col - 1];}}// 4.返回值return dp.back().back();
}

不同路径 II

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
{// 1.dp数组int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> dp(m, vector<int>(n));// 2.初始化for(int i = 0; i < m; ++i){if(obstacleGrid[i][0] == 1)break;dp[i][0] = 1;}for(int i = 0; i < n; ++i){if(obstacleGrid[0][i] == 1)break;dp[0][i] = 1;}// 3.状态转移方程for(int row = 1; row < m; ++row){for(int col = 1; col < n; ++col){if(obstacleGrid[row][col] == 1)continue;dp[row][col] = dp[row - 1][col] + dp[row][col - 1];}}// 4.返回值return dp.back().back();
}

珠宝的最高价值

状态表示:经验+题目要求：以[i,j]位置为结尾来入手dp[i][j]: 表示到达[i,j]位置时所能得到的的最大价值
状态转移方程:dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + frame[i][j]

int jewelleryValue(vector<vector<int>>& frame)
{// 1.dp数组int row = frame.size();int col = frame[0].size();vector<vector<int>> dp(row, vector<int>(col));// 2.初始化dp[0][0] = frame[0][0];for(int i = 1; i < col; ++i){dp[0][i] = dp[0][i - 1] + frame[0][i];}for(int i = 1; i < row; ++i){dp[i][0] = dp[i - 1][0] + frame[i][0];}// 3.状态转移方程for(int i = 1; i < row; ++i){for(int j = 1; j < col; ++j){dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j];}}// 4.返回值return dp.back().back();
}

下降路径最小和

状态表示:经验+题目要求：以[i,j]位置为结尾来入手dp[i][j]: 表示到达[i,j]位置时所得到的最小下降路径和
状态转移方程:dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + frame[i][j]

    int minFallingPathSum(vector<vector<int>>& matrix){// 1.dp数组int n = matrix.size();vector<vector<int>> dp(n, vector<int>(n));// 2.初始化for(int i = 0; i < n; ++i){dp[0][i] = matrix[0][i];}// 3.状态转移方程for(int i = 1; i < n; ++i){for(int j = 0; j < n; ++j){if(j == 0){dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + matrix[i][j];}else if(j == n - 1){dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + matrix[i][j];}else{dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i][j];}}}// 4.返回值int min_sum = dp[n - 1][0];for(int i = 1; i < n; ++i){if(dp[n - 1][i] < min_sum) min_sum = dp[n - 1][i];}return min_sum;}

最小路径和

状态表示:经验+题目要求：以[i,j]位置为结尾来入手dp[i][j]: 表示到达[i,j]位置时所得到的最小路径和
状态转移方程:dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

int minPathSum(vector<vector<int>>& grid)
{// 1.dp数组int m = grid.size();int n = grid[0].size();vector<vector<int>> dp(m, vector<int>(n));// 2.初始化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 i = 1; i < n; ++i){dp[0][i] = dp[0][i - 1] + grid[0][i];}// 3.状态转移方程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];}}// 4.返回值return dp.back().back();
}

地下城游戏

状态表示:经验+题目要求：以[i,j]位置为起点来入手dp[i][j]: 表示从[i,j]位置出发，到达终点，所需的最低初始健康点数
状态转移方程:dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]); // 细节处理，健康点数至少为1才能存活

int calculateMinimumHP(vector<vector<int>>& dungeon)
{// 1.dp数组int m = dungeon.size();int n = dungeon[0].size();vector<vector<int>> dp(m, vector<int>(n));// 2.初始化if(dungeon[m - 1][n - 1] < 0) dp[m - 1][n - 1] = 1 - dungeon[m - 1][n - 1];else dp[m - 1][n - 1] = 1;for(int i = n - 2; i >= 0; --i){dp[m - 1][i] = dp[m - 1][i + 1] - dungeon[m - 1][i];dp[m - 1][i] = max(1, dp[m - 1][i]);}for(int i = m - 2; i >= 0; --i){dp[i][n - 1] = dp[i + 1][n - 1] - dungeon[i][n - 1];dp[i][n - 1] = max(1, dp[i][n - 1]);}// 3.状态转移方程for(int i = m - 2; i >= 0; --i){for(int j = n - 2; j >= 0; --j){dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];dp[i][j] = max(1, dp[i][j]);}}// 4.返回值return dp[0][0];
}