2 篇有 "dynamic programming" 標籤的文章
最大子數列問題 (Maximum Subarray Problem) 及 Kadane's Algorithm
給定 A = [a0, a1, …, an-1]，如何使得 slice 的和 sum(A[p], A[p+1], …, A[q]) 有最大值 (slice長度可以為0) ？有個知名的 Kadane’s Algorithm 可以解決這個問題。 目錄 Kadane’s…
Read more →Min Abs Sum
給定A = [a0, a1, …, an-1]，如何找到一組S = [s0, s1, … sn-1], sj ∈ {-1, 1}, 使得abs(sum(ai * si))有最小值？關鍵在於對於 A 中的每個元素 a 能夠產生的 sum…
Read more →