我正在尝试复习动态规划的一些注释和示例，但我很难弄清楚它是如何工作的。我将发布问题，然后发布我遇到的困难:
Given a sequence of points p1= (x1,y1),...,pn=(xn,yn) sorted from left to right (ie, x1 < x2 < ... < xn) and a number k between 1 and n, find a polygonal chain from p1 to pn with k edges that goes from left to right, minimizing the sum of the vertical distances of the points to the chain. Design dynamic programming algorithm that solves the problem in O(n^3) time. Set the subproblems, give all base cases necessary, calculate recursive formula, and write pseudocode for the algorithm. Also a function f(a,b) is defined for us to use in calculating the vertical difference, so I dont have to worry about implementing that. I can just use it as f(a,b)
我认为子问题应该这样划分:
C[i,j] = 从 p1 到 pi 的具有 j 条边的多边形链，最小化垂直距离的总和。
那么答案就是:C[n,k]
基本情况:C[i,0] = 0
现在我在想出递归公式时遇到了一些困难。我的第一个问题，我是否正确地分解了子问题？这个问题给出了一个暗示，使它看起来像我做的，但我不是 100% 确定。如果我是，关于如何继续推导递归公式的任何提示？
感谢大家的帮助。
最佳答案
你的子问题是正确的，但我认为稍微改变一下公式可以帮助你得出公式:
与其让 C(i, j) 表示从 1 到 i 有 j 条边的任何链，不如让它具体表示“以 i 结尾的链”。然后，要确定 C(i, j) 的答案，您只需尝试最后一条边开始的所有可能性。
那么答案可以是所有C(i, k)中的最优。
关于algorithm - 动态规划递归公式，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11422087/