Kadane算法的動態編程方面

Initialize: 
    max_so_far = 0 
    max_ending_here = 0 

Loop for each element of the array 
    (a) max_ending_here = max_ending_here + a[i] 
    (b) if(max_ending_here < 0) 
     max_ending_here = 0 
    (c) if(max_so_far < max_ending_here) 
      max_so_far = max_ending_here 
return max_so_far

任何人都可以幫助我理解最佳子結構和重疊問題（麪包和黃油的DP）我上面的算法嗎？Kadane算法的動態編程方面

來源

2013-05-01 Bhavish Agarwal

Kadane的算法很貪心，IIRC。 – nhahtdh 2013-05-01 18:25:40

+1，我一直在努力。我無法確定它是否被視爲DP：我們有最佳的子結構，但沒有重疊的子問題。我已經看到它被標記爲DP，但嚴格來說，我會說它不是。 – IVlad 2013-05-01 18:26:45

無法找到某人具有和我一樣的問題;） – 2015-10-17 03:03:55

據重疊子問題this定義，Kadane的算法（f[i] = max(f[i - 1] + a[i], a[i])）的遞歸製劑不表現出這種特性。每個子問題只能在幼稚的遞歸實現中計算一次。

它不會根據其定義here但是表現出最優子：我們使用的解決方案，以更小的子問題，以便找到解決我們給定的問題（f[i]使用f[i - 1]）。

考慮動態規劃定義here：

在數學，計算機科學，經濟學，動態規劃是通過將它們分解成更簡單的子問題解決複雜問題的方法。它適用於展現重疊子問題1和最優子結構（下面描述）的性質的問題。在適用的情況下，該方法比沒有利用子問題重疊的樸素方法（如深度優先搜索）花費的時間少得多。

動態規劃背後的想法很簡單。一般來說，要解決一個給定的問題，我們需要解決問題的不同部分（子問題），然後結合子問題的解決方案來達到一個整體解決方案。通常當使用更天真的方法時，許多子問題都會生成並解決許多次。動態規劃方法尋求解決每個子問題只有一次，從而減少計算

這留下解釋的餘地，以Kadane的算法是否能夠被認爲是DP算法的數字：它打破解決問題它變成了更容易的子問題，但其核心遞歸方法不會產生重疊的子問題，這就是DP要有效處理的問題 - 所以這會使其不屬於DP的專業。另一方面，你可以說基本的遞歸方法不需要導致重疊的子問題，但是這會使得任何遞歸算法成爲DP算法，這會給DP在我的範圍上太寬泛意見。然而，我並沒有意識到文學中的任何東西肯定會解決這個問題，所以我不會以任何方式標記學生或對書籍或文章置之不理。

所以我會說這不是一個DP算法，只是一個貪婪和/或遞歸的，取決於實現。由於上面列出的原因，我會從算法的角度將其標記爲貪婪，但客觀上我會考慮其他解釋同樣有效。

來源

2013-05-01 18:43:03 IVlad

有趣的是，它只涉及兩個存儲元素。這再次使它不像典型的DP算法。你知道有哪些算法被認爲是DP，只需要很少的存儲空間？ – 2013-05-01 20:58:45

@PeterdeRivaz - 斐波那契復發將會計數：它具有最佳的子結構和重疊的子問題，也可以用'O（1）'記憶來實現。 – IVlad 2013-05-01 21:56:05

Kadane算法的動態編程方面

回答

相關問題