c++怎么找出路徑數目與最小路徑和

這篇文章主要介紹“c++怎么找出路徑數目與最小路徑和”，在日常操作中，相信很多人在c++怎么找出路徑數目與最小路徑和問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”c++怎么找出路徑數目與最小路徑和”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

#include <iostream>
#include <vector>
#include <limits>
using namespace std;

/*
思路：對于某一點dp[i][j]的路徑數目，是該點正上方和正左方路徑數目之和
dp[i][j] = dp[i][j-1] + dp[i-1][j]; 但是對于特殊地方需要特殊考慮 
*/

int Unique_path(int m,int n,int first,int second)
{
	vector<vector<int> > dp(m);
	int i,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];
					else if(j== 0)
						dp[i][j] = dp[i-1][j];
					else
						dp[i][j] = dp[i][j-1]+dp[i-1][j];
				}
			}
		}
	} 
	return dp[m-1][n-1];
} 

/*
第二個問題，從左上角到右下角，尋找代價最小的路徑 
典型的動態規劃問題，和上個問題類似
*/

int MinPathSum(vector<vector<int> >& vec)
{
	vector<vector<int> > dp(vec.size());
	int i,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];
	
	int tmp;
	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);
		}		
 	}
	return dp[vec.size()-1][vec[0].size()-1];
} 


int main()
{
//	cout << Unique_path(3,7,2,3)<<endl;
	vector<vector<int> > vec(3);
	int i,j;
	int array[]={2,4,3,7};
	int array1[]={5,3,2,1};
	int array2[]={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;
	return 0;
}

到此，關于“c++怎么找出路徑數目與最小路徑和”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！