All Public Dynamic Programming (DP) Problems at LeetCode

#	Title	Difficulty	Category	Sub-Category
70	Climbing Stairs	Easy	1.Linear DP
121	Best Time to Buy and Sell Stock	Easy	1.Linear DP
746	Min Cost Climbing Stairs	Easy	1.Linear DP
1025	Divisor Game	Easy	1.Linear DP
123	Best Time to Buy and Sell Stock III	Hard	1.Linear DP
552	Student Attendance Record II	Hard	1.Linear DP
639	Decode Ways II	Hard	1.Linear DP
982	Triples with Bitwise AND Equal To Zero	Hard	1.Linear DP
1235	Maximum Profit in Job Scheduling	Hard	1.Linear DP
1326	Minimum Number of Taps to Open to Water a Garden	Hard	1.Linear DP
1359	Count All Valid Pickup and Delivery Options	Hard	1.Linear DP
1406	Stone Game III	Hard	1.Linear DP
1416	Restore The Array	Hard	1.Linear DP
1449	Form Largest Integer With Digits That Add up to Target	Hard	1.Linear DP
1510	Stone Game IV	Hard	1.Linear DP
91	Decode Ways	Medium	1.Linear DP
96	Unique Binary Search Trees	Medium	1.Linear DP
198	House Robber	Medium	1.Linear DP
279	Perfect Squares	Medium	1.Linear DP
309	Best Time to Buy and Sell Stock with Cooldown	Medium	1.Linear DP
322	Coin Change	Medium	1.Linear DP
338	Counting Bits	Medium	1.Linear DP
343	Integer Break	Medium	1.Linear DP
357	Count Numbers with Unique Digits	Medium	1.Linear DP
376	Wiggle Subsequence	Medium	1.Linear DP
416	Partition Equal Subset Sum	Medium	1.Linear DP
646	Maximum Length of Pair Chain	Medium	1.Linear DP
714	Best Time to Buy and Sell Stock with Transaction Fee	Medium	1.Linear DP
740	Delete and Earn	Medium	1.Linear DP
790	Domino and Tromino Tiling	Medium	1.Linear DP
935	Knight Dialer	Medium	1.Linear DP
983	Minimum Cost For Tickets	Medium	1.Linear DP
1043	Partition Array for Maximum Sum	Medium	1.Linear DP
1105	Filling Bookcase Shelves	Medium	1.Linear DP
1218	Longest Arithmetic Subsequence of Given Difference	Medium	1.Linear DP
1262	Greatest Sum Divisible by Three	Medium	1.Linear DP
879	Profitable Schemes	Hard	2.Knapsack
956	Tallest Billboard	Hard	2.Knapsack
1388	Pizza With 3n Slices	Hard	2.Knapsack
1402	Reducing Dishes	Hard	2.Knapsack
213	House Robber II	Medium	2.Knapsack
474	Ones and Zeroes	Medium	2.Knapsack
494	Target Sum	Medium	2.Knapsack
638	Shopping Offers	Medium	2.Knapsack
650	2 Keys Keyboard	Medium	2.Knapsack
801	Minimum Swaps To Make Sequences Increasing	Medium	2.Knapsack
1626	Best Team With No Conflicts	Medium	2.Knapsack
188	Best Time to Buy and Sell Stock IV	Hard	3.Multi Dimensions DP
321	Create Maximum Number	Hard	3.Multi Dimensions DP
403	Frog Jump	Hard	3.Multi Dimensions DP
410	Split Array Largest Sum	Hard	3.Multi Dimensions DP
514	Freedom Trail	Hard	3.Multi Dimensions DP
871	Minimum Number of Refueling Stops	Hard	3.Multi Dimensions DP
920	Number of Music Playlists	Hard	3.Multi Dimensions DP
1220	Count Vowels Permutation	Hard	3.Multi Dimensions DP
1289	Minimum Falling Path Sum II	Hard	3.Multi Dimensions DP
1320	Minimum Distance to Type a Word Using Two Fingers	Hard	3.Multi Dimensions DP
1335	Minimum Difficulty of a Job Schedule	Hard	3.Multi Dimensions DP
1411	Number of Ways to Paint N × 3 Grid	Hard	3.Multi Dimensions DP
1420	Build Array Where You Can Find The Maximum Exactly K Comparisons	Hard	3.Multi Dimensions DP
1444	Number of Ways of Cutting a Pizza	Hard	3.Multi Dimensions DP
1473	Paint House III	Hard	3.Multi Dimensions DP
1575	Count All Possible Routes	Hard	3.Multi Dimensions DP
120	Triangle	Medium	3.Multi Dimensions DP
377	Combination Sum IV	Medium	3.Multi Dimensions DP
576	Out of Boundary Paths	Medium	3.Multi Dimensions DP
688	Knight Probability in Chessboard	Medium	3.Multi Dimensions DP
799	Champagne Tower	Medium	3.Multi Dimensions DP
813	Largest Sum of Averages	Medium	3.Multi Dimensions DP
931	Minimum Falling Path Sum	Medium	3.Multi Dimensions DP
1024	Video Stitching	Medium	3.Multi Dimensions DP
1027	Longest Arithmetic Subsequence	Medium	3.Multi Dimensions DP
1140	Stone Game II	Medium	3.Multi Dimensions DP
1155	Number of Dice Rolls With Target Sum	Medium	3.Multi Dimensions DP
1223	Dice Roll Simulation	Medium	3.Multi Dimensions DP
1621	Number of Sets of K Non-Overlapping Line Segments	Medium	3.Multi Dimensions DP
132	Palindrome Partitioning II	Hard	4.Interval DP
312	Burst Balloons	Hard	4.Interval DP
546	Remove Boxes	Hard	4.Interval DP
664	Strange Printer	Hard	4.Interval DP
903	Valid Permutations for DI Sequence	Hard	4.Interval DP
1000	Minimum Cost to Merge Stones	Hard	4.Interval DP
1478	Allocate Mailboxes	Hard	4.Interval DP
1547	Minimum Cost to Cut a Stick	Hard	4.Interval DP
1563	Stone Game V	Hard	4.Interval DP
375	Guess Number Higher or Lower II	Medium	4.Interval DP
413	Arithmetic Slices	Medium	4.Interval DP
486	Predict the Winner	Medium	4.Interval DP
647	Palindromic Substrings	Medium	4.Interval DP
877	Stone Game	Medium	4.Interval DP
1039	Minimum Score Triangulation of Polygon	Medium	4.Interval DP
1049	Last Stone Weight II	Medium	4.Interval DP
1130	Minimum Cost Tree From Leaf Values	Medium	4.Interval DP
1690	Stone Game VII	Medium	4.Interval DP
691	Stickers to Spell Word	Hard	5.bit DP
847	Shortest Path Visiting All Nodes	Hard	5.bit DP
1125	Smallest Sufficient Team	Hard	5.bit DP
1349	Maximum Students Taking Exam	Hard	5.bit DP
1434	Number of Ways to Wear Different Hats to Each Other	Hard	5.bit DP
1595	Minimum Cost to Connect Two Groups of Points	Hard	5.bit DP
1601	Maximum Number of Achievable Transfer Requests	Hard	5.bit DP
1655	Distribute Repeating Integers	Hard	5.bit DP
1659	Maximize Grid Happiness	Hard	5.bit DP
464	Can I Win	Medium	5.bit DP
698	Partition to K Equal Sum Subsets	Medium	5.bit DP
600	Non-negative Integers without Consecutive Ones	Hard	6.Digit DP
902	Numbers At Most N Given Digit Set	Hard	6.Digit DP
1012	Numbers With Repeated Digits	Hard	6.Digit DP
968	Binary Tree Cameras	Hard	7.DP on Trees
1373	Maximum Sum BST in Binary Tree	Hard	7.DP on Trees
1569	Number of Ways to Reorder Array to Get Same BST	Hard	7.DP on Trees
95	Unique Binary Search Trees II	Medium	7.DP on Trees
337	House Robber III	Medium	7.DP on Trees
1339	Maximum Product of Splitted Binary Tree	Medium	7.DP on Trees
1367	Linked List in Binary Tree	Medium	7.DP on Trees
1372	Longest ZigZag Path in a Binary Tree	Medium	7.DP on Trees
392	Is Subsequence	Easy	8.String DP
32	Longest Valid Parentheses	Hard	8.String DP
115	Distinct Subsequences	Hard	8.String DP
140	Word Break II	Hard	8.String DP
466	Count The Repetitions	Hard	8.String DP
472	Concatenated Words	Hard	8.String DP
730	Count Different Palindromic Subsequences	Hard	8.String DP
940	Distinct Subsequences II	Hard	8.String DP
1147	Longest Chunked Palindrome Decomposition	Hard	8.String DP
1278	Palindrome Partitioning III	Hard	8.String DP
1397	Find All Good Strings	Hard	8.String DP
1531	String Compression II	Hard	8.String DP
1639	Number of Ways to Form a Target String Given a Dictionary	Hard	8.String DP
131	Palindrome Partitioning	Medium	8.String DP
139	Word Break	Medium	8.String DP
467	Unique Substrings in Wraparound String	Medium	8.String DP
712	Minimum ASCII Delete Sum for Two Strings	Medium	8.String DP
1048	Longest String Chain	Medium	8.String DP
1405	Longest Happy String	Medium	8.String DP
808	Soup Servings	Medium	9.Probability DP
837	New 21 Game	Medium	9.Probability DP
1227	Airplane Seat Assignment Probability	Medium	9.Probability DP
53	Maximum Subarray	Easy	10.Classic DP	Cadane's Algorithm
152	Maximum Product Subarray	Medium	10.Classic DP	Cadane's Algorithm
898	Bitwise ORs of Subarrays	Medium	10.Classic DP	Cadane's Algorithm
978	Longest Turbulent Subarray	Medium	10.Classic DP	Cadane's Algorithm
1186	Maximum Subarray Sum with One Deletion	Medium	10.Classic DP	Cadane's Algorithm
1191	K-Concatenation Maximum Sum	Medium	10.Classic DP	Cadane's Algorithm
368	Largest Divisible Subset	Medium	10.Classic DP	Cadane's Algorithm
873	Length of Longest Fibonacci Subsequence	Medium	10.Classic DP	Cadane's Algorithm
10	Regular Expression Matching	Hard	10.Classic DP	LCS
44	Wildcard Matching	Hard	10.Classic DP	LCS
72	Edit Distance	Hard	10.Classic DP	LCS
97	Interleaving String	Hard	10.Classic DP	LCS
1092	Shortest Common Supersequence	Hard	10.Classic DP	LCS
1312	Minimum Insertion Steps to Make a String Palindrome	Hard	10.Classic DP	LCS
1458	Max Dot Product of Two Subsequences	Hard	10.Classic DP	LCS
5	Longest Palindromic Substring	Medium	10.Classic DP	LCS
516	Longest Palindromic Subsequence	Medium	10.Classic DP	LCS
718	Maximum Length of Repeated Subarray	Medium	10.Classic DP	LCS
1143	Longest Common Subsequence	Medium	10.Classic DP	LCS
354	Russian Doll Envelopes	Hard	10.Classic DP	LIS
960	Delete Columns to Make Sorted III	Hard	10.Classic DP	LIS
1187	Make Array Strictly Increasing	Hard	10.Classic DP	LIS
1671	Minimum Number of Removals to Make Mountain Array	Hard	10.Classic DP	LIS
1691	Maximum Height by Stacking Cuboids	Hard	10.Classic DP	LIS
300	Longest Increasing Subsequence	Medium	10.Classic DP	LIS
673	Number of Longest Increasing Subsequence	Medium	10.Classic DP	LIS
174	Dungeon Game	Hard	10.Classic DP	2D Grid Traversal
741	Cherry Pickup	Hard	10.Classic DP	2D Grid Traversal
1301	Number of Paths with Max Score	Hard	10.Classic DP	2D Grid Traversal
1463	Cherry Pickup II	Hard	10.Classic DP	2D Grid Traversal
1643	Kth Smallest Instructions	Hard	10.Classic DP	2D Grid Traversal
62	Unique Paths	Medium	10.Classic DP	2D Grid Traversal
63	Unique Paths II	Medium	10.Classic DP	2D Grid Traversal
64	Minimum Path Sum	Medium	10.Classic DP	2D Grid Traversal
1594	Maximum Non Negative Product in a Matrix	Medium	10.Classic DP	2D Grid Traversal
1706	Where Will the Ball Fall	Medium	10.Classic DP	2D Grid Traversal
303	Range Sum Query - Immutable	Easy	10.Classic DP	Cumulative Sum
85	Maximal Rectangle	Hard	10.Classic DP	Cumulative Sum
363	Max Sum of Rectangle No Larger Than K	Hard	10.Classic DP	Cumulative Sum
517	Super Washing Machines	Hard	10.Classic DP	Cumulative Sum
689	Maximum Sum of 3 Non-Overlapping Subarrays	Hard	10.Classic DP	Cumulative Sum
1074	Number of Submatrices That Sum to Target	Hard	10.Classic DP	Cumulative Sum
1537	Get the Maximum Score	Hard	10.Classic DP	Cumulative Sum
221	Maximal Square	Medium	10.Classic DP	Cumulative Sum
304	Range Sum Query 2D - Immutable	Medium	10.Classic DP	Cumulative Sum
764	Largest Plus Sign	Medium	10.Classic DP	Cumulative Sum
838	Push Dominoes	Medium	10.Classic DP	Cumulative Sum
1139	Largest 1-Bordered Square	Medium	10.Classic DP	Cumulative Sum
1277	Count Square Submatrices with All Ones	Medium	10.Classic DP	Cumulative Sum
1314	Matrix Block Sum	Medium	10.Classic DP	Cumulative Sum
1423	Maximum Points You Can Obtain from Cards	Medium	10.Classic DP	Cumulative Sum
1504	Count Submatrices With All Ones	Medium	10.Classic DP	Cumulative Sum
1664	Ways to Make a Fair Array	Medium	10.Classic DP	Cumulative Sum
523	Continuous Subarray Sum	Medium	10.Classic DP	Hashmap (SubArray)
1477	Find Two Non-overlapping Sub-arrays Each With Target Sum	Medium	10.Classic DP	Hashmap (SubArray)
1546	Maximum Number of Non-Overlapping Subarrays With Sum Equals Target	Medium	10.Classic DP	Hashmap (SubArray)
446	Arithmetic Slices II - Subsequence	Hard	11. DP + Alpha (Tricks/DS)
975	Odd Even Jump	Hard	11. DP + Alpha (Tricks/DS)
1425	Constrained Subsequence Sum	Hard	11. DP + Alpha (Tricks/DS)
1687	Delivering Boxes from Storage to Ports	Hard	11. DP + Alpha (Tricks/DS)
629	K Inverse Pairs Array	Hard	12.Insertion DP
943	Find the Shortest Superstring	Hard	13.Graph DP
787	Cheapest Flights Within K Stops	Medium	13.Graph DP
87	Scramble String	Hard	14.Memoization
1240	Tiling a Rectangle with the Fewest Squares	Hard	14.Memoization
1269	Number of Ways to Stay in the Same Place After Some Steps	Hard	14.Memoization
1340	Jump Game V	Hard	14.Memoization
1553	Minimum Number of Days to Eat N Oranges	Hard	14.Memoization
1654	Minimum Jumps to Reach Home	Medium	14.Memoization
1483	Kth Ancestor of a Tree Node	Hard	15. Binary Lifting
818	Race Car	Hard	16. Math
887	Super Egg Drop	Hard	16. Math
964	Least Operators to Express Number	Hard	16. Math
1363	Largest Multiple of Three	Hard	16. Math
1611	Minimum One Bit Operations to Make Integers Zero	Hard	16. Math
264	Ugly Number II	Medium	16. Math
1641	Count Sorted Vowel Strings	Medium	16. Math

 

POJ.1741 Tree

1.Problem
1741 -- Tree (poj.org)

2.Idea
Centroid Decomposition of Tree

3.Source

 struct edge {   
      int to, length;   
      edge(int x, int y) { to = x; length = y; }  
 };  
 int n, k;  
 vector<edge> G[10004];  
 bool centroid[10004];  
 int subtree_size[10004];  
 int ans;  
 void init(int n) {  
      REP(i, n) G[i].clear();  
 }  
 void add_edge(int a, int b, int c) {  
      G[a].push_back(edge( b, c ));  
      G[b].push_back(edge( a, c ));  
 }  
 int compute_subtree(int v, int p)  
 {  
      int c = 1;  
      for (int i = 0; i < G[v].size(); i++) {  
           int w = G[v][i].to;  
           if (w == p || centroid[w]) continue;  
           c += compute_subtree(G[v][i].to, v);  
      }  
      subtree_size[v] = c;  
      return c;  
 }  
 pair<int, int> search_centroid(int v, int p, int t)  
 {  
      pair<int, int> res = make_pair(INT_MAX, -1);  
      int s = 1, m = 0;  
      for (int i = 0; i < G[v].size(); i++) {  
           int w = G[v][i].to;  
           if (w == p || centroid[w]) continue;  
           res = min(res, search_centroid(w, v, t));  
           m = max(m, subtree_size[w]);  
           s += subtree_size[w];  
      }  
      m = max(m, t - s);  
      res = min(res, make_pair(m, v));  
      return res;  
 }  
 void enumarate_paths(int v, int p, int d, vector<int> &ds)  
 {  
      ds.push_back(d);  
      for (int i = 0; i < G[v].size(); i++) {  
           int w = G[v][i].to;  
           if (w == p || centroid[w]) continue;  
           enumarate_paths(w, v, d + G[v][i].length, ds);  
      }  
 }  
 int count_pairs(vector<int> &ds)  
 {  
      int res = 0;  
      sort(ds.begin(), ds.end());  
      int j = ds.size();  
      for (int i = 0; i < ds.size(); i++) {  
           while (j > 0 && ds[i] + ds[j - 1] > k) --j;  
           res += j - (j > i ? 1 : 0);  
      }  
      return res / 2;  
 }  
 void solve_subproblem(int v)  
 {  
      compute_subtree(v, -1);  
      int s = search_centroid(v, -1, subtree_size[v]).second;  
      centroid[s] = true;  
      for (int i = 0; i < G[s].size(); i++) {  
           if (centroid[G[s][i].to]) continue;  
           solve_subproblem(G[s][i].to);  
      }  
      vector<int> ds;  
      ds.push_back(0);  
      for (int i = 0; i < G[s].size(); i++) {  
           if (centroid[G[s][i].to]) continue;  
           vector<int> tds;  
           enumarate_paths(G[s][i].to, s, G[s][i].length, tds);  
           ans -= count_pairs(tds);  
           ds.insert(ds.end(), tds.begin(), tds.end());  
      }  
      ans += count_pairs(ds);  
      centroid[s] = false;  
 }  
 void solve()  
 {  
      while (scanf("%d %d", &n, &k), n) {  
           init(n);  
           REP(i, n - 1) {  
                int u, w, l;  
                scanf("%d %d %d", &u, &w, &l);  
                u--; w--;  
                add_edge(u, w, l);  
           }  
           ans = 0;  
           solve_subproblem(0);  
           printf("%d\n", ans);  
      }  
 }  

POJ.3260 The Fewest Coins

1.Problem
3260 -- The Fewest Coins (poj.org)

2.Idea
Knapsack problem. Reference

3.Source

 #include <cstdio>  
 #include <cstring>  
 const int maxn = 101, maxt = 10001, maxv = 121, INF = 0x3f3f3f3f;  
 int n, t, lim, v[maxn], c[maxn], que[maxt + maxv * maxv][2], l, r, f[maxt + maxv * maxv], g[maxv * maxv], ans;  
 int main()  
 {  
      scanf("%d%d", &n, &t);  
      for(int i = 0; i < n; ++i)  
      {  
           scanf("%d", v + i);  
           if(lim < v[i])  
                lim = v[i];  
      }  
      for(int i = 0; i < n; ++i)  
           scanf("%d", c + i);  
      lim *= lim;  
      t += lim;  
      memset(f, 0x3f, sizeof f);  
      memset(g, 0x3f, sizeof g);  
      f[0] = g[0] = 0;  
      for(int i = 0; i < n; ++i)  
           for(int a = 0; a < v[i]; ++a)  
           {  
                l = r = 0;  
                for(int j = 0; j * v[i] + a <= t; ++j)  
                {  
                     int tmp = f[j * v[i] + a] - j;  
                     while(l < r && que[r - 1][1] >= tmp)  
                          --r;  
                     que[r][0] = j;  
                     que[r++][1] = tmp;  
                     f[j * v[i] + a] = que[l][1] + j;  
                     if(que[l][0] == j - c[i])  
                          ++l;  
                }  
           }  
      for(int i = 0; i < n; ++i)  
           for(int j = v[i]; j <= lim; ++j)  
                if(g[j] > g[j - v[i]] + 1)  
                     g[j] = g[j - v[i]] + 1;  
      t -= lim;  
      ans = INF;  
      for(int i = 0; i <= lim; ++i)  
           if(ans > f[t + i] + g[i])  
                ans = f[t + i] + g[i];  
      if(ans != INF)  
           printf("%d\n", ans);  
      else  
           puts("-1");  
      return 0;  
 }  

POJ.2823 Sliding Window

1.Problem
2823 -- Sliding Window (poj.org)

2.Idea
Using Deque

3.Source

 const int N = 1000006;  
 //////////////////////////////  
 int n, k;  
 int a[N];  
 int mn[N], mx[N];  
 int deq[N];  
 void solve()  
 {  
      scanf("%d%d", &n, &k);  
      REP(i, n) scanf("%d", &a[i]);  
      //MIN values  
      int s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] >= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mn[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mn[i], i == n - k ? '\n' : ' ');  
      }  
      //MAX Values  
      s = 0, t = 0;  
      REP(i, n) {  
           while (s < t && a[deq[t - 1]] <= a[i]) t--;  
           deq[t++] = i;  
           if (i - k + 1 >= 0) {  
                mx[i - k + 1] = a[deq[s]];  
                if (deq[s] == i - k + 1) s++;  
           }  
      }  
      REP(i, n - k + 1) {  
           printf("%d%c", mx[i], i == n - k ? '\n' : ' ');  
      }  
 }