题目如下:有一个全是正整数的数组a,现要求构造一个数组b,并满足以下要求:1.全为正整数2.a,b数组元素和相同3.同一位置出元素不相同,即a[i] != b[i]问总共有多少种可能情况能够满足上述要求。我做的python解法如下:def func(nums):    n = len(nums)    total = sum(nums)    #dp[i][j]表示前i个数拼凑出j的可能数    dp = [[0]*(total+1) for _ in range(n+1)]        #初始化,前0个数拼凑出0的可能数是1    dp[0][0] = 1        for i in range(1,n+1):        for j in range(i,total+1):            cnt = 0            #前i个数拼凑出j的可能数依赖于前i-1个数拼凑出1,2……j-1的情况            #还要保证当前这个数和nums中的数不一样,即(j-x) != nums[i-1]            for x in range(j):                 if dp[i-1][x] and (j-x) != nums[i-1]:                     cnt += dp[i-1][x]            dp[i][j] = cnt      return dp[-1][-1]print(func([2,1,2])) #只有一种可能,1,3,1
点赞 2
评论 0
全部评论

相关推荐

群星之怒:不是哥们,你就不好奇瘫痪三十年的老植物人是啥样的吗?
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务