[アルゴリズムC++]整数三角形


今日の質問


https://programmers.co.kr/learn/courses/30/lessons/43105

せいすうさんかくけい



私の答え

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    
    vector<vector<int>> dp = triangle;
    for(int i=0;i<triangle.size()-1;i++){
        for(int j =0;j<triangle[i].size();j++){
            dp[i][j] = -1;
        }
    }
    dp[0][0] = triangle[0][0];
    
    for(int i=0;i<triangle.size()-1;i++){
        for(int j =0;j<triangle[i].size();j++){
            int up = dp[i][j];
            dp[i+1][j] = max(dp[i+1][j], up + triangle[i+1][j]);//왼
            dp[i+1][j+1] = max(dp[i+1][j+1], up + triangle[i+1][j+1]);//오
        }
    }
    for(int i=0;i<dp[dp.size()-1].size();i++)
        answer = max(answer, dp[dp.size()-1][i]);
    return answer;
}

模範解答

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;

    int temp;
    int Size = triangle.size();
    for (int i = 0; i < Size; ++i)
    {
        temp = 0;
        if (i != Size - 1)
        {
            for (int j = 0; j < triangle[i].size(); ++j)
            {
                if (temp < triangle[i + 1][j] + triangle[i][j])
                    temp = triangle[i + 1][j] + triangle[i][j];

                triangle[i+1][j] = temp;
                if (j != triangle[i].size() - 1)
                    temp = triangle[i + 1][j + 1] + triangle[i][j];
                else
                    triangle[i + 1][j + 1] += triangle[i][j];
            }
        }
        else if (i == Size - 1)
        {
            for (int j = 0; j < triangle[i].size(); ++j)
            {
                if (answer < triangle[i][j])
                    answer = triangle[i][j];
            }
        }
    }

    return answer;
}

学ぶべきところ


第3段階はココア問題と第2段階を除いて差が少ない.
  • プログラマー60問をクリア!9月の最終日、バージェビットは
  • をしました.