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

明天蓝桥杯了，希望能争二保三吧

题目：
将 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;
} 


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
 

记忆化搜索题解来自这篇

文章来源: blog.csdn.net，作者：开心星人，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_55675216/article/details/125332281