算法入門經典大賽 Dynamic Programming

111 - History Grading LCS

103 - Stacking Boxes 最多能疊多少個box DAG最長路

10405 - Longest Common Subsequence LCS

674 - Coin Change 全然背包求方案數 

10003  - Cutting Sticks 區間DP dp[l][r]代表分割l到r的最小費用

116 - Unidirectional TSP 簡單遞推 輸出字典序最小解 從後往前推

10131 - Is Bigger Smarter? DAG的最長路

10066 -

The Twin Towers LCS

10192 - Vacation LCS

147 - Dollars 全然背包求方案數 

357 - Let Me Count The Ways 全然背包求方案數

562 - Dividing coins 全部物品之和除以2為背包體積做01背包

348 - Optimal Array Multiplication Sequence 矩陣鍊乘+輸出解

624 - CD 01背包+輸出解

10130 - SuperSale 01背包

531 - Compromise LCA

10465 - Homer Simpson 全然背包

10285 - Longest Run on a Snowboard 滑雪 經典記憶化搜尋

437 - The Tower of Babylon 最長上升序列 LIS

10404 - Bachet's Game 全然背包

？620 - Cellular Structure 

825 - Walking on the Safe Side 直接左上到右下

10069 - Distinct Subsequences 大數+dp

dp[i][j]為第一個字元長度為i 出現第二個字元串0-j-1子串的數量

dp[i][j] = dp[i-1][j] if(s[i]==s[j]) dp[i][j] += dp[i-1][j-1]

10534 - Wavio Sequence LIS

正反兩次二分+LIS

10051-Tower of Cubes 記憶化搜尋吧

好像還是搭積木

10651 - Pebble Solitaire 爆搜

590 - Always on the run

dp[i][j]為第i天到達j城市的最小值

10306 - e-Coins 全然背包

dp[i][j] 為 橫坐标為i縱坐标為y的最小數量 最後求i*i+j*j=s*s的最小的dp[i][j]

10739 - String to Palindrome 最少操作幾次變成回文串

10304 - Optimal Binary Search Tree 區間dp

花費最少的二叉樹 一顆二叉樹的權值是全部點的權值*深度在求和

dp[i][j] =  dp[i][k-1]+dp[k+1][j] + a[i]+a[i+1]+...+a[j]-a[k]

10271 - Chopsticks dp[i][j]前i根筷子選出j對的最小值

10617 - Again Palindrome 求回文串數目

if(a[i]==a[j]) dp[i][j] = dp[i][j-1]+dp[i+1][j] 否則 dp[i][j] = dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1];

11137 - Ingenuous Cubrency 全然背包

10201 - Adventures in Moving - Part IV

？10154 - Weights and Measures

10453 - Make Palindrome 最少改動次數邊回文+輸出回文

？10029 - Edit Step Ladders

10313 - Pay the Price 背包變形

dp[i][j] 用j個硬币表示i面值的方案數 dp[i][j] += dp[i-w][j-1] w為目前枚舉的某一種面值硬币

10401 - Injured Queen Problem dp[i][j]代表(i, j)位置放皇後的方案數

10891 - Game of Sum 博弈dp 區間dp

11151 - Longest Palindrome

10911 - Forming Quiz Teams 狀态壓縮dp

10635 - Prince and Princess LCS轉LIS