招商银行2020FinTech精英训练营-研发赛道 A 金币

题目描述

小招在玩一款游戏：在一个N层高的金字塔上，以金字塔顶为第一层，第i层有i个落点，每个落点有若干枚金币，在落点可以跳向左斜向下或向右斜向下的落点。若知道金字塔的层数N及每层的金币数量分布，请计算小招在本次游戏中可以获得的最多金币数量。

输入描述:

输入共有N + 1行(N ≤ 1024)，第一行为高度N，第二行至N + 1行 ，为该金字塔的金币数量分布。

输出描述:

输出金币数量。

示例1

输入
5
8
3 8
8 1 0
4 7 5 4
3 5 2 6 5

输出
31

思路

动态规划。p[i][j]表示第i+1层第j+1个落点上有几枚金币。dp[i][j]表示落到第i+1层左起第j+1个落点上所得到的最多金币数




最终结果就是 max(dp[n-1])。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n,input;
    cin>>n;
    vector<vector<int>> p(n), dp(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<i+1;j++){
            cin>>input;
            p[i].push_back(input);
            if(i==0){
                dp[i].push_back(p[0][0]);
            }else if(j==0){
                dp[i].push_back(dp[i-1][0]+p[i][0]);
            }else if(j==i){
                dp[i].push_back(dp[i-1][i-1]+p[i][i]);
            }else{
                dp[i].push_back(max(dp[i-1][j-1],dp[i-1][j])+p[i][j]);
            }
        }
    }
    vector<int>::iterator idx = max_element(dp[n-1].begin(), dp[n-1].end());
    cout<<*idx;
    return 0;
}