c 怎么找出路径数目与最小路径和

这篇文章主要介绍“c 怎么找出路径数目与最小路径和”，在日常操作中，相信很多人在c 怎么找出路径数目与最小路径和问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”c 怎么找出路径数目与最小路径和”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！
#include<iostream>#include<vector>#include<limits>usingnamespacestd;/*思路：对于某一点dp[i][j]的路径数目，是该点正上方和正左方路径数目之和dp[i][j]=dp[i][j-1] dp[i-1][j];但是对于特殊地方需要特殊考虑*/intunique_path(intm,intn,intfirst,intsecond){vector<vector<int>>dp(m);inti,j;for(i=0;i<dp.size();i )dp[i].assign(n,0);dp[0][0]=1;for(i=0;i<dp.size();i ){for(j=0;j<dp[0].size();j ){if(i!=0||j!=0){if(i==first&&j==second)dp[i][j]=0;else{if(i==0)dp[i][j]=dp[i][j-1];elseif(j==0)dp[i][j]=dp[i-1][j];elsedp[i][j]=dp[i][j-1] dp[i-1][j];}}}}returndp[m-1][n-1];}/*第二个问题，从左上角到右下角，寻找代价最小的路径典型的动态规划问题，和上个问题类似*/intminpathsum(vector<vector<int>>&vec){vector<vector<int>>dp(vec.size());inti,j;for(i=0;i<vec.size();i )dp[i].assign(vec[i].size(),numeric_limits<int>::max());dp[0][0]=vec[0][0];for(i=1;i<vec.size();i )dp[i][0]=vec[i][0] dp[i-1][0];for(j=1;j<vec[0].size();j )dp[0][j]=vec[0][j] dp[0][j-1];inttmp;for(i=1;i<vec.size();i ){for(j=1;j<vec[0].size();j ){tmp=min(vec[i][j] dp[i][j-1],vec[i][j] dp[i-1][j]);dp[i][j]=min(dp[i][j],tmp);}}returndp[vec.size()-1][vec[0].size()-1];}intmain(){//cout<<unique_path(3,7,2,3)<<endl;vector<vector<int>>vec(3);inti,j;intarray[]={2,4,3,7};intarray1[]={5,3,2,1};intarray2[]={4,8,6,2};vec[0].assign(array,array 4);vec[1].assign(array1,array1 4);vec[2].assign(array2,array2 4);cout<<minpathsum(vec)<<endl;return0;}
到此，关于“c 怎么找出路径数目与最小路径和”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注箭头云网站，小编会继续努力为大家带来更多实用的文章！

微信公众号-市场咨询
美团、大众点评、百度糯米APP竞品分析报告
域名实名认证被拒绝了说电子信息不合适为什么
百度发布第三季度财报：实现营收282亿元，净利润137亿元
全面开放合作 华为携手合作伙伴共筑会员生态
如何部署web项目到云服务器
盘点APP推广里面的这些坑
管理云服务器的网站源码