[数据结构与算法]HNU蛇形矩阵

【问题描述】蛇形矩阵是由 1 开始的自然数依次排列成的一个矩阵上三角形

【输入形式】 正整数 N表示层数，N 不大于 100

【输出形式】输出一个 N 行的蛇形矩阵，矩阵三角中同一行的数字用一个空格分开，行尾不要多余的空格。

【样例输入】

5

【样例输出】

1 3 6 10 15
2 5 9 14
4 8 13
7 12
11

这道题，我当时一看，哎呀这不是动态规划吗，我昨晚上刚看过动态规划！照着网上的模板写了一个动态规划，然后我发现不会输出路径了【笑哭】【笑哭】，于是又找了一些代码学着写路径，下面第一种是递归的动态归化，第二种是可以输出路径的方法。

#include<bits/stdc++.h>
#define MAX 101
using namespace std;
int n;
int a[MAX][MAX];
int digui(int i,int j)
{
	if(i==n) return a[i][j];
	int x=digui(i+1,j);
	int y=digui(i+1,j+1);
	return max(x,y)+a[i][j];
}
int main()
{
	int i,j;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	cout<<digui(1,1)<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,i,j;
	int a[101][101],b[101][101],c[101][101];
	cin>>n;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=i;j++)
		{
		    cin>>a[i][j];
		    b[i][j]=a[i][j];
		}
	}
	for(i=n-1;i>=1;i--)
	{
		for(j=1;j<=i;j++)
		{
			if(a[i+1][j]>a[i+1][j+1])
			a[i][j]+=a[i+1][j];
			else 
			{
			    a[i][j]+=a[i+1][j+1];
			    c[i][j]=1;
		    }
		}
	}
	cout<<a[1][1]<<endl;
	j=1;
	for(i=1;i<=n;i++)
	{
		cout<<b[i][j]<<" ";
		j+=c[i][j];
	}
	return 0;
}