阿里笔试动态规划

参考博客 https://blog.csdn.net/qwb492859377/article/details/50654627

昨天是阿里网络笔试，实验室有一兄弟参加了，今天聊了聊发现有一个题特别有意思特别有启发，故拿出来表一表。

问题描述

题目大意是这样的：有 m 个鱼丸 n 个肉丸，将它们放到 k 个碗中有多少种放法。

要求：碗可以为空；碗的空间可以视为无限；鱼丸和肉丸不能放到同一个碗中；丸子之间碗之间没有区别。

取值范围： 1 <= m,n,k <= 50

求解

一看到这个问题感觉很像高中的排列组合问题，假设有一个函数 f(x, y) 可以计算出将 x 个丸子放到 y 个碗中所有放法，那么这道题就迎刃而解了:

def solution(m, n, k):
    res = 0
    for i in range(1, k):
        res += f(m, i) * f(n, k-i)
        res += f(n, i) * f(m, k-i)
    return res 

所以现在问题是写出函数 f(x, y)。最开始是想着用递归来做：

def f(x, y):
    if y == 0:
        return 0
    if x <= 1:
        return 1
    pass

两个特殊情况很容易写出来：如果碗的个数为0显然无解返回0；如果丸子个数小于等于1，那么只有1中放法，返回1。然而关键部分的代码却理不清了，考虑用穷举法来做，即第一个碗里可以放 0 ~ x 个，那么第二个碗，第三个碗…… 且不考虑复杂度，问题在于不能解决重复问题，以2个丸子放2个碗举例 (0, 2) 和 (2, 0) 是一样的。问题进入瓶颈。

参考逍遥丶綦的博客发现，我们可以通过是否有空碗对所有情况进行分类。有空碗和无空碗是对立的，可以直接想加，不存在重叠也就是重复的问题。那么函数pass部分可以这样写：

f(x, y) = f(x, y-1) + f(x-y, y)

f(x, y-1) 即将 x 个丸子放到 y-1 个碗中，保证空碗的存在；而 f(x-y, y) 即不存在空碗的情况下，y个碗中至少都要有一个丸子，然后我们把剩下的 x-y 个丸子放到碗中即可。当然这里要考虑 x 和 y 的大小关系，如果 x-y < 0 的话等式的第二部分直接赋0即可。

写到这里就发现，可以用动态规划来做，上述等式即为状态转移方程。

可以写出代码：

def solution(m, n, k):
    res = 0
    m, n = max(m, n), min(m, n)
    dp = [[0] * (k + 1) for _ in range(m + 1)]
    # 初始化
    for i in range(1, k + 1):
        dp[0][i] = 1
        dp[1][i] = 1
    for i in range(1, m + 1):
        dp[i][1] = 1
    # 构造动态规划数组
    for i in range(2, m + 1):
        for j in range(1, k + 1):
            dp[i][j] = dp[i][j - 1] + (dp[i - j][j] if i - j >= 0 else 0)
    print(dp)
    for i in range(1, k):
        # 控制空碗
        res += (dp[n][i] - dp[n][i - 1]) * (dp[m][k - i])
    return res

特别需要注意的是控制空碗，即 res += (dp[n][i] - dp[n][i - 1]) * (dp[m][k - i]) ，保证空碗只在放肉丸的时候出现，否则会出现重复。

问题描述

求解

FEATURED TAGS

FRIENDS