算法提高 数的划分(动态规划)
问题描述
一个正整数可以划分为多个正整数的和，比如n=3时：
3；1＋2；1＋1＋1；
共有三种划分方法。
给出一个正整数，问有多少种划分方法。
输入格式
一个正整数n
输出格式
一个正整数，表示划分方案数
样例输入
3
样例输出
3
思路：
本题的意思就是用数的和组成一个n问有多少种可以，我们可以把他当作背包题，当n为这么多的时候有多少种装法，反之我们就知道1-n就是我们可以取的值范围。下面的i表示我当前可以取的数，j表示当时n为多少。我们知道当取的数比j大时我们就保持原来的次数，当i小于等于时，我们就可以取他的数那么转移方程就得本身数+dp[j-i]，dp[j]+=dp[j-i]。因为我们可以取一样的数，所以我们就没有必要取原来的次数，所以我们让for循环的j我正推就行了。
程序：
z=int(input())
dp=[0 for i in range(z+1)]
dp[0]=1
for i in range(1,z+1): #我当时去的数
for j in range(i,z+1): #当前的值
dp[j]+=dp[j-i]
print(dp[z])
禁止转载。仅用于自己学习。对程序错误不负责。
