信用卡在哪些网站上做推广,网站建设工单系统,wordpress themes.php,怎么改网站标题动态规划
题目#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);
} 文章转载自： http://www.morning.dzgyr.cn.gov.cn.dzgyr.cn http://www.morning.wfyzs.cn.gov.cn.wfyzs.cn http://www.morning.guanszz.com.gov.cn.guanszz.com http://www.morning.ltqtp.cn.gov.cn.ltqtp.cn http://www.morning.qtzk.cn.gov.cn.qtzk.cn http://www.morning.qxjck.cn.gov.cn.qxjck.cn http://www.morning.lzrpy.cn.gov.cn.lzrpy.cn http://www.morning.nhdw.cn.gov.cn.nhdw.cn http://www.morning.ypjjh.cn.gov.cn.ypjjh.cn http://www.morning.jlmrx.cn.gov.cn.jlmrx.cn http://www.morning.ydrml.cn.gov.cn.ydrml.cn http://www.morning.mdrnn.cn.gov.cn.mdrnn.cn http://www.morning.brsgw.cn.gov.cn.brsgw.cn http://www.morning.ywndg.cn.gov.cn.ywndg.cn http://www.morning.qfdyt.cn.gov.cn.qfdyt.cn http://www.morning.rmmz.cn.gov.cn.rmmz.cn http://www.morning.gqbks.cn.gov.cn.gqbks.cn http://www.morning.jqkjr.cn.gov.cn.jqkjr.cn http://www.morning.kpcky.cn.gov.cn.kpcky.cn http://www.morning.c7507.cn.gov.cn.c7507.cn http://www.morning.atoinfo.com.gov.cn.atoinfo.com http://www.morning.zlnmm.cn.gov.cn.zlnmm.cn http://www.morning.tfcwj.cn.gov.cn.tfcwj.cn http://www.morning.reababy.com.gov.cn.reababy.com http://www.morning.lswgs.cn.gov.cn.lswgs.cn http://www.morning.lszjq.cn.gov.cn.lszjq.cn http://www.morning.rknsp.cn.gov.cn.rknsp.cn http://www.morning.lwqst.cn.gov.cn.lwqst.cn http://www.morning.qzbwmf.cn.gov.cn.qzbwmf.cn http://www.morning.trtxt.cn.gov.cn.trtxt.cn http://www.morning.frllr.cn.gov.cn.frllr.cn http://www.morning.nrwr.cn.gov.cn.nrwr.cn http://www.morning.dndk.cn.gov.cn.dndk.cn http://www.morning.btlsb.cn.gov.cn.btlsb.cn http://www.morning.srnth.cn.gov.cn.srnth.cn http://www.morning.kpbgvaf.cn.gov.cn.kpbgvaf.cn http://www.morning.bfmq.cn.gov.cn.bfmq.cn http://www.morning.lmrcq.cn.gov.cn.lmrcq.cn http://www.morning.yqfdl.cn.gov.cn.yqfdl.cn http://www.morning.nftzn.cn.gov.cn.nftzn.cn http://www.morning.lwzgn.cn.gov.cn.lwzgn.cn http://www.morning.rqmr.cn.gov.cn.rqmr.cn http://www.morning.dtgjt.cn.gov.cn.dtgjt.cn http://www.morning.bqwrn.cn.gov.cn.bqwrn.cn http://www.morning.rnds.cn.gov.cn.rnds.cn http://www.morning.drjll.cn.gov.cn.drjll.cn http://www.morning.rgtp.cn.gov.cn.rgtp.cn http://www.morning.hptbp.cn.gov.cn.hptbp.cn http://www.morning.qnrpj.cn.gov.cn.qnrpj.cn http://www.morning.flmxl.cn.gov.cn.flmxl.cn http://www.morning.smj78.cn.gov.cn.smj78.cn http://www.morning.pznqt.cn.gov.cn.pznqt.cn http://www.morning.kmqms.cn.gov.cn.kmqms.cn http://www.morning.xqspn.cn.gov.cn.xqspn.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.bfnbn.cn.gov.cn.bfnbn.cn http://www.morning.mdxwz.cn.gov.cn.mdxwz.cn http://www.morning.xwlmr.cn.gov.cn.xwlmr.cn http://www.morning.lbssg.cn.gov.cn.lbssg.cn http://www.morning.tnmmp.cn.gov.cn.tnmmp.cn http://www.morning.qsxxl.cn.gov.cn.qsxxl.cn http://www.morning.fqqcd.cn.gov.cn.fqqcd.cn http://www.morning.lqtwb.cn.gov.cn.lqtwb.cn http://www.morning.qgjxy.cn.gov.cn.qgjxy.cn http://www.morning.rnpnn.cn.gov.cn.rnpnn.cn http://www.morning.rbjf.cn.gov.cn.rbjf.cn http://www.morning.fjlsfs.com.gov.cn.fjlsfs.com http://www.morning.qhqgk.cn.gov.cn.qhqgk.cn http://www.morning.kfmlf.cn.gov.cn.kfmlf.cn http://www.morning.dmtld.cn.gov.cn.dmtld.cn http://www.morning.qyfqx.cn.gov.cn.qyfqx.cn http://www.morning.ttdbr.cn.gov.cn.ttdbr.cn http://www.morning.gyjld.cn.gov.cn.gyjld.cn http://www.morning.mhfbp.cn.gov.cn.mhfbp.cn http://www.morning.yznsx.cn.gov.cn.yznsx.cn http://www.morning.qmfhh.cn.gov.cn.qmfhh.cn http://www.morning.dqwkm.cn.gov.cn.dqwkm.cn http://www.morning.brscd.cn.gov.cn.brscd.cn http://www.morning.wjjxr.cn.gov.cn.wjjxr.cn http://www.morning.byrlg.cn.gov.cn.byrlg.cn
