📄️ Guidelines
Before trying to solve a problem with DP approach first ask yourself if the problem respects the rule of optimality. To determine that see if you can solve the problem by first solving a simpler problem and then using that calculation to solve the initial one. There has to be a natural transition from smaller to larger subproblem (solving a problem for a subarray 0..2, and then using that to solve the problem for subarray 0..5). "Left to right" data structures like arrays, strings, leaves of a tree are natural candidates to apply DP approach to.
📄️ Climbing Stairs
You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
📄️ Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
📄️ House Robber
Given an integer array nums representing the amount of money of each house, return *the maximum amount of money you can rob tonight without alerting the police.
📄️ House Robber II
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle.
📄️ Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
📄️ Decode Ways
Given a string s containing only digits, return the number of ways to decode it.
📄️ Maximum Subarray
Given an integer array nums, find the subarray which has the largest sum and return its sum.
📄️ Maximum Product Subarray
Given an integer array nums, find a subarray that has the largest product, and return the product.
📄️ Combination Sum IV
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
📄️ Best Time to Buy and Sell Stock with Cooldown
You are given an array prices where prices[i] is the price of a given stock on the ith day.
📄️ Unique Paths
There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0])...
📄️ Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence.
📄️ Longest Palindromic Substring
Given a string s, return the longest palindromic substring in s.
📄️ Palindromic Substrings
Given a string s, return the number of palindromic substrings in it.
📄️ Maximal Square
Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
📄️ Target Sum
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
📄️ Partition Equal Subset Sum
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
📄️ Word Break
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
📄️ Number of Longest Increasing Subsequence
Given an integer array nums, return the number of longest increasing subsequences.
📄️ Partition to K Equal Sum Subsets
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.
📄️ Longest Valid Parentheses
Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.
📄️ Maximum Profit in Job Scheduling
You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range.
📄️ Count Unique Characters of All Substrings of a Given String
Given a string s, return the sum of countUniqueChars(t) where t is a substring of s. The test cases are generated such that the answer fits in a 32-bit integer.