蓝桥杯算法提高VIP-夺宝奇兵 （C++代码）

解题思路:dp动态规划求解





注意事项:





参考代码:

#include <deque>

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <iterator>

#include <numeric>

#include <iomanip>

#include <sstream>  

#include <string>

#include <cmath>

#include <string.h>

using namespace std;

int dp[101][101];

int a[101][101];

int main()

{

int n;

cin>>n;

for(int i=0;i<n;i++)

{

for(int j=0;j<=i;j++)

{

cin>>a[i][j];

}

}

for(int j=0;j<n;j++)

{

dp[n-1][j]=a[n-1][j];

}

for(int i=n-2;i>=0;i--)

{

for(int j=0;j<=i;j++)

{

dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+a[i][j];

}

}

cout<<dp[0][0]<<endl;

return 0;

}