Dynamic Programming

TODO: Add notes here - leaving blank for now.

Basics

Climbing Stairs

https://leetcode.com/problems/climbing-stairs/

N-th Tribonacci Number

https://leetcode.com/problems/n-th-tribonacci-number/description/

Perfect Squares

https://leetcode.com/problems/perfect-squares/description/

Matrix Chain Multiplication

Linear Sequences with Constant Transition

Here the solution requires us to solve the sub problem on every prefix of the array. The definition of a prefix of an array is a subarray from 0 to i for some i.

Min Cost Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/

House Robber

https://leetcode.com/problems/house-robber/

Decode Ways

https://leetcode.com/problems/decode-ways/

Minumum Cost for Tickets

https://leetcode.com/problems/minimum-cost-for-tickets/description/

Solving Questions with Brainpower

https://leetcode.com/problems/solving-questions-with-brainpower/

Grid Problems

The cached table will have the same dimensions as the grid. The DP solution will involve solving the sub problem on a bunch of subgrids.

Unique Paths

https://leetcode.com/problems/unique-paths/

Unique Paths II

https://leetcode.com/problems/unique-paths-ii/

Minimum Path Sum

https://leetcode.com/problems/minimum-path-sum/

Count Square Submatrices with All Ones

https://leetcode.com/problems/count-square-submatrices-with-all-ones/

Maximal Square

https://leetcode.com/problems/maximal-square/

Dungeon Game

https://leetcode.com/problems/dungeon-game/description/

Dual Sequence or DP on Subsequences

The prblem asks about calcuating some value related to two sequences. The cache[i][j] will store the answer to the subproblem solved on a prefix on sequence 1 with length i, and prefix on sequence 2 with length j.

Longest Common Subsequence

https://leetcode.com/problems/longest-common-subsequence/description/

Uncrossed Lines

https://leetcode.com/problems/uncrossed-lines/

Minimum ASCII Delete Sum for Two Strings

https://leetcode.com/problems/minimum-ascii-delete-sum-for-two-strings/description/

Edit Distance

https://leetcode.com/problems/edit-distance/description/

Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/description/

Shortest Common Supersequence

https://leetcode.com/problems/shortest-common-supersequence/description/

Interval

The DP sub problem is solved on every single interval (subarray) of the array.

Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/description/

Stone Game VII

https://leetcode.com/problems/stone-game-vii/

Palindromic Substrings

https://leetcode.com/problems/palindromic-substrings/

Minimum Cost Tree From Leaf Values

https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/description/

Burst Balloons

https://leetcode.com/problems/burst-balloons/description/

Strange Printer

https://leetcode.com/problems/strange-printer/description/

Linear Sequences with Non-Constant Transition

DP problem is solved on every prefix of the array just like group 2. However, transitions may not be simple and require a linear amount of options from indices j < i.

Count Number of Teams

https://leetcode.com/problems/count-number-of-teams/

Longest Increasing Subsequence

https://leetcode.com/problems/longest-increasing-subsequence/

Partition Array for Maximum Sum

https://leetcode.com/problems/partition-array-for-maximum-sum/description/

Largest Sum of Averages

https://leetcode.com/problems/largest-sum-of-averages/

Filling Bookcase Shelves

https://leetcode.com/problems/filling-bookcase-shelves/

Knapsack Problems

Problems with constraints.

0-1 Knapsack

Minimum Cost to Cut a Stick

https://leetcode.com/problems/minimum-cost-to-cut-a-stick/description/

Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/

Number of Dice Rolls with Target Sum

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/description/

Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/description/

Ones and Zeros

https://leetcode.com/problems/ones-and-zeroes/

Coin Change

https://leetcode.com/problems/coin-change/

Coin Change II

https://leetcode.com/problems/coin-change-ii/description/

Target Sum

https://leetcode.com/problems/target-sum/description/

Last Stone Weight II

https://leetcode.com/problems/last-stone-weight/

Profitable Schemes

https://leetcode.com/problems/profitable-schemes/