首页 > 代码库 > 算法训练 数的划分
算法训练 数的划分
http://lx.lanqiao.cn/problem.page?gpid=T84
dp[i][j] 将i分成j份的方法数
不考虑顺序,则要么包含1 要么不含1
dp[i-j][j] j份每个都给1 在把剩下的i-j分成j份 则不会再出现1
#include <bits/stdc++.h> using namespace std; typedef pair<int,int> ii; const int inf=1e9; const int N=2e2+20; int n,k; int dp[N][N];// int main() { while(cin>>n>>k) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][1]=1; dp[0][0]=1; for(int i=2;i<=n;i++) { for(int j=1;j<=min(i,k);j++) { dp[i][j]=dp[i-j][j]+dp[i-1][j-1]; } } cout<<dp[n][k]<<endl; } return 0; }
算法训练 数的划分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。