动态规划
Dynamic Programming
简写为 DP,是运筹学的一个分支,是求解决策过程最优化的过程。20世纪50年代初,美国数学家贝尔曼(R.Bellman)等人在研究多阶段决策过程的优化问题时,提出了著名的最优化原理,从而创立了动态规划。动态规划的应用极其广泛,包括工程技术、经济、工业生产、军事以及自动化控制等领域,并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
动态规划算法的基本步骤包括:
- 确定状态:确定需要求解的状态,并将其表示为变量。
- 确定状态转移方程:根据问题的特定约束条件和目标函数,确定状态之间的转移关系,并将其表示为数学公式。
- 初始化:为初始状态赋初值,并将其表示为初始条件。
- 递推计算:根据状态转移方程,使用循环依次计算各个状态的解,并将其保存在数组或表中。
- 求解最终结果:根据问题的目标,从计算得到的解中得出最终结果。
动态规划算法可以用于解决各种问题,例如最短路径问题、背包问题、最长公共子序列问题等。在实现动态规划算法时,需要根据具体问题的特点进行设计和调整,以确保算法的正确性和效率。
适用条件
任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
最优化原理(最优子结构性质)
最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质 [8] 。
无后效性
将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性 [8] 。
子问题的重叠性
动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其他的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间。
真题举例(1)
44. 通配符匹配
给定一个字符串 (s
) 和一个字符模式 (p
) ,实现一个支持 '?'
和 '*'
的通配符匹配。
'?' 可以匹配任何单个字符。'*' 可以匹配任意字符串(包括空字符串)。
两个字符串完全匹配才算匹配成功。
说明:
s
可能为空,且只包含从a-z
的小写字母。p
可能为空,且只包含从a-z
的小写字母,以及字符?
和*
。
示例 1:
输入:s = "aa" p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入:s = "aa" p = "*"
输出: true
解释: '*' 可以匹配任意字符串。
示例 3:
输入:s = "cb" p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。
示例 4:
输入:s = "adceb" p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".
示例 5:
输入:s = "acdcb" p = "a*c?b"
输出: false
代码1:
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isMatch(string s, string p) { vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1)); dp[0][0] = 1; for (int j = 1; j <= p.size(); j++) { dp[0][j] = dp[0][j - 1] && p[j - 1] == '*'; } for (int i = 1; i <= s.size(); i++) { for (int j = 1; j <= p.size(); j++) { if (p[j - 1] == '*') { dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } else { dp[i][j] = (s[i - 1] == p[j - 1] || p[j - 1] == '?') && dp[i - 1][j - 1]; } } } return dp[s.size()][p.size()]; } }; int main() { Solution s; cout << s.isMatch("aa", "a") << endl; cout << s.isMatch("aa", "*") << endl; cout << s.isMatch("cb", "?a") << endl; cout << s.isMatch("adceb", "*a*b") << endl; cout << s.isMatch("acdcb", "a*c?b") << endl; return 0; }
代码2:
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isMatch(string s, string p) { int m = s.size(); int n = p.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1)); dp[0][0] = true; for (int i = 1; i <= n; i++) { if (p[i - 1] == '*') dp[0][i] = true; else break; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (p[j - 1] == '*') { dp[i][j] |= dp[i][j - 1]; dp[i][j] |= dp[i - 1][j]; } else { if (p[j - 1] == '?' || s[i - 1] == p[j - 1]) { dp[i][j] |= dp[i - 1][j - 1]; } } } } return dp[m][n]; } }; int main() { Solution s; cout << s.isMatch("aa", "a") << endl; cout << s.isMatch("aa", "*") << endl; cout << s.isMatch("cb", "?a") << endl; cout << s.isMatch("adceb", "*a*b") << endl; cout << s.isMatch("acdcb", "a*c?b") << endl; return 0; }
代码3:
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isMatch(string s, string p) { if (p.empty()) return s.empty(); if (s.empty()) { if (p[0] == '*') return isMatch(s, p.substr(1)); else return false; } if (p[0] == '*') return isMatch(s, p.substr(1)) || isMatch(s.substr(1), p); else return (s[0] == p[0] || p[0] == '?') && isMatch(s.substr(1), p.substr(1)); } }; int main() { Solution s; cout << s.isMatch("aa", "a") << endl; cout << s.isMatch("aa", "*") << endl; cout << s.isMatch("cb", "?a") << endl; cout << s.isMatch("adceb", "*a*b") << endl; cout << s.isMatch("acdcb", "a*c?b") << endl; return 0; }
代码4:
#include <bits/stdc++.h> using namespace std; class Solution { public: bool isMatch(string s, string p) { if (s == "" && p == "" || (s == "" && p == "*")) return true; if (s == p) return true; int lens = s.length(); int lenp = p.length(); bool questionm = false, starm = false; for (int k = 0; k < lenp; k++) { if (p[k] == '?') questionm = true; if (p[k] == '*') starm = true; } if (lenp != lens && questionm == false && starm == false) return false; int i = 0, j = 0; int mstar = 0, sstar = -1; while (i < lens) { if (j < lenp && p[j] == '*') { mstar = i; sstar = j; j += 1; } else if (j < lenp && (s[i] == p[j] || p[j] == '?')) { i++; j++; } else if (sstar != -1) { mstar += 1; j = sstar + 1; i = mstar; } else return false; } while (j < lenp) { if (p[j] != '*') return false; j++; } return true; } }; int main() { Solution s; cout << s.isMatch("aa", "a") << endl; cout << s.isMatch("aa", "*") << endl; cout << s.isMatch("cb", "?a") << endl; cout << s.isMatch("adceb", "*a*b") << endl; cout << s.isMatch("acdcb", "a*c?b") << endl; return 0; }
62. 不同路径
一个机器人位于一个 m x n
网格的左上角 (起始点在下图中标记为 “Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。问总共有多少条不同的路径?
示例 1:
输入:m = 3, n = 7
输出:28
示例 2:
输入:m = 3, n = 2
输出:3
解释:从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3:
输入:m = 7, n = 3
输出:28
示例 4:
输入:m = 3, n = 3
输出:6
提示:
1 <= m, n <= 100
- 题目数据保证答案小于等于
2 * 10^9
代码1:
#include <bits/stdc++.h> using namespace std; class Solution { public: int uniquePaths(int m, int n) { int N = m + n - 2; int M = m < n ? m - 1 : n - 1; long ans = 1; for (int i = 1; i <= M; i++) ans = ans * (N - i + 1) / i; return ans; } }; int main() { Solution s; cout << s.uniquePaths(3, 7) << endl; cout << s.uniquePaths(3, 2) << endl; cout << s.uniquePaths(7, 3) << endl; cout << s.uniquePaths(3, 3) << endl; return 0; }
代码2:
#include <bits/stdc++.h> using namespace std; class Solution { public: int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) { return 0; } vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } }; int main() { Solution s; cout << s.uniquePaths(3, 7) << endl; cout << s.uniquePaths(3, 2) << endl; cout << s.uniquePaths(7, 3) << endl; cout << s.uniquePaths(3, 3) << endl; return 0; }
代码3:
#include <bits/stdc++.h> using namespace std; typedef vector<int> BigInt; class Solution { public: int uniquePaths(int m, int n) { if (m == 0 || n == 0) return 0; if (m == 1 || n == 1) return 1; int m_ = m - 1 + n - 1; int n_ = n - 1; BigInt a = fac(m_); int result = 0; for (int i = n_; i >= 1; i--) a = div(a, i); for (int i = m_ - n_; i >= 1; i--) a = div(a, i); int k = a.size() - 1; while (a[k] == 0) k--; for (int i = k; i >= 0; i--) result = result * 10 + a[i]; return result; } BigInt fac(int n) { BigInt result; result.push_back(1); for (int factor = 1; factor <= n; ++factor) { long long carry = 0; for (auto &item : result) { long long product = item * factor + carry; item = product % 10; carry = product / 10; } if (carry > 0) { while (carry > 0) { result.push_back(carry % 10); carry /= 10; } } } return result; } BigInt div(BigInt a, int d) { int b = 0; BigInt result; int len = a.size(); for (int i = len - 1; i >= 0; i--) { b = b * 10 + a[i]; result.insert(result.begin(), b / d); b = b % d; } return result; } }; int main() { Solution s; cout << s.uniquePaths(3, 7) << endl; cout << s.uniquePaths(3, 2) << endl; cout << s.uniquePaths(7, 3) << endl; cout << s.uniquePaths(3, 3) << endl; return 0; }
代码4:
#include <bits/stdc++.h> using namespace std; class Solution { public: int uniquePaths(int m, int n) { vector<vector<int>> path(m, vector<int>(n, 0)); for (int i = 0; i < n; i++) path[0][i] = 1; for (int i = 0; i < m; i++) path[i][0] = 1; for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) path[i][j] = path[i - 1][j] + path[i][j - 1]; return path[m - 1][n - 1]; } }; int main() { Solution s; cout << s.uniquePaths(3, 7) << endl; cout << s.uniquePaths(3, 2) << endl; cout << s.uniquePaths(7, 3) << endl; cout << s.uniquePaths(3, 3) << endl; return 0; }
63. 不同路径 II
一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径?
网格中的障碍物和空位置分别用 1
和 0
来表示。
示例 1:
输入:obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出:2
解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径:
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
示例 2:
输入:obstacleGrid = [[0,1],[0,0]]
输出:1
提示:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j]
为0
或1
代码1:
#include <bits/stdc++.h> using namespace std; class Solution { public: int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) { int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); int p[m][n]; int k = 0; while (k < m && obstacleGrid[k][0] != 1) p[k++][0] = 1; while (k < m) p[k++][0] = 0; k = 0; while (k < n && obstacleGrid[0][k] != 1) p[0][k++] = 1; while (k < n) p[0][k++] = 0; for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 1) p[i][j] = 0; else p[i][j] = p[i - 1][j] + p[i][j - 1]; } return p[m - 1][n - 1]; } }; int main() { Solution s; vector<vector<int>> obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; obstacleGrid = {{0,1},{0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; return 0; }
代码2:
#include <bits/stdc++.h> using namespace std; class Solution { public: int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); vector<vector<int>> dp(m, vector<int>(n, 0)); for (int i = 0; i < m && obstacleGrid[i][0] != 1; i++) { dp[i][0] = 1; } for (int i = 0; i < n && obstacleGrid[0][i] != 1; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] != 1) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } } return dp[m - 1][n - 1]; } }; int main() { Solution s; vector<vector<int>> obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; obstacleGrid = {{0,1,0},{0,0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; return 0; }
代码3:
#include <bits/stdc++.h> using namespace std; class Solution { public: int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) { if (obstacleGrid.size() == 0 || obstacleGrid[0].size() == 0) return 0; int m = obstacleGrid.size(); int n = obstacleGrid[0].size(); vector<vector<int>> info(m, vector<int>(n, 0)); for (int i = 0; i < m; ++i) { if (obstacleGrid[i][0] == 1) { for (int j = i; j < m; j++) { info[j][0] = 0; } break; } else info[i][0] = 1; } for (int i = 0; i < n; ++i) { if (obstacleGrid[0][i] == 1) { for (int j = i; j < n; ++j) { info[0][j] = 0; } break; } else info[0][i] = 1; } for (int i = 1; i < m; ++i) { for (int j = 1; j < n; ++j) { if (obstacleGrid[i][j] == 1) { info[i][j] = 0; } else { info[i][j] = info[i - 1][j] + info[i][j - 1]; } } } return info[m - 1][n - 1]; } }; int main() { Solution s; vector<vector<int>> obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; obstacleGrid = {{0,1,0},{0,0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; return 0; }
代码4:
#include <bits/stdc++.h> using namespace std; class Solution { public: int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) { int m = obstacleGrid.size(), n = obstacleGrid[0].size(); if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0; vector<vector<int>> dp(m, vector<int>(n, 0)); dp[0][0] = 1; for (int i = 1; i < m; i++) { if (obstacleGrid[i][0] == 0) dp[i][0] = dp[i - 1][0]; } for (int i = 1; i < n; i++) { if (obstacleGrid[0][i] == 0) dp[0][i] = dp[0][i - 1]; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (obstacleGrid[i][j] == 0) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } }; int main() { Solution s; vector<vector<int>> obstacleGrid = {{0,0,0},{0,1,0},{0,0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; obstacleGrid = {{0,1,0},{0,0,0}}; cout << s.uniquePathsWithObstacles(obstacleGrid) << endl; return 0; }
64. 最小路径和
给定一个包含非负整数的 m x n
网格 grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12
提示:
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100
代码1:
#include <bits/stdc++.h> using namespace std; class Solution { public: int minPathSum(vector<vector<int>> &grid) { if (grid.size() == 0) return 0; int m = grid.size(); int n = grid[0].size(); vector<vector<int>> m_memo = vector<vector<int>>(m + 1, vector<int>(n + 1, 0)); for (int i = n - 1; i >= 0; --i) m_memo[m - 1][i] = grid[m - 1][i] + m_memo[m - 1][i + 1]; for (int j = m - 1; j >= 0; --j) m_memo[j][n - 1] = grid[j][n - 1] + m_memo[j + 1][n - 1]; for (int i = m - 2; i >= 0; --i) { for (int j = n - 2; j >= 0; --j) { m_memo[i][j] = grid[i][j] + min(m_memo[i][j + 1], m_memo[i + 1][j]); } } return m_memo[0][0]; } }; int main() { Solution s; vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}}; cout << s.minPathSum(grid) << endl; grid = {{1,2,3},{4,5,6}}; cout << s.minPathSum(grid) << endl; return 0; }
代码2:
#include <bits/stdc++.h> using namespace std; class Solution { public: int minPathSum(vector<vector<int>> &grid) { int row = grid.size(); int column = grid[0].size(); for (int i = 1; i < column; ++i) { grid[0][i] = grid[0][i - 1] + grid[0][i]; } for (int i = 1; i < row; ++i) { grid[i][0] = grid[i - 1][0] + grid[i][0]; } for (int i = 1; i < row; ++i) { for (int j = 1; j < column; ++j) { int temp = grid[i - 1][j] > grid[i][j - 1] ? grid[i][j - 1] : grid[i - 1][j]; grid[i][j] = grid[i][j] + temp; } } return grid[row - 1][column - 1]; } }; int main() { Solution s; vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}}; cout << s.minPathSum(grid) << endl; grid = {{1,2,3},{4,5,6}}; cout << s.minPathSum(grid) << endl; return 0; }
代码3:
#include <bits/stdc++.h> using namespace std; class Solution { public: int minPathSum(vector<vector<int>> &grid) { int row = grid.size(); int col = grid[0].size(); vector<int> f(col, 0); for (int i = 0; i < row; ++i) { f[0] = f[0] + grid[i][0]; for (int j = 1; j < col; ++j) { if (i == 0) f[j] = f[j - 1] + grid[i][j]; else f[j] = min(f[j - 1], f[j]) + grid[i][j]; } } return f[col - 1]; } }; int main() { Solution s; vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}}; cout << s.minPathSum(grid) << endl; grid = {{1,2,3},{4,5,6}}; cout << s.minPathSum(grid) << endl; return 0; }
代码4:
#include <bits/stdc++.h> using namespace std; class Solution { private: int m, n; int memo[100][100]; public: int minPathSum(vector<vector<int>> &grid) { m = grid.size(), n = grid[0].size(); for (int i = 0; i < m; i++) { memset(memo[i], -1, sizeof(int) * n); } return dfs(grid, 0, 0); } int dfs(vector<vector<int>> &grid, int r, int c) { if (r < 0 || r >= m || c < 0 || c >= n) return 1000000; if (memo[r][c] != -1) return memo[r][c]; if (r == m - 1 && c == n - 1) { memo[r][c] = grid[m - 1][n - 1]; return memo[r][c]; } int right = dfs(grid, r, c + 1); int down = dfs(grid, r + 1, c); memo[r][c] = min(right, down) + grid[r][c]; return memo[r][c]; } }; int main() { Solution s; vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}}; cout << s.minPathSum(grid) << endl; grid = {{1,2,3},{4,5,6}}; cout << s.minPathSum(grid) << endl; return 0; }
续:https://hannyang.blog.csdn.net/article/details/132091605