有一家搬家公司。它在两个城市运营。他们希望最大化利润。给定的是代表两个城市的2个数组。每个数组中位置i的值表示当天该城市要赚取的最大利润。如果他们在第i天在城市A中工作，在第i + 1天在城市B中工作，则在两个城市c之间旅行会产生成本。我们需要使用动态编程来找到最大的收益。这是一个例子：
A = {10, 20, 30}
B = {-10, 50, 20}
c = 20
optimal solution = (10 + (50 - 20) + 20) = 10 + 30 + 20 = 60
我认为这类似于加权间隔计划或子集和问题（背包）。任何帮助表示赞赏。
编辑：
我需要找到递归关系，算法的时间复杂度，然后证明其正确性。有什么想法吗？
为了更好地表示这个问题，
A是利润矩阵，其中A[c]是城市c的利润数组（第一个城市为c = 0，第二个城市为c = 1，依此类推）。 P(i, c)成为直到i天（含）的最佳利润，以使搬家公司最终在c天进入城市i。 C(c', c)是从城市c'迁移到城市c的成本。 此设置使我们可以将解决方案推广到任意数量的城市。
为了最大化P(i, c)，我们必须考虑搬家者在前一天i-1可能位于的所有可能的城市，然后选择最大选项。这些可能性包括搬家者在前一天在同一个城市，并且在前一天从另一个城市搬家而产生搬家费用。因此
P(i, c) = max(P(i-1, c), max(P(i-1, c') + C(c', c) for all cities c' != c)) + A[c][i]
外部max（P(i-1, c)）中的第一个参数考虑搬家者前一天在同一城市，而第二个参数（内部max）评估并最大化利润（包括搬家费用）（如果搬家者前一天在另一个城市。
[最终答案就是max(P(n, x) for all cities x)，其中n是最后一天（考虑到搬家可能在最后一天结束的所有可能的城市）。
在您的示例中，城市A ==城市0，城市B ==城市1，利润矩阵A = [[10, 20, 30], [-10, 50, 20]]和C(0, 1) = C(1, 0) = 20。
编辑：
时间复杂度将为O(nc)，其中n是天数，c是城市数。如果城市数量固定，则时间复杂度为O(n)。
可以通过归纳证明正确性。假设P(i-1, x)对于所有城市x都是最大值。然后证明上述定义的某个城市P(i, c)的c最大。最大解决方案有两种可能性：
c天在同一城市i-1中>c'天位于另一个城市i-1。现在您需要显示的是，在上述两种情况下，上面定义的重复周期都将为您提供正确的解决方案。
我认为您可以在这里简单地使用自下而上的DP。
您需要DP解决方案，但我认为贪婪的方法更适合此问题。这是贪婪的解决方案：