相信很多人和我一样刚开始一直不懂最后一个递推式。
q(n, m)表示:整数n按照“分出来的数”不大于m的分法有多少种。
可以看出q(6,2)可以分为两种情况,一是加数不包含2的部分,这部分也是家数都小于2的部分。还有一部分是包含2的,那么可以先将2给拿出来,然后继续拼接。
如果是q(n,m),可以分为包含m的部分即m**拼接**q(n-m,m)。和加数都小于等于m的即q(n,m-1)。
加下来上代码:
#include<iostream>using namespace std;int divide(int n,int m)
{if (n == 0) return 1;if (n < 0 || m == 0) return 0;if (n == 1 || m == 1) return 1;else if(n<m) return divide(n,n);else if(n==m) return (1 + divide(n,n-1));else return (divide(n-m,m) + divide(n,m-1));
}int main()
{int n;cin>>n;cout<<divide(n,n)<<endl;return 0;
}
这里为什么不和函数一模一样呢?
仔细看树,就知道了。
这里还可以进行记忆化搜索,我就不写了。