美团第二场测试笔试第三道题

题目如下：有一个全是正整数的数组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