鸣人的影分身

递归

https://www.acwing.com/solution/content/8444/

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25;
int t,n,m;

int f(int n,int m)
{
    if(n == 0) return 1;
    if(m == 0) return 0;
    //苹果数量 《 盘子数量
    if(n < m) return f(n,n);
    //苹果数量 》= 盘子数量（可以分类讨论）
    else{
        //盘子都放 + 盘子有的不放
        return f(n-m,m) + f(n,m-1);
    }
}

int main(void)
{
    cin >> t;
    while(t --){

        cin >> n >> m;
        cout << f(n,m) << endl; 
    }
    return 0;
}

线性DP

算法1基础上的DP思考（非闰式DP法）

C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25;
int t,n,m;
int f[N][N];

int main(void)
{
    cin >> t;
    while(t --)
    {
        cin >> n >> m;
        for(int i = 0;i <= n;i ++)
            for(int j = 0;j <= m;j ++){
                //苹果数 < 盘子数
                if(i < j)  f[i][j] = f[i][i];  //递归中先进行判断再运行语句，此处就是先运行语句，对于运行的语句最后判断，也就是和递归的差别
                if(i >= j) f[i][j] = f[i-j][j] + f[i][j-1];
                //            1每个盘子放一个苹果，其他位置分苹果
                //            2一个盘子不放苹果                     
                if(j == 0) f[i][j] = 0;
                if(i == 0) f[i][j] = 1;

            }
        cout << f[n][m] << endl;
    }
    return 0;
}