Dynamic Programming Problems
Let’s solve dynamic programming problems starting from very basic questions
Remember that whenever there is words such as minimum cost or maximum or number of ways for any problems try thinking in terms of DP
- Fibonacci Number (Leet Code)
F(0) = 0, F(1) = 1
construct an array and store the value of already found numberF(n) = F(n - 1) + F(n - 2), for n > 1.
Solution:
2. Climbing Stairs (Leet Code)
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?
Approach:
At every given point you have to choose to climb either 1 step or 2 step and count the number of ways we could get to that result
- Memoization: Solve each subproblem once and save it for later use.
Solution:
3. Target Sum (Leet Code)
You are given an integer array nums and an integer target.
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.
- For example, if
nums = [2, 1], you can add a'+'before2and a'-'before1and concatenate them to build the expression"+2-1".
Return the number of different expressions that you can build, which evaluates to target.
Solution:
4. Minimum Cost For Tickets (Leet Code)
You have planned some train traveling one year in advance. The days of the year in which you will travel are given as an integer array days. Each day is an integer from 1 to 365.
Train tickets are sold in three different ways:
- a 1-day pass is sold for
costs[0]dollars, - a 7-day pass is sold for
costs[1]dollars, and - a 30-day pass is sold for
costs[2]dollars.
The passes allow that many days of consecutive travel.
- For example, if we get a 7-day pass on day, then we can travel for
7days:2,3,4,5,6,7, and8.
Return the minimum number of dollars you need to travel every day in the given list of days.
5. Word Break (Leet Code)
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. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Solution:
6. House Robber (Leet Code)
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
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.
Recurrence Relation:rob = max( arr[0] + rob[2:n] , rob[1:n])
7. House Robber 2 (Leet Code)
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. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.
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.
8. Maximum Product Subarray (Leet Code)
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
9. Unique Paths (Leet Code)
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]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
10. Pascal’s Triangle (Leet Code)
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:
11. Coin Change
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Solution:
12. Minimum Path Sum
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
Solution:
13. Paint House
There is a row of n houses, each house can be painted with one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color, and you need to cost the least. Return the minimum cost. The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting the house 0 with color red; costs[1][2] is the cost of painting a house 1 with the color green, and so on... Find the minimum cost to paint all houses.
Input: [[14,2,11],[11,14,5],[14,3,10]]
Output: 10
Explanation: Paint house 0 into blue, paint house 1 into green, paint house 2 into blue. Minimum cost: 2 + 5 + 3 = 10.
Solution:
14. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
Solution:
Perfect Squares
Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
Solution:
Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equals t.
A string’s subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters’ relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not). The test cases are generated so that the answer fits on a 32-bit signed integer.
Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit
Solution:
Combination Sum
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.
The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.
The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.
Solution:
References: