C++动态规划二层循环 | #Redraiment的走法#

因为把返回值误认为dp[N-1]而报错，因为最大值不一定在最后一步。

第一反应就是动态规划，dp[i]指走到第i个桩子时走过的最长递增步数。

每一步只能跟前一步比较决定要不要+1，需要获得走前一步时走过的最大步数，每一步都要遍历寻找之前的最大步数，一次循环无法解决，所以二层。

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

int stepN(vector<int> h, int N){
    vector<int> dp(N, 1);
    int res = dp[0];
    for(int i = 1; i < N; i ++){
        for(int j = 0; j < i; j ++){
            if(h[j] < h[i]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        res = dp[i] > res ? dp[i] : res;
    }

    return res;
}

int main() {
    int N;
    cin >> N;
    vector<int> h(N);
    for(int i = 0; i < N; i++) cin >> h[i];

    cout << stepN(h, N);

    return 0;
}