动态规划之整数拆分

问题描述:

? ? ? ? ? ? ? ? 将整数n拆分为将其拆分为至少两个正整数的和,且拆分的最大数为k,求解所有的拆分情况

示例:

? ? ? ? ? ? ? ? n =? 5, k = 5时的拆分方案:

? ? ? ? ? ? ? ? 5 = 5

? ? ? ? ? ? ? ? 5 = 4 + 1

? ? ? ? ? ? ? ? 5 = 3 + 2?

? ? ? ? ? ? ? ? 5 = 3? + 1 + 1

? ? ? ? ? ? ? ? 5 = 2? + 2 + 1

? ? ? ? ? ? ? ? 5 = 2 + 1 + 1 + 1?

? ? ? ? ? ? ? ? 5 = 1 + 1 + 1 + 1 + 1

代码:

#include <iostream>
using namespace std;

const int N = 110;
int dp[N][N];

// 使用动态规划求解整数拆分的方案数
int getAns(int n, int k) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (i == 1 || j == 1)
                dp[i][j] = 1;
            else if (i < j)
                dp[i][j] = dp[i][i]; // 最大数超过当前数字个数时，与当前数字个数相同
            else if (i == j)
                dp[i][j] = dp[i][j - 1] + 1; // 最大数等于当前数字个数时，加上一个最大数即可
            else if (i > j)
                dp[i][j] = dp[i - j][j] + dp[i][j - 1]; // 其他情况的状态转移方程
        }
    }
    return dp[n][k];
}

int main() {
    int n, k;
    cin >> n >> k;
    
    cout << getAns(n, k);
    
    return 0;
}

? ? ? ? ??