算法篇之動态規劃

動态規劃（dynamic programming，dp）是運籌學的一個分支，是求解[決策過程最優化]的方法。

把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創立了解決這類過程優化問題的新方法——動态規劃

雖然動态規劃主要用于求解以時間劃分階段的動态過程的優化問題，但是一些與時間無關的靜态規劃(如線性規劃、非線性規劃)，

隻要人為地引進時間因素，把它視為多階段決策過程，也可以用動态規劃方法友善地求解。

在現實生活中，有一類活動的過程，由于它的特殊性，可将過程分成若幹個互相聯系的階段，在它的每一階段都需要作出決策，進而使整個過程達到最好的活動效果。是以各個階段決策的選取不能任意确定，它依賴于目前面臨的狀态，又影響以後的發展。當各個階段決策确定後，就組成一個決策序列，因而也就确定了整個過程的一條活動路線．這種把一個問題看作是一個前後關聯具有鍊狀結構的多階段過程就稱為多階段決策過程，這種問題稱為多階段決策問題。在多階段決策問題中，各個階段采取的決策，一般來說是與時間有關的，決策依賴于目前狀态，又随即引起狀态的轉移，一個決策序列就是在變化的狀态中産生出來的，故有“動态”的含義，稱這種解決多階段決策最優化的過程為動态規劃方法

動态規劃算法通常用于求解具有某種最優性質的問題。在這類問題中，可能會有許多可行解。每一個解都對應于一個值，我們希望找到具有最優值的解。動态規劃算法與分治法類似，其基本思想也是将待求解問題分解成若幹個子問題，先求解子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，适合于用動态規劃求解的問題，經分解得到子問題往往不是互相獨立的。若用分治法來解這類問題，則分解得到的子問題數目太多，有些子問題被重複計算了很多次。

動态規劃（英語：dynamic programming，簡稱 dp）是一種在數學、管理科學、計算機科學、經濟學和生物資訊學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

動态規劃常常适用于有重疊子問題和最優子結構性質的問題，并且記錄所有子問題的結果，是以動态規劃方法所耗時間往往遠少于樸素解法。

動态規劃有自底向上和自頂向下兩種解決問題的方式。自頂向下即記憶化遞歸，自底向上就是遞推。

使用動态規劃解決的問題有個明顯的特點，一旦一個子問題的求解得到結果，以後的計算過程就不會修改它，這樣的特點叫做無後效性，求解問題的過程形成了一張有向無環圖。動态規劃隻解決每個子問題一次，具有天然剪枝的功能，進而減少計算量。

從上面的定義中可以知道使用動态規劃的場景特征： 

求一個問題的最優解 

大問題可以分解為子問題，子問題還有重疊的更小的子問題 

 整體問題最優解取決于子問題的最優解（狀态轉移方程） 

從上往下分析問題，從下往上解決問題 

讨論底層的邊界問題

動态規劃最重要的有三個概念：

最優子結構：是指每個階段的最優狀态可以從之前某個階段的某個或某些狀态直接得到(子問題的最優解能夠決定這個問題的最優解),

邊界：指的是問題最小子集的解(初始範圍)

狀态轉移方程：是指從一個階段向另一個階段過度的具體形式,描述的是兩個相鄰子問題之間的關系(遞推式)

https://leetcode-cn.com/problems/maximum-subarray/

https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/23/dynamic-programming/54/

給定一個整數數組 <code>nums</code> ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]

輸出：6

解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。

示例 2：

輸入：nums = [1]

輸出：1

示例 3：

輸入：nums = [0]

輸出：0

示例 4：

輸入：nums = [-1]

輸出：-1

示例 5：

輸入：nums = [-100000]

輸出：-100000

提示：

1 &lt;= nums.length &lt;= 3 * 104

-105 &lt;= nums[i] &lt;= 105