Dynamic Programming Notes

Categorization

Counting

• How many ways to go to the left bottom corner
• How many ways to find k elements to get to a sum
• How many ways to permutate for a valid answer

Maximum/Minimum

• Maximum Path

• Longest Ascending Subsequence

• Leetcode 152. Maximum Product Subarray https://leetcode.com/problems/maximum-product-subarray/

True/False

• Can someone win in a duel game

• Can we find k elements to get to a sum

• Can we permutate for a valid answer

• Leetcode 55. Jump Game https://leetcode.com/problems/jump-game/

Type

Coordinate

Overview

• Usually given an array/sequence or grid/matrix as your input
• Need to find a subsequence/vector/path for
  • maximizing/minimizing a certain property
  • counting
  • true/false
• State is represented by dp[i] and dp[i][j], which are the most optimal cases for a[i] or a[i][j]
• Initalization is usually dp[0] with a[0]

Examples

• Leetcode 62. Unique Paths https://leetcode.com/problems/unique-paths/
• Leetcode 63. Unique Paths II https://leetcode.com/problems/unique-paths-ii/
• Leetcode 64. Minimum Path Sum https://leetcode.com/problems/minimum-path-sum/
• Leetcode 674. Longest Continuous Increasing Subsequence https://leetcode.com/problems/longest-continuous-increasing-subsequence/
• Leetcode 1277. Count Square Submatrices with All Ones
• Leetcode 221. Maximal Square
• Leetcode 931. Minimum Falling Path Sum
• Leetcode 361. Bomb Enemy

Sequence

• Leetcode 256. Paint House https://leetcode.com/problems/paint-house