Python 代码实现正整数划分：允许重复元素和不允许重复元素

Python 代码实现正整数划分：允许重复元素和不允许重复元素\n\n本文介绍了使用动态规划的方法用 Python 代码实现正整数划分问题，并区分了允许包含相同元素和不允许包含相同元素的两种情况。代码示例展示了如何计算划分个数和生成具体的划分情况。\n\n问题描述：\n\n将正整数 n 表示成一系列正整数之和：n = n1 + n2 + … + nk，其中 n1 ≥ n2 ≥ … ≥ nk ≥ 1，k ≥ 1。正整数 n 的这种表示称为正整数 n 的划分。\n\n代码实现：\n\npython\ndef partition_with_duplicates(n):\n # 初始化动态规划数组\n dp = [[0] * (n+1) for _ in range(n+1)]\n dp[0][0] = 1\n\n # 动态规划求解\n for i in range(1, n+1):\n for j in range(1, i+1):\n dp[i][j] = dp[i-j][j] + dp[i-1][j-1]\n\n # 构造划分情况\n partitions = []\n def generate_partitions(target, current):\n if target == 0:\n partitions.append(current)\n else:\n for i in range(min(target, current[-1]), 0, -1):\n generate_partitions(target-i, current + [i])\n\n generate_partitions(n, [n])\n\n return dp[n][n], partitions\n\ndef partition_without_duplicates(n):\n # 初始化动态规划数组\n dp = [[0] * (n+1) for _ in range(n+1)]\n dp[0][0] = 1\n\n # 动态规划求解\n for i in range(1, n+1):\n for j in range(1, i+1):\n dp[i][j] = dp[i-j][j-1] + dp[i-1][j-1]\n\n # 构造划分情况\n partitions = []\n def generate_partitions(target, current, start):\n if target == 0:\n partitions.append(current)\n else:\n for i in range(start, min(target, current[-1]), -1):\n generate_partitions(target-i, current + [i], i)\n\n generate_partitions(n, [n], n-1)\n\n return dp[n][n], partitions\n\nn = int(input("请输入一个正整数："))\n\ncount_with_duplicates, partitions_with_duplicates = partition_with_duplicates(n)\ncount_without_duplicates, partitions_without_duplicates = partition_without_duplicates(n)\n\nprint("在允许包含相同元素下，拆分种数：", count_with_duplicates)\nprint("具体情况：")\nfor partition in partitions_with_duplicates:\n print("+\".join(map(str, partition)))\n\nprint("在不允许包含相同元素下，拆分种数：", count_without_duplicates)\nprint("具体情况：")\nfor partition in partitions_without_duplicates:\n print("+\".join(map(str, partition)))\n\n\n代码解释：\n\n1. 动态规划数组： 使用二维数组 dp 存储动态规划的结果。dp[i][j] 表示将正整数 i 表示成一系列不大于 j 的正整数之和的划分个数。\n2. 动态规划求解： 使用两个嵌套循环计算 dp 数组的值。\n3. 构造划分情况： 使用递归函数 generate_partitions 生成具体的划分情况。\n\n代码运行示例：\n\n输入：6\n\n输出：\n\n在允许包含相同元素下，拆分种数： 11\n具体情况：\n6\n5+1\n4+2\n4+1+1\n3+3\n3+2+1\n3+1+1+1\n2+2+2\n2+2+1+1\n2+1+1+1+1\n1+1+1+1+1+1\n\n在不允许包含相同元素下，拆分种数： 4\n具体情况：\n6\n5+1\n4+2\n3+2+1\n\n总结：\n\n本文介绍了使用动态规划的方法用 Python 代码实现正整数划分问题，并区分了允许包含相同元素和不允许包含相同元素的两种情况。代码示例展示了如何计算划分个数和生成具体的划分情况。\n\n更多信息：\n\n如果您想了解更多关于动态规划算法的信息，可以参考以下资源：\n\n* 维基百科：动态规划\n* MIT OpenCourseware：动态规划\n* LeetCode：动态规划\n\n希望本文对您有所帮助！