题解 | #Redraiment的走法#

方法：

1. 递归法：超时，思路非常简单，就是对每个当前桩子now，计算所有高于它的桩子开始到之后能走的step中的最大step。然后加上当前桩子的step：1
2. 动态规划：使用一个一维dp表，表值记录每个桩子的step。然后从第二个桩子开始遍历，对遍历桩子i的所有之前的桩子j，当高度大于之前的桩子，那么step就取dp[i]和dp[j]+1中的较大值。最后取dp表中的最大值作为输出

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;

// 递归法，超时
int Step(vector<int> following, int now){
    int len = size(following);
    if(len == 0)
        return 1;
    int count = 1;
    int max_step = 0;
    for(int i = 0; i < len; i ++){
        if(following[i] > now){
            vector<int> sub;
            sub.assign(following.begin()+i+1, following.end());
            int step = Step(sub, following[i]);
            if(max_step < step) max_step = step;
        }
    }
    count += max_step;
    return count;

}

// 动态规划
int Step2(vector<int> piles){
    int len = size(piles);

    vector<int> dp(len, 1);
    int max = 0;
    // 从第二个桩子开始遍历，对于之前所有比它矮的桩子，取自身所处的步数（即dp记录的值）和之前桩子步数+1中更大的那个作为新步数
    for(int i = 1; i < len; i ++){
        for(int j = 0; j < i; j ++){
            if(piles[i] > piles[j]){
                dp[i] = dp[i]>dp[j]+1? dp[i]:dp[j]+1;
            }
        }
        // 每个桩子更新完最大step
        max = max>dp[i]?max:dp[i];
    }

    return max;
}

int main() {
    int num = 0;
    cin >> num;
    std::vector<int> store;

    for(int i = 0; i < num; i ++){
        int dt = 0;
        cin>>dt;
        store.push_back(dt);
    }

    int step = Step2(store);
    cout << step << endl;

    // int max_step = 0;
    // for(int i = 0; i < num; i ++){
    //     vector<int> sub;
    //     int now = store[i];
    //     sub.assign(store.begin()+i+1, store.end());
    //     int step = Step(sub,now);
    //     if(max_step < step)
    //         max_step = step;
    // }
    // cout << max_step << endl;

}
// 64 位输出请用 printf("%lld")