算法入门经典大赛 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