中国建设银行对公网站,广州工商注册名字查询,国家职业资格证书官网,网页网站怎么做的动态规划
题目#xff1a;
建议看这里#xff0c;有这道题详细的解析。我觉得写的挺好。
这是我在学动态规划的时候#xff0c;动手做的一道题。
虽然我在学动态规划#xff0c;但是我之前学了dps#xff0c;所以我就想先用dps试着做#xff0c;结果发现不行#xf…动态规划
题目
建议看这里有这道题详细的解析。我觉得写的挺好。
这是我在学动态规划的时候动手做的一道题。
虽然我在学动态规划但是我之前学了dps所以我就想先用dps试着做结果发现不行原因是我的中止条件没有弄好最终如果改成dpsmemory就会和动态规划一样了。 解析
dp状态【Fxy】走到xy时所用的最小路径和。满足「最优子结构」和「无后效性」。
dp转移方程分类讨论的思想
如果上边和左边都有就找上边和左边的min如果只有上边那就上边最小路径和xy的值如果只有左边那就左边最小路径和xy的值如果上边左边都没有就保持原来的值00
复杂度计算
时间复杂度O(nm) 空间复杂度O(1)
代码
这题一写就过了太好了
#include vector
//解法一动态规划
//最小路径和
//时间复杂度O(nm)
//空间复杂度O(1)
class Solution {
public:int minPathSum(std::vectorstd::vectorint grid) {if (grid.empty() || grid[0].empty())return 0;row grid.size();col grid[0].size();//状态grid[i][j]for (int i 0; i row; i){for (int j 0; j col; j){//转移方程分类讨论if (i - 1 0 j - 1 0)//上边和左边都有就找上边和左边的mingrid[i][j] (grid[i][j - 1] grid[i - 1][j]) ? grid[i][j - 1] : grid[i - 1][j];else if (i - 1 0)//只有上边grid[i][j] grid[i - 1][j];else if (j - 1 0)//只有左边grid[i][j] grid[i][j - 1];}}return grid[row - 1][col - 1];}
private:int row;int col;
};void Test_solution2()
{//std::vectorstd::vectorint grid { {1,3,1},{1,5,1},{4,2,1} };//std::vectorstd::vectorint grid { {1,2,3},{4,5,6} };//std::vectorstd::vectorint grid { {1,2,3} };//std::vectorstd::vectorint grid { {1,3,1},{1,5,1},{4,2,0} };//std::vectorstd::vectorint grid { {3} };std::vectorstd::vectorint grid { {} };Solution solution;std::cout solution.minPathSum(grid);
}
