动态规划的一般解题方法

解题思路:

注意事项:

参考代码:

#include<iostream>
using namespace std;

int arr[100][100] ={0};
int dp[100][100];
int maxi =-1;
void my(int n)
{
for(int i =1;i<=n;i++)
{
for(int j =1;j<=i;j++)
{
cin>>arr[i][j];
}
}
for(int i =1;i<=n;i++)
{
for(int j =1;j<=i;j++)
{
dp[i][j]= max(dp[i-1][j-1],dp[i-1][j])+arr[i][j]; //递推，dp[i][j]只能由dp[i-1][j]或者dp[i-1][j-1]得来
}
}
for(int i =1;i<=n;i++)
{
for(int j =1;j<=i;j++)
{
if(dp[i][j]>maxi)
{
maxi=dp[i][j];
}
}
}
cout<<maxi<<endl;
}

 
int main()
{
int n =0;
cin>>n;
for(int i =0;i<n;i++)
{
int j;
cin>>j;
my(j);
}
return 0;
 }