1514: 蓝桥杯算法提高VIP-夺宝奇兵

解题思路:这道题有点奇怪，有些条件没有说清楚，这里题人不能往右走，切只能往上走或者走左上角，既然这样就直接dp

注意事项:当i==j的时候不能往上走，如果没有限制的话会超时

参考代码:

#include<bits/stdc++.h>
using namespace std;
int x[105][105];
int dp[105][105];
int opt(int j,int i)
{
	if(i==-1||j==-1)return 0;//超出山的界限直接结束
	if(i==0&&j==0)return x[0][0];//到山顶
	if(i==j)return x[i][j]+opt(j-1,i-1);
	if(dp[i][j]!=0)return dp[i][j];//记忆存储防止多做做过的
	return dp[i][j]=max(x[i][j]+opt(j,i-1),x[i][j]+opt(j-1,i-1));
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<=i;j++)
    	{
    		cin>>x[i][j];
    	}
    }
    int num=0;
    int t;
    for(int j=n-1;j>=0;j--)
    {

    	if(num<(t=(opt(j,n-1))))
    	{
    		num=t;
    	}
    }
    cout<<num<<endl;
    return 0;
}