整数分解(记忆化搜索、排列组合)

题目：
将 3 分解成两个正整数的和，有两种分解方法，分别是 3 = 1 + 2 和 3 = 2 + 1。注意顺序不同算不同的方法。
将 5 分解成三个正整数的和，有 6 种分解方法，它们是 1+1+3 = 1+2+2 = 1+3+1 = 2+1+2 = 2+2+1 = 3+1+1。
请问，将 2021 分解成五个正整数的和，有多少种分解方法？

排列组合解法
2020个位置，选4个
C⁴₂₀₂₀

记忆化搜索
f[i][j] 表示用i个数凑出j的方案数（即将j分解成i个正整数的和有多少种分解方法）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[10][2100];
ll dfs(int i,int j){
	if(f[i][j]!=-1){
		return f[i][j];
	}
	if(!i)
	{
		if(!j) return 1;
		return 0;
	}
	f[i][j]=0;
	for(int n=1;n<=j;n++){
		f[i][j]+=dfs(i-1,j-n);		
	}
	return f[i][j];
	
	
}
int main(){
	memset(f,-1,sizeof(f));
	cout<<dfs(5,2021)<<endl;
	cout<<f[5][2021]<<endl;
	return 0;
} 

记忆化搜索题解来自这篇