区間dp

問題

徐々に探索幅を広げていく

( 端を取り除きdpに格納 + より広い区間でdpが最大値となる組み合わせ ) の繰り返し

//ボトムアップ(for文)
int dp[310][310]; //それぞれの区間の最大個数
int w[310];


int main() {

    int n; //個数
    cin >> n;

    rep(i, 0, n)rep(j, 0, n) dp[i][j] = 0;

    rep(i, 0, n) cin >> w[i]; //重さ


    for (int W = 1;W < n;W++) // 探索幅
    {
        //left
        for (int l = 0;l < n;l++) // 区切る位置
        {
            int r = l + W;
            if (r >= n) continue;

            //端を除いたすべてが取り除ける(必須) && 端が取り除ける
            if (dp[l + 1][r - 1] == W - 1 && abs(w[l] - w[r]) <= 1)
            {
                dp[l][r] = W + 1;
            }
            //探索幅におけるすべてのパターン
            for (int mid = l;mid <= r;mid++) // 探索幅を二等分した区間の和の最大値
            {
                dp[l][r] = max(dp[l][r], dp[l][mid] + dp[mid + 1][r]);
            }
        }
    }
    cout << dp[0][n - 1] << endl;
}

//再帰
int dp[310][310]; //それぞれの区間の最大個数
int w[310];

//区間 l ～ r で取り除ける数
int rec(int l, int r) {

    //既に計算済みか？(区間で分けた片方で使用)
    if (dp[l][r] != -1) return dp[l][r]; //メモ化再帰

    //これ以上取り除けない？(1つしかない場合)
    if (abs(l - r) == 0) return 0;

    int res = 0; //取り除ける数

    //端が取り除ける && 端を除いたすべてが取り除ける(必須) 
    if (abs(w[l] - w[r]) <= 1 && rec(l + 1, r - 1) == r - l - 1)
    {
        res = r - l + 1;
    }

    //探索幅におけるすべてのパターン
    for (int mid = l; mid < r; mid++)
    {
        res = max(res, rec(l, mid) + rec(mid + 1, r));
    }
    
    return dp[l][r] = res;
};


int main() {

    int n; //個数
    cin >> n;

    rep(i, 0, n)rep(j, 0, n) dp[i][j] = -1;

    rep(i, 0, n) cin >> w[i]; //重さ

    cout << rec(0, n - 1) << endl;
    
}