动态规划（dp）之路径规划（Path Planning）_动态路径规划

五步走：

1、状态表示；

2、转移方程；（核心）

3、初始化

        （1）赋值

        （2）赋值虚拟位置（虚拟表的值、映射））；

4、填表顺序；

5、返回值。

//地下城游戏
int calculateMinimumHP(vector<vector<int>>& dungeon) {
	int m = dungeon.size();
	int 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]);
		}
	return dp[0][0];
}
 
//最小路径和
int minPathSum(vector<vector<int>>& grid) {
	int m = grid.size();
	int n = grid[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
	dp[0][0] = dp[0][1] = dp[1][0] = 0;
	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 - 1][j - 1];
	return dp[m][n];
}
 
//下降路径最小和
int minFallingPathSum(vector<vector<int>>& matrix) {
	int m = matrix.size();
	int n = matrix[0].size();
	vector<vector<int>> dp(m + 1, vector<int>(n + 2, INT_MAX));
	for (int i = 0; i <= n + 1; i++)
		dp[0][i] = 0;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) + matrix[i - 1][j - 1];
	int ret = dp[m][1];
	for (int j = 1; j <= n; j++)
		ret = min(ret, dp[n][j]);
	return ret;
}
 
//礼物的最大价值
int maxValue(vector<vector<int>>& grid) {
	int m = grid.size();
	int n = grid[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][j - 1], dp[i - 1][j]) + grid[i - 1][j - 1];
	return dp[m][n];
}
 
//不同路径
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
	int m = obstacleGrid.size();  //行
	int 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][j] == 0)
			dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
		}
	return dp[m][n];
}
 
//路径规划
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];
}