【C/C++】金币

做了一下去年的题目，今年看起来就没这么难了

从上到下的可以从下到上考虑，会简单很多，dp入门

题目金币

小招在玩一款游戏，在一个N层高的金字塔上，以金字塔顶为第一层，第i层有i个落点，每个落点有若干金币，在落点可以往向下或右斜向下移动，问能获得的最大金币值。

其实也没啥好说的，就是动态规划数塔问题，从第N层塔往上走比较好算。

样例输入

5

8

3 8

8 1 0

4 7 5 4

3 5 2 6 5

输出

31

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010;

int dp[maxn][maxn];

int data[maxn][maxn];

int main()

{

    memset(data, 0, sizeof(data));

    memset(dp, 0, sizeof(data));

    int n;

    scanf("%d", &n);

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

    {

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

        {

            scanf("%d", &data[i][j]);

        }

    }

    // 边界

    for (int i = n; i>=1; i--)

    {

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

        {

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

        }

    }

    cout << dp[1][1] << endl;

    system("pause");

}

巴特西

【C/C++】金币

最新文章

热门文章