algorithm - 如何在动态规划算法中进行转换？

Question

假设我们有以下问题:

一条街上有m个地方:

p1,p2,...,pm (each place has a weight)

我们可以在哪里放置 k 家商店:

s1,s2,...,sk (each store has a weight).

在 pj 位置放置商店 si 需要花费:

k(si,pj)=si*pj.

如何设计一种动态规划算法来解决这个问题:

以总成本 SUM(k(si,pj)) 最小的方式放置所有商店 + 商店必须按顺序放置，即存储 s4 到位置 p2 和 s2 到位置 p5 是无效的!

我正在尝试考虑递归的解决方案。因为有了递归的解法，将算法转化为动态规划算法应该是'容易'的(这个不用解释)。但我什至无法弄清楚如何用递归解决这个问题(例如，如何将其拆分为子问题？)。有人可以给我提示吗？

Answer 1

这是一种使用递归的解决方案。有一种方法可以不放置商店。否则，可以通过将第一家商店放置在所有可能的位置来枚举放置选项，并且对于第一家商店的每个放置，枚举其余商店的所有放置选项。在 Python 中(未经测试):

def mincost(s, i, p, j):  # min cost of placements of stores i.. in places j..
    if i == len(s):
        return 0  # no stores remaining
    else:
        least = float('inf')  # infinity, i.e., infeasible
        for k in range(j, len(p)):  # all places for store i
            least = min(least, s[i] * p[k] + mincost(s, i + 1, p, k + 1))
        return least

print(mincost(s, 0, p, 0))  # root call

现在，通过缓存由 i 和 j(s 和 p 不要改变)。