動態編程遞歸公式

Question

我正在嘗試去看一些筆記和動態編程的例子，並且我在理解它是如何工作的時候遇到了一些困難。我將發佈這個問題，然後我會遇到困難：

給定從左到右排序的點序列p1 =（x1，y1），...，pn =（xn，yn） （即，x1 < x2 < ... < xn）和介於1和n之間的數字k，找到從p1到pn的多邊形鏈，k邊從左到右，最小化點的垂直距離的總和連鎖店。設計解決O（n^3）時間問題的動態規劃算法。設置子問題，給所有必要的基本情況，計算遞歸公式，併爲算法編寫僞代碼。還有一個函數f（a，b）被定義爲我們用來計算垂直差異，所以我不必擔心它的實現。我可以只使用它爲f（A，B）

相信子問題應被劃分爲這樣：

C [I，J] =從P1多邊形鏈到pi其中j邊緣最小化垂直距離的總和。

然後答案是：C [N，K]

基例：C [I，0] = 0

現在我有想出的遞歸公式的一些困難。我的第一個問題，我是否正確地打破了子問題？這個問題提供了一個讓我看起來像我一樣的暗示，但我不是100％確定的。如果我是，有關如何繼續推導遞歸公式的提示？

感謝任何幫助傢伙。

Answer 1

你的子問題是正確的，但我認爲在制定一個小變化可以幫助你拿出公式：

而不必C(i, j)意味着從1任鏈我的J邊緣，使其特指「以i結尾的鏈條」。然後，爲了確定C(i, j)的答案，你只需要嘗試所有可能的最後的邊緣開始。

然後答案可以是所有的最佳C(i, k)。