DP数タワー問題

1131 ワード

最上階から下層階まで歩くことが求められ、一歩ごとに隣接するノードまでしか歩けない場合、通過するノードの数の和は最大でいくらですか? 
試験例の最初の行は整数N(1<=N<=100)であり、数塔の高さを表し、次に数塔をN行の数字で表し、i行目にi個の整数があり、すべての整数が区間[0,99]内にある.Outputは、各テストインスタンスについて、出力可能な最大和であり、各インスタンスの出力が1行を占める. 
Sample Input 5 7 3 8 8 1 0  2 7 4 4 4 5 2 6 5 Sample Output 30  
DPを使わなければ、DFSを使うこともできますが、メモリを消費します.DPでやるには状態を探す必要があります.
現在i番目,j番目に進むと,現在の状態はi,jから最下層の最大ノードとなり,初期条件が最下層のdp配列が彼自身であることが容易に考えられる.
次に状態遷移を見る:i,jノードに着いて、私たちは2つの選択があります:1.左下へ行く.理論上の状態遷移方程式を右下に進むと決定される
すなわち、dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])である.しかし問題が発生し、dp[i+1]の層の状況を知らなかった.
そのため初期条件を合わせると,底から上へ行くことが考えられる.
#include
#include
#include
using namespace std;
const int maxn = 100;
int dp[maxn][maxn];
int g[maxn][maxn];
int t;

int main()
{
    scanf("%d",&t);
    for(int i=0;i=0;i--)
    {
        for(int j=0;j<=i;j++)
        {
            dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+g[i][j];
        }
    }
    printf("%d",dp[0][0]);
    return 0;
}