原题：https://ac.nowcoder.com/acm/contest/24213/1018

解法一：朴素递归，从后往前，从抽象到边界，记忆化搜索，反推（递归）
解法二：动态规划_01背包，从前往后，从边界到抽象，正推（递推）
两种解法是完全相反的过程

解法一（递归）：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <time.h>
#include <iomanip>
#include <cctype>
#include <string>
using namespace std;
typedef long long ll;
const ll Mod = 1e9 + 7;//https://ac.nowcoder.com/acm/contest/24213/1018

int val[110];//价值
int tim[1010];//时间
int rec[110][1010];//记忆化,记录f(i,j)

//从后往前递归，记录最优子结构避免重复计算(记忆化)，，，倒过来就是动规
//f(i,j)采前i个草药，剩余j时间，此时能得到的最大价值
//f(i,j)=max(f(i-1,j),f(i-1,j-tim[i])+val[i])    *max(不采第i株，采第i株)
//f(0,j)=0  *边界
int f(int i,int j){
    if(i==0) return 0;
    if(rec[i][j]>0) return rec[i][j];//f[i][j]算过了就不用算了
    if(tim[i]>j) 
        rec[i][j]=f(i-1,j);
    else
        rec[i][j]=max(f(i-1,j),f(i-1,j-tim[i])+val[i]);
    return rec[i][j];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t,n;cin>>t>>n;
    for(int i=1;i<=n;i++)
        cin>>tim[i]>>val[i];
    cout<<f(n,t)<<endl;
    return 0;
}

解法二（dp）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <time.h>
#include <iomanip>
#include <cctype>
#include <string>
using namespace std;
typedef long long ll;
const ll Mod = 1e9 + 7;//https://ac.nowcoder.com/acm/contest/24213/1018

int val[110];//价值
int tim[1010];//时间
int dp[110][1010];

//从前往后正推，，，，倒过来就是递归
//dp[i][j] 采前i个草药，剩余j时间,此时能得到的最大价值
//状态转移方程 dp[i][j]=max(dp[i-1][j],dp[i-1][j-tim[i]]+val[i])    *max(不采第i株，采第i株)
//dp[0][]=0  *边界

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t,n;cin>>t>>n;
    for(int i=1;i<=n;i++)
        cin>>tim[i]>>val[i];
    
    for(int i=1;i<=n;i++){
        for(int j=t;j>=0;j--){
            if(tim[i]>j) dp[i][j]=dp[i-1][j];
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-tim[i]]+val[i]);
        }
    }

    cout<<dp[n][t]<<endl;
    return 0;
}