典型ナップサックを1次元配列で解く。

※一番PV数が多いので、ちょっと直しました(2020/5/24)

例題として、 B - 書き換え（Rewrite）を使います。
まずはこのコードを見てください。　

#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    cin >> N >> M;
    vector<int>V(N),T(N);
    for(int i = 0; i < N; ++i){
        cin >> V[i] >> T[i];
    }
    vector<int>dp(M + 1,0);
    for(int i = 0; i < N; i++)
        for(int t = M; t >= 0;t--){
            if(t + T[i] <= M)
                dp[t + T[i]] = max(dp[t + T[i]], dp[t] + V[i]);
        }
    cout << *max_element(dp.begin(), dp.end()) << endl;
    
}

シンプルですね。時間計算量はですが、空間計算量はで少しお得です。

まずは2次元で考える。

二次元DPで考えると、
個目の書類を見ている時に,時間使ったときの最大値
　という漸化式になります。

さて、この問題を1次元配列で解くことを考えます。
時間のときの最大の価値
つまり、どの書類を見ているか、という情報を捨てます。

以下が工夫するポイントです。

後ろ向きに更新する

時間を後ろからなめて、次のように更新します。

for(int t = M; t >= 0; --t)

嬉しいポイントは、値の更新がすでに見たに対して行われます。つまり、番目の書類を重複して更新されることがありません。

荷物を取らない推移ないけど？

必要無いからです。2次元DPの際は,番目の書類まで見た結果を番目にも反映させる必要があるますが、この場合はありません。