Leetcode 3343. Count Number of Balanced Permutations

• Leetcode 3343. Count Number of Balanced Permutations
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3343. Count Number of Balanced Permutations

1. 解题思路

这一题整体思路上就是一个动态规划，不过整体怎么进行动态规划坦率地说是看了下答案搞定的，有点惭愧……

不过从答案来反过来看就感觉非常显然了，就是分别考察奇偶位置上从0到9各自分配多少个数，对应有多少种分配方法，然后最后两边的差是否为0即可。

我们使用一个delta参数来记录两边的差，然后分配的个数就是一个循环遍历，然后分配方法就是$C_n^i$。

然后，我们将其转换成代码语言即可。

2. 代码实现

给出python代码实现如下：

MOD = 10**9+7

factorials = [1 for i in range(41)]
for i in range(2, 41):
    factorials[i] = (i * factorials[i-1]) % MOD
    
revs = [1 for i in range(41)]
for i in range(2, 41):
    revs[i] = pow(factorials[i], -1, mod=MOD)
    
@lru_cache(None)
def C(n, i):
    return (factorials[n] * revs[i] * revs[n-i]) % MOD

class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        
        cnt = Counter(num)
        odd, even = len(num) - len(num)//2, len(num)//2
        
        @lru_cache(None)
        def dp(idx, delta, odd, even):
            if idx == 10:
                return 1 if delta == 0 else 0
            n, m = odd, even
            k = cnt[str(idx)]
            ans = 0
            for i in range(k+1):
                if i > n or k-i > m:
                    continue
                ans = (ans + C(n, i) * C(m, k-i) * dp(idx+1, delta + idx * (i*2-k), odd-i, even-k+i)) % MOD
            return ans
        
        return dp(0, 0, odd, even)

提交代码评测得到：耗时2195ms，占用内存113.7MB。