欲張り法_ダイナミックプランニング-タワー問題

貪欲法は,各選択において現在の状態で最良または最良の選択をとり,最適解を得るアルゴリズムである.一つの直感的な解釈は『まっすぐ行け!』です.
貪欲法は、最小生成ツリー、ハフマン符号化など、一般的なアルゴリズム問題の一部を解決することができ、1つの問題が貪欲法で解決できれば、貪欲法は最適なアルゴリズムに違いない.
ほとんどの問題に対して貪欲法を用いると必ずしも最適解が得られるとは限らない.例えば迷路を歩いているときにゴールまでまっすぐ行くと、袋小路に出る可能性が高い.
しかし、ほとんどの問題に対して、貪欲法は少なくとも1つの最適に近い解を与えることができ、したがって、貪欲法は、探索上界を決定するために使用される補助アルゴリズム、または正確な最適解を与える必要がないいくつかのシナリオとしてしばしば使用される.
動的計画は,原問題を比較的簡単なサブ問題に分解することによって複雑な問題を解く方法である.動的計画の解法の多くは繰返しであり,再帰的に解かなければならない問題もあるが,通常はまず問題の状態表現を決定し,状態間の遷移方程式を押し出して最終状態の解を求める.
動的計画で問題を正しく解決できる条件は3つあります.

     ：              （                ）；

    ：         ，                 ；

     ：           ，               ，             ，              。

ダイナミックプランニングには多くのタイプがあり、ダイナミックプランニングの順序に従って線形ダイナミックプランニングとツリーダイナミックプランニングが区分されています.また,状態圧縮付きダイナミックプランニングもプログラム設計コンテストによく登場する知識点である.
動的計画の古典的な問題は、最長共通サブシーケンス(LCS)、最長上昇サブシーケンス(LIS)、リュックサック問題(01リュックサック、多重リュックサックなど)、連通性動的計画(通称プラグDP)、ハミルトンロード、スタンナツリーなど、多くあり、興味のある読者はネット検索を通じて関連資料を読み続けることができる.
数塔問題は貪欲な戦略動態計画に適しておらず,繰返しとして理解でき,前の層の2つの値の中から1つの大きいものを選択し,本層を計算した.

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 100;
//                ，o   o x    
template <class T>
void updateMax(T& o, const T& x) {
    o = (o > x) ? o : x;
}

// f            
// num        
// n        
int f[N][N], num[N][N], n;

int main() {
    //   n     num
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            scanf("%d", &num[i][j]);
        }
    }

    // step 1 begin:              
    //       ，       
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j){
            //f[i][j]        （i,j）       
            updateMax(f[i][j],max(f[i-1][j],f[i-1][j-1])+num[i][j]);
        }
    }
    // step 1 end.

    //         result，        ，      0
    int result = 0;
    for (int i = 1; i <= n; ++i) {
        // step 2 begin:               
        //   ，       result
        updateMax(result,f[n][i]);
        // step 2 end.
    }
    //          result
    printf("%d
", result);
    return 0;
}