@：
@Date：2020/7/7
人生最重要的不是所站的位置，而是內心所朝的方向。只要我在每篇博文中寫得自己體會，修煉身心；在每天的不斷重復學習中，耐住寂寞，練就真功，不畏艱難，奮勇前行，不忘初心，砥礪前行，人生定會有所收獲，不留遺憾 （作者： ）
作者介紹：目前大三下學期，專業化學工程與工藝，大學沉迷日語，， Java和一系列數據分析軟件。導致翹課嚴重，專業排名中下。.在大學60%的時間，都在CSDN。決定今天比昨天要更加努力。
前面文章，點擊下面鏈接
我的教程，不斷整理，反復學習
今天高考，當年我就是一個辣雞，現在還是一個辣雞，祝高考的個個清華北大 。辣雞的我決定繼續更新教程，今天就開始了八十五、 | 數據結構之圖和動態規劃算法系列。
圖
在計算機科學中，一個圖就是一些頂點的集合，這些頂點通過一系列邊結對（連接）。頂點用圓圈表示，邊就是這些圓圈之間的連線。頂點之間通過邊連接。
一個圖G = (V, E)由以下元素組成。
度
表示一個頂點又多少條邊
鄰接矩陣
在鄰接矩陣實現中，由行和列都表示頂點，由兩個頂點所決定的矩陣對應元素表示這里兩個頂點是否相連、如果相連這個值表示的是相連邊的權重。
還有 稀疏圖。 稀疏圖就是頂點多，但是每個頂點邊并不多
應用：微信號幾億的用戶，對應到圖上就好幾億的頂點，但是每個用戶的好友并不會很多，最多5000，如果用鄰接矩陣來存儲，那么存儲空間都被浪費了
鄰接表
鄰接矩陣存儲比較浪費時間，但是使用起來比較節省時間。相反鄰接表存儲起來比較節省空間，但是使用就比較浪費時間。
上圖是否存在一條從頂點2到頂點4的邊，就要遍歷頂點2對應的鏈表
動態規劃算法
先來看看生活中經常遇到的事吧——假設您是個土豪，身上帶了足夠的1、5、10、20、50、100元面值的鈔票。現在您的目標是湊出某個金額w，需要用到盡量少的鈔票。
依據生活經驗，我們顯然可以采取這樣的策略：能用100的就盡量用100的，否則盡量用50的……依次類推。在這種策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10張鈔票。
這種策略稱為“貪心”：假設我們面對的局面是“需要湊出w”，貪心策略會盡快讓w變得更小。能讓w少100就盡量讓它少100，這樣我們接下來面對的局面就是湊出w-100。長期的生活經驗表明，貪心策略是正確的。
但是，如果我們換一組鈔票的面值，貪心策略就也許不成立了。如果一個奇葩國家的鈔票面額分別是1、5、11，那么我們在湊出15的時候，貪心策略會出錯：
15=1×11+4×1 （貪心策略使用了5張鈔票） 15=3×5 （正確的策略，只用3張鈔票）
再從一個簡單的例子分析： 有 5 個物品，重量分別是 w = [1, 2, 3, 4, 5]； 對應的價值是 v = [1, 2, 4, 2, 5]； 背包容量 C = 10。
暴力法：對所有選擇的組合貪心算法 背包問題 c，算出每一種情況的總價值，比較即可得出答案。
遞歸法：對于每個物品都有選與不選的決策，即原問題可以分解成兩個子問題的比較。
假設有一個計算總價值的函數 F(n, c)，上述五個物品編號 i 為 1 ~ 5，c 是背包容量。 對于上例，第五個物品選擇與否，通過比較兩種子情況得到的價值大小來決定：
F(5, 10) = Max(F(4, 10) , F(4, 5) + 5)
故原問題有：
F(i, c) = Max( F(i-1, c), F(i-1, c - wi) + vi)
當然貪心算法 背包問題 c，如果背包剩余容量不足以容納下一個物品，則再將 i-1。
動態規劃：在遞歸的基礎上儲存已經求出的值。 當子問題重復出現時直接獲取儲存中的結果。 用一個 c*i 的二維數組儲存——
第64題：最小路徑和
#給定一個包含非負整數的?m?x?n?網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。?
#
#?說明：每次只能向下或者向右移動一步。?
#
#?示例:?
#
#?輸入:
#[
#??[1,3,1],
#??[1,5,1],
#??[4,2,1]
#]
#輸出:?7
#解釋:?因為路徑?1→3→1→1→1?的總和最小。
#?
#?Related?Topics?數組?動態規劃本題dp實現采用數組實現，因為只能向右或者向下移動，要走到走到在第ｉ行第ｊ列的網格，必須是從第ｉ-1行第ｊ列的網格或者第ｉ行第ｊ-1列的網格移動過來，假設二維數組dp[i][j]表示在第ｉ行第ｊ列的網格上的最小數字總和
初始化dp所有的元素均為0，在網格的第一行和第一列的所有路徑和應該都是固定的，因為都是向右或者向下移動
而當位置(i,j)處時，dp[i][j] = min(dp[i-1][j] +grid[i][j]，dp[i][j-1]++grid[i][j])，另外，二維數組是額外的輔助空間，如果將直接將原數組grid來存儲dp數組的結果，邊遍歷邊更新，對grid進行原地修改，可降低空間復雜度，如下．
from?typing?import?List
class?Solution:
????def?minPathSum(self,?grid:?List[List[int]])?->?int:
????????m?=?len(grid)
????????n?=len(grid[0])????????
????????#在網格的第一行和第一列的所有路徑和應該都是固定的，直接向右或者向下移動相加
????????for?i?in?range(1,m):
????????????grid[i][0]?+=?grid[i-1][0]
????????for?j?in?range(1,n):
????????????grid[0][j]?+=?grid[0][j-1]????????????
????????#非第一行和非第一列：
????????for?i?in?range(1,m):
????????????for?j?in?range(1,n):
????????????????grid[i][j]=?min(grid[i-1][j]?+?grid[i][j],?grid[i][j-1]?+?grid[i][j]?)
????????return?grid[-1][-1]
if?__name__?==?"__main__":
????s=Solution()
????t=[[1,3,1],
??????[1,5,1],
??????[4,2,1]]
????print(s.minPathSum(t))
#?result
7第70題：爬樓梯
#假設你正在爬樓梯。需要?n?階你才能到達樓頂。?
#?每次你可以爬?1?或?2?個臺階。你有多少種不同的方法可以爬到樓頂呢？?
#?注意：給定?n?是一個正整數。?
#?示例?1：?
#?輸入：?2
#輸出：?2
#解釋：?有兩種方法可以爬到樓頂。
#1.??1?階?+?1?階
#2.??2?階?
#?示例?2：?
#?輸入：?3
#輸出：?3
#解釋：?有三種方法可以爬到樓頂。
#1.??1?階?+?1?階?+?1?階
#2.??1?階?+?2?階
#3.??2?階?+?1?階
#?Related?Topics?動態規劃動態規劃：第一個想法就是利用遞推公式求解方法數。 分析這個題目：
即，該問題可以轉換為斐波那契數列問題
優化空間復雜度：其實每次計算 f(i) 的值，都只用了離它最近的兩個值，而沒有用數組中其他的值。
也就是說我們根本不需要用一個數組來存放，只需要用兩個變量來存放每次更新后最新得到的兩個值即可。
class?Solution:
????def?climbStairs(self,?n:?int)?->?int:
????????#?這里我們用prev?curr分別存放離當前臺階數最近的兩個臺階數對應的方法數。
????????curr?=?prev?=?1
????????for?_?in?range(n-1):
????????????curr,?prev?=?curr?+?prev,?curr
????????return?curr
class?Solution:
????def?climbStairs(self,?n,?s1?=?0,?s2?=?1):
????????return?n?and?self.climbStairs(n?-?1,?s2,?s1?+?s2)?or?s2第322題： 零錢兌換
#給定不同面額的硬幣?coins?和一個總金額?amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額，返回?-1。?
#?示例?1:?
#?輸入:?coins?=?[1,?2,?5],?amount?=?11
#輸出:?3?
#解釋:?11?=?5?+?5?+?1?
#?示例?2:?
#?輸入:?coins?=?[2],?amount?=?3
#輸出:?-1?
#?說明:?
#你可以認為每種硬幣的數量是無限的。?
#?Related?Topics?動態規劃動態規劃問題的一般形式就是求最值，求最值就是窮舉所有的可能性。
假設輸入不同面額的硬幣 coins = [coin1, coin2, coin3] , 總金額
采用貪心算法做法： 對于 [1,2,5] 組成 11 塊，排序[5,2,1]
因此結果是 3，但是貪心算法也有可能出錯。 就拿這道題目來說， 它也是不正確的！ 比如 coins = [1, 5, 11] amout = 15, 因此這種做法有時候不靠譜，我們還是采用靠譜的做法。
因此需要dp算法， 用dp[i] 來表示組成i塊錢，需要最少的硬幣數，那么第j個硬幣我可以選擇不拿 這個時候， 硬幣數 = dp[i]
第j個硬幣我可以選擇拿 這個時候， 硬幣數 = dp[i - coins[j]] + 1
和背包問題不同， 硬幣是可以拿任意個
對于每一個 dp[i] 我們都選擇遍歷一遍 coin， 不斷更新 dp[i]。
這算是一道比較經典的動態規劃題目了吧。關鍵是確定狀態轉移方程，如果當前組合dp[i]的個數小于另一i-1個組合+某一硬幣的組合，則需要更新該值，所以可以得到狀態轉移方程如下：
dp[i]?=?min(dp[i],dp[i-coin]+1)那么就可以很容易地寫出題解。
class?Solution:
????def?coinChange(self,?coins:?List[int],?amount:?int)?->?int:
????????dp?=?[amount?+?1]?*?(amount?+?1)
????????dp[0]?=?0
????????for?i?in?range(1,?amount?+?1):
????????????for?j?in?range(len(coins)):
????????????????if?i?>=?coins[j]:
????????????????????dp[i]?=?min(dp[i],?dp[i?-?coins[j]]?+?1)
????????return?-1?if?dp[-1]?==?amount?+?1?else?dp[-1]