首页 > 其他 > 详细

900. 整数划分(动态规划)

时间:2020-08-18 20:24:17      阅读:101      评论:0      收藏:0      [点我收藏+]

技术分享图片

 

 方法一: 背包模型

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, mod = 1e9 + 7;
int dp[N][N];
int n;

int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) dp[i][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(j >= i) {
                dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % mod;
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    printf("%d\n",dp[n][n]);
    return 0;
}

方法二:

#include <bits/stdc++.h>
using namespace std;

const int N = 10010, mod = 1e9 + 7;
int dp[N][N];
int n;

int main() {
    scanf("%d",&n);  // dp[i][j]:总数为i,分为j组的方案数
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
                        // 两种集合划分
                        //有1         // 没有1
            dp[i][j] = (dp[i-1][j-1] + dp[i-j][j]) % mod;
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++) res = (res + dp[n][i]) % mod;
    printf("%d\n",res);
    return 0;
}

 

900. 整数划分(动态规划)

原文:https://www.cnblogs.com/yonezu/p/13525593.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!