思路：下降<=>上升

两种思路： 一. 1.递推中要确定最后一列的积木数量，就一定要直到前一个符合要求的方案最后一列的积木数量， 所以用[n块][m列][k最后一列数量]记录

求递推关系式，考虑最后一列，若最后一列使用的方块数<k，如从1,2,3,...,k-1，所有的方案数加起来等价于(n,m,k-1)

若最后一列使用的方块数=k(>k就不是这个数组元素了)，那么就是最后一列用了k个方块=>先把前面m-1列摆好(n-k,m-1,k-1)

故[n][m][k]=[n][m][k-1]+[n-k][m-1][k-1]

int a[]          //j->m;i->n;k->隐式
a[0][0]=1//空排列也是一种排列
for(int k=1;k<=n;++k)//最终计算的相当于[n][m][k],为所需要的
for(int j=m;j>0;--j)//j从大到小,a[j][i]=a[j][i]+a[j-1][i-k];
//所以每个j-1都是后更新的，残留的是k-1；j=0时如果i>0，方案数为0，即默认初始化为0
for(int i=n;i>=k;--i)//n-k>=0
{
    a[j][i]+=a[j-1][i-k];  
}
>

二.依然用[n块][m列]记录 考虑拆分成子问题 第一列为1时，移除后列数减少。 第一列大于1时，移除后列数不变，但积木减少。 递归所有可能情况，判断边界条件。

a[n][m]=a[n-m][m-1]+a[n-m][m];

AC代码：

#include<iostream>
const int N=100,M=10;//N->个数,M->列数
using namespace std;
int dp[M+1][N+1];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int t,n,m,i,j;cin>>t;
    dp[0][0]=1;
    for(j=1;j<=M;++j)
    {
        for(i=(j*(j+1))>>1;i<=N;++i) //这里相当于等差数列求和，严格单增要有m列，最少也是有(1+2+3+4+...+m)块
		{dp[j][i]=dp[j-1][i-j]+dp[j][i-j];}
    }
    while(t--)
    {
        cin>>n>>m;
        cout<<dp[m][n]<<'\n';
    }
    return 0;
}

拓展1：要是问n个积木，分成m垛，这些积木垛排成一行，使得所有垛的积木块数不相同，且呈“山“字形（积木数先单调上升，再单调下降）。比如6块积木，分成3垛，只有132,231两种方案。怎么办？

思考了半天，其实并不需要重新想递推式。只要微调前面得出的结果即可

#include<cmath>
cout<<(long long)(dp[m][n])*(long long)(pow(2,m-1)-2)<<'\n';
//相当于已经严格单增，除了最高（最后）那一列可以交换到它关于最后一列对称的位置
//乘法原理2**(m-1)，但是如果全交换或全不交换又回到以前，所以排除这两种

数据过大的话要用long long算乘法

拓展2：你有n个积木块，堆成一排，共m列，要求每列都必须有积木，且每列上积木的数量不一样。如果你有6块积木，堆成3列，可以堆成“123”，“132”，“213”，“231”，“312”，“321”,一共六种。求方案数。

有了拓展1的铺垫这个就好想了。严格递增只是限定了顺序，并没有限定每列积木的数量，而且严格单增还保证了各列积木数不同，这下只要考虑n个数乱排，全排列Ann=n!;

long long fac[11]={1,1,2,6,24,120,720,5040,40320,362880,3628800};
cout<<(long long)(dp[m][n])*fac[m]<<'\n';