2127: 信息学奥赛一本通T1258- 数字金字塔

解题思路:

注意事项:

参考代码:

//顺推法：

#include<iostream>

using namespace std;

const int N = 1005;

int arr[N][N];

int dp[N][N];

int main()

{

    int R;

    int ans = -1;

    cin >> R;

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

    {

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

        {

            cin >> arr[i][j];//拿到用户输入的所有数据

        }

    }

    dp[0][0] = arr[0][0];//顺推法，需从上往下推，要先把第一个数的值拿到，再推出下面的值

    for (int i = 1; i < R; i++)

    {

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

        {

            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j];//状态转移方程，当选完最优解后，把上一个选的值加上去

        }

    }

    //由于全部计算完之后，会得出最后一行所有值，这时我们只需找出最大值即可

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

    {

        ans = max(ans, dp[R - 1][i]);

    }

    cout << ans;

    return 0;

}

//逆推法：

#include<iostream>

using namespace std;

const int N = 1005;

int arr[N][N];

int dp[N][N];

int main()

{

int R;

cin >> R;

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

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

cin >> arr[i][j];

for (int i = 0; i < R; i++)//拿到最后一行的数据

dp[R - 1][i] = arr[R - 1][i];

for (int i = R - 2; i >= 0; i--)//从最后一行往上递推

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

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

cout << dp[0][0];//推出来之后第一个数就是最大值

return 0;

}