动态规划法求解三角形最小路径问题

特殊情况：两个边界，即第1列和对角线达到它们中结点的路径只有一条而不是常规的两条。

状态转移方程：

#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
using namespace std;

#define MAXN 100
int a[MAXN][MAXN];
int n;

int ans=0;
int dp[MAXN][MAXN];
int pre[MAXN][MAXN];

int Search(){
	dp[0][0]=a[0][0];
	for(int i=1;i<n;i++){
		dp[i][0]=dp[i-1][0]+a[i][0];
		pre[i][0]=i;
	}
	for(int i=1;i<n;i++){
		dp[i][i]=a[i][i]+dp[i-1][i-1];
		pre[i][i]=i-1;
	}
	for(int i=2;i<n;i++){
		for(int j=1;j<i;j++){
			if(dp[i-1][j-1]<dp[i-1][j]) {
				pre[i][j]=j-1;
				dp[i][j]=a[i][j]+dp[i-1][j-1];
			}
			else {
				pre[i][j]=j;
				dp[i][j]=a[i][j]+dp[i-1][j];
			}
		}
	}
	ans=dp[n-1][0];
	int k=0;
	for(int j=1;j<n;j++){
		if(ans>dp[n-1][j]) {
			ans=dp[n-1][j];
			k=j;
		}
	}
	return k;
}
void Disppath(int k){
	int i=n-1;
	vector<int>path;
	while(i>=0){
		path.push_back(a[i][k]);
		k=pre[i][k];
		i--;
	}
	vector<int>::reverse_iterator it;
	for(it=path.rbegin();it!=path.rend();++it){
		cout<<*it<<" ";
	}
}
int main(){
	int k;
	memset(pre,0,sizeof(pre));
	memset(dp,0,sizeof(dp));
	//输入三角形 
	cin>>n;
	k=Search();
	Disppath(k);
	cout<<ans<<endl;
}

最后

以上就是文静水蜜桃为你收集整理的动态规划法求解三角形最小路径问题的全部内容，希望文章能够帮你解决动态规划法求解三角形最小路径问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。