以下哪个C++代码片段可以正确计算将正整数4拆分为若干不计顺序的正整数之和的方案数?

uk156307 单选题 共 个子题

整数拆分指将正整数分解为若干正整数的和,不计顺序且允许重复使用数字。例如正整数4的拆分方案共有5种:1+1+1+1、1+1+2、1+3、2+2、4。

A
int countSplit(int n) {
    int dp[5][5] = {0};
    // 边界条件初始化
    for(int j = 0; j <= n; j++) dp[0][j] = 1;
    for(int i = 1; i <= n; i++) dp[i][0] = 0;
    // 动态规划递推
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(j > i) dp[i][j] = dp[i][i];
            else dp[i][j] = dp[i][j-1] + dp[i-j][j];
        }
    }
    return dp[n][n];
}
B
int countSplit(int n) {
    int dp[5][5] = {0};
    // 错误的边界初始化
    for(int j = 0; j <= n; j++) dp[0][j] = 0;
    for(int i = 1; i <= n; i++) dp[i][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(j > i) dp[i][j] = dp[i][i];
            else dp[i][j] = dp[i][j-1] + dp[i-j][j];
        }
    }
    return dp[n][n];
}
C
int countSplit(int n) {
    int dp[5] = {0};
    dp[0] = 1;
    // 有序拆分的递推逻辑
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= i; j++) {
            dp[i] += dp[i-j];
        }
    }
    return dp[n];
}
D
int countSplit(int n) {
    int dp[5][5] = {0};
    for(int j = 0; j <= n; j++) dp[0][j] = 1;
    for(int i = 1; i <= n; i++) dp[i][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(j > i) dp[i][j] = dp[i][i];
            else dp[i][j] = dp[i][j-1] + dp[i-j][j-1];
        }
    }
    return dp[n][n];
}
正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧