首页 > 代码库 > 相加之和为某个数n,求方法数 ------------ 动态规划的方法
相加之和为某个数n,求方法数 ------------ 动态规划的方法
uva11137 n3可转化为n2(立方和为n的方法数)
/* ID: neverchanje PROG: LANG: C++11 */ #include<iostream> #include<cstring> #include<cstdio> typedef long long ll; using namespace std; int n; long long d[23][maxn]; //下标<=21 int main(){ memset(d,0,sizeof(d)); d[0][0]=1; for(int i=1;i<22;i++) for(int j=0;j<=10000;j++){//注意j不能超过10001,否则会出错(不知道怎么回事) if(j-i*i*i>=0) d[i][j] += d[i][j-i*i*i]; d[i][j] += d[i-1][j]; } while(cin>>n) printf("%lld\n",d[21][n]); return 0; } /* DESCRIPTION: d(i,j)为下标不超过i的立方和为j的方法数 d(i,j) = sum( d(i-1,j-k*i^3) ) 答案是d(21,n) 注意: 由于j要从0开始,所以转移方程要有所改变 d(i,j+k*i^3) = sum( d(i-1,j) ) */
poj2140 (计算和为n的方法数) 其实这道题有更好的方法
/* ID: neverchanje PROG: LANG: C++11 */ #include<iostream> using namespace std; int res=1,N; void dp(int a,int i){ //a<i的情况可排除 if(a==i) res++; else if(a>i) dp(a-i,i+1); } int main(){ cin>>N; for(int i=1;i<=N/2+1;i++) //i<=n/2+1会漏掉一个解:N本身,所以res初始化为1 dp(N,i); cout<<res<<endl; return 0; } /* DESCRIPTION: 几个连续的数之和为N 可以用dp dp(a,i)表示以i为开头的,和为a的连续子序列的数量 dp(a,i) = dp(a-i,i+1) (a>=i) 边界: i<j 都有 dp(i,j)=0; 用记忆化搜素会更高效一些 复杂度应该是O(n*sqrt(n))的,但实际上应该少的多 */
暂时只有这两题,但是方法各不相同,怕混淆,做个笔记
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。