[プログラマ]整数三角形

8639 ワード
DP programmers C どうてきけいかくほう Level 3 テキストリンク

質問リンク

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

    • 問題の概要

  • から与えられたデジタルピラミッドの頂部から底部までの数字の和が最大の値である.

    • パルプ流


  • 問題に表示される中央揃えの数値三角形を左揃えに変更すると、
    7
    3 8
    8 1 0
    2 7 4 4
    4 5 2 6 5
    このような形態を形成する.
    2 D配列の行を1行1列見、各数字を1行1列見ます.

  • セルを下に移動すると、対角線方向に1つのセルの右または左側しか移動できません.
    現在位置の数字は、対角線の左上から対角線の右下に、対角線の右上から左下にも表示されます.
    現在位置の数字がiの1行目のj次の数字であれば、上から現在位置までの数字はi-1の1行目のj-1次の数字、i-1の1行目のj+1次の数字とすることができる.

  • 現在のtriangle[i][j]の値は固定されているため、以前にどの数字がここに到着したかによって、数字全体とが決定されます.したがって、現在位置の数字が到達可能な最大数字の和をdp[i][j]と呼ぶと、
    dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j+1])

  • 上部から下部まで、各数字が持つことができる数字とdpを求め、下部dpの最大値を戻せばよい.

    • コード#コード#

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

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

    int dp[500][500];
    for(int i=0;i<500;i++)
    {
        for(int j=0;j<500;j++)
            dp[i][j] = 0;
    }
    
    dp[0][0] = triangle[0][0];
    
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            int from_left = j > 0 ? dp[i-1][j-1] : 0;
            int from_right = j < i ? dp[i-1][j] : 0;
            dp[i][j] = triangle[i][j] + max(from_left, from_right);
        }
    }
    
    for(int i=0;i<n;i++)
    {
        if(answer < dp[n-1][i])
            answer = dp[n-1][i];
    }
    
    return answer;
}
    特定の語のみを置換[MySQL]
    Lv.1数字の文字列と英語の単語