(动态规划路径基础 最小路径和)leetcode 64
视频教程
1.初始化dp数组，初始化边界
2、从[1行到n-1行][1列到m-1列]依次赋值
#include<vector>
#include<algorithm>
#include <iostream>
using namespace std;
int main()
{
vector<vector<int>> grid = { {1,3,1},{1,5,1},{4,2,1} };
vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), 0));
dp[0][0] = grid[0][0];
for (int i = 1;i < grid[0].size();i++)
{
dp[0][i] = grid[0][i] + dp[0][i-1];
}
for (int i = 1;i < grid.size();i++)
{
dp[i][0] = grid[i][0] + dp[i-1][0];
}
for (int i = 1;i < grid.size();i++)
{
for (int j = 1;j < grid[0].size();j++)
{
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1])+grid[i][j];
}
}
cout << dp[grid.size()-1][grid[0].size() - 1] << endl;
for (int i = 0;i < dp.size();i++)
{
for (auto n : dp[i])
{
cout << n<<" ";
}
cout << endl;
}
return 0;
}