一个正整数N可以分解为M(M>1)个正整数的和,即N=K+L,例如N=5、M=2时可以分解为(1+4,2+3)。
给定一个正整数N(1<N<200)及正整数M(1<M<200),求有多少种可能的分解组合(注:K+L和L+K算一种)
N, K = list(map(int,input().strip(' ').split(','))) dic = {} def recur(N,K): if N==K&nbs***bsp;N==K+1&nbs***bsp;K==1: return 1 if K == 2: return (N//2) res = 0 for i in range(1,min(N-K,K)+1): if (N-K,i) in dic: res += dic[(N-K,i)] else: res += recur(N-K,i) dic[(N,K)] = res return res print(recur(N,K))
N, M = list(map(int,input().strip(' ').split(','))) dic = {} def DP(n,m): """ n-----目前有的数 m-----目前的次数 n-m---剩余需要处理的数 """ global dic if n == m or n - m == 1 or m == 1: dic[(n,m)] = 1 return if m == 2 and n >= m: dic[(n,m)] = int(n // 2) return i = 1 res = 0 while i <= n-m and i <= m: if (n-m,i) in dic: res += dic[(n-m,i)] i += 1 else: DP(n-m,i) dic[(n,m)] = res return DP(N,M) print(dic[(N,M)])
data= [int(x) for x in input().split(',')] N=data[0] K=data[1] def Data(data,min_,k): if k==1: if data>=min_: return 1 else: return 0 else: temp=0 for i in range(min_,data//k+1): temp+=Data(data-i,i,k-1) return temp print(Data(N,1,K))感觉应该用动态规划,理解了一下楼里大佬的,稍稍修改,另外加了注释。就100%通过了
data= [int(x) for x in input().split(',')] N=data[0] K=data[1] def Data(data,k): #k拆分 if data<k: return 0 #楼里大佬的问题,没判断无法划分的问题。。。 else: if k==1: return 1 else: D={} D[0,0]=0 for i in range(1,data+1): for j in range(1,min(i+1,k+1)): if j==1: D[i,j]=1 else: D[i,j]=D[i-1,j-1] #D[i,j]=D[i-j,j]+D[i-1,j-1] if i>=2*j: #意思是分割有两种情况:不包含1和包含1,当然可能不一定包含1 D[i,j]+=D[i-j,j] return D[data,k] print(Data(N,K))
n,m = map(int, input().split(",")) dic = {} def loop(n, m): if (m == 1)&nbs***bsp;(n - m == 1)&nbs***bsp;(n == m): dic[(n, m)] = 1 elif m == 2: dic[(n, m)] = int( n / 2) else: left, i, total = n - m, 1, 0 while left >= i and i <= m: if (left, i) in dic.keys(): total = total + dic[(left, i)] i = i + 1 else: loop(left, i) dic[(n, m)] = total loop(n,m) print(dic[(n,m)])