<dp入门>01背包之金矿模型

二十天之前写的题，现在完全不记得思路了。
碰见dp题宕机不说，还瞎指鹿为马，气煞我也，一个期中考试回到解放前。
所以回来吃掉你了

题目链接：
https://www.acoj.com/problems/12098

AC代码：

#include<stdio.h>       
#include<string.h>
int n,m;                                        //m个人参与挖矿，共n座矿
int A[105],B[105],dp[105][1005];                //A表示该矿挖掘需要人数,B表示该矿可得金子数 

int max(int a,int b)
{
    return a>b?a:b; 
} 

int f(int i,int j)                              //i是第i座金矿,j是该矿可得金子数
{
    int ans;
    if(dp[i][j]!=-1)
        return dp[i][j];                            //dp记忆化搜索 
        
    if(i==n)
        ans=0;          //return 0; 
    
    else if(A[i]>j)
        ans=f(i+1,j);
    else
        ans=max(f(i+1,j),f(i+1,j-A[i])+B[i]);       //max(dp[i+1][j],dp[i+1][j-A[i]]+B[i]);
    
    dp[i][j]=ans;                               //dp记忆化搜索 
    return ans; 
} 

int main()
{
    scanf("%d%d",&m,&n);
    
    memset(dp,-1,sizeof(dp)); 
    for(int i=0;i<n;i++) 
        scanf("%d%d",&A[i],&B[i]); 
    
    printf("%d",f(0,m));
}