递归和动态规划裸题分析

递归和动态规划

裸题如下：

https://www.luogu.com.cn/problem/P1060

递归

递归的思路如下：

1. 思考递归边界。
2. 确定最后应该向上层返回什么东西（例如这里向上层返回的就是权重值）
3. 思考应该做什么重复的事(例如这里就是对是否买玩具做判断)。
4. 思考应该向下面传递什么参数(例如这里就是（玩具数组索引，兜里剩的钱，当前已经攒了多少权重）)

完成以上思路很轻松就能写出以下代码。

import java.util.*;
public class Main{
    static int N,m;
    static int v[],w[];
    static int _get(int deep,int money,int value){
        if(deep==-1){
            return value;
        }
        if(money<v[deep]){
            return _get(deep-1, money, value);
        }  
        int l = _get(deep-1, money, value);
        int r = _get(deep-1, money-v[deep], value+w[deep]);
        
        return r>l?r:l;
    }
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        N = sc.nextInt();
        v=new int[N+5];
        w=new int[N+5];
        for(int i=0;i<N;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt()*v[i];
        }
        
        System.out.println(_get(N, m, 0));
    }
}

DP:

动态规划的思路如下：

1. 确定每个可能遇到的状态 例如这道题就是确定遇到f(n,m)时的状态，当并将每个值保存到f[n][m]的二维数组中。每个f(n,m)的意义是兜里还有m块钱，想买玩具已经规划到第n个了，
2. 确定每个可能遇到的状态 如何找到上一个状态例如f[i][j]的上一个状态可能就是f[i-1][j]
3. 确定状态转移方程这道题的状态转移方程就是：f[i][j]=max(f[i-1][j]，f[i-1][j-v[i]]+w[i]);

import java.util.*;
public class P1060{
    static int n,m;
    static int v[],w[];
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        n = sc.nextInt();
        v=new int[n+5];
        w=new int[n+5];
        int[][] f=new int[n+5][m+5];
        for(int i=1;i<=n;i++){
            v[i] = sc.nextInt();
            w[i] = sc.nextInt()*v[i];
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                //买不起
                if(j<v[i]){
                    f[i][j] = f[i-1][j];
                }
                else{
                    f[i][j] = f[i-1][j]>f[i-1][j-v[i]]+w[i]?
                    f[i-1][j]:f[i-1][j-v[i]]+w[i];
                }
            }
        }
        System.out.println(f[n][m]);
    }
}