[アルゴリズム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段階を除いて差が少ない.
Reference
この問題について([アルゴリズムC++]整数三角形), 我々は、より多くの情報をここで見つけました https://velog.io/@huijae0817/알고리즘-C-정수-삼각형テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol