【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]; }