You are given a notepad with a single character 'A' present. You are allowed to perform one of two operations for every step:
1. Copy Everything: You can make a copy of all the characters on the notepad. You are not allowed to partially copy the text on the notepad.
2. Paste: You can paste all the characters which have been copied and the pasted characters will append onto the existing string.
Given an integer n, return the minimum number of steps to take such that the notepad only shows n number of 'A's.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: 3
Output: 3
Explanation:
We start off with one character 'A'.
In step 1, we use the Copy Everything operation.
In step 2, we use the Paste operation to get 'AA'.
In step 3, we use the Paste operation to get 'AAA'.
</pre>
&nbsp;

Two Button Keyboard

You have a keyboard that only has these 4 buttons:
<code></code>Button 1: Print an 'A' on the screen
Button 2: Select the whole screen
Button 3: Copy the selected text to buffer
Button 4: Print buffer on the screen and append it to whatever is on the screen.
You are allowed to press the keyboard N times, return the maximum number of 'A's you can print on the screen.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: N = 3
Output: 3
Explanation: 
We can print at most 3 A's on the screen by pressing following buttons: 1, 1, 1
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: N = 7
Output: 9
Explanation: 
We can print at most 9 A's on screen by pressing following buttons:
1, 1, 1, 2, 3, 4, 4
</pre>

Four Button Keyboard

A number sequence is called arithmetic as long as it consists of at least 3 elements and if the difference between any 2 consecutive elements are the same.
For example, these are arithmetic sequences:
<pre style="white-space: pre-wrap; word-break: keep-all;">1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9</pre>
The following sequence is not arithmetic.
<pre style="white-space: pre-wrap; word-break: keep-all;">1, 1, 2, 5, 7</pre>
Given an array, A, return the number of arithmetic slices. An arithmetic slice is any pair of integers (P, Q) such that 0 &lt;= P &lt; Q &lt; N and&nbsp;A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. This means that P + 1 &lt; Q.
&nbsp;
Example:
<pre style="white-space: pre-wrap; word-break: keep-all;">A = [1, 2, 3, 4]
</pre>

<pre style="white-space: pre-wrap; word-break: keep-all;">
return: 3 There are 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.
</pre>

Count Slices

You have an array, <code>prices</code>, in which the ith element represents the price of stock on day i. 

Find the maximum profit with instructions below: 

<ul>
	<li> You can complete at most two transactions . </li>
	<li> You must always sell the stock before you can buy again. You cannot engage in multiple transactions at the same time.
</ul>

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [1,4,2,1,4,6,10]
Output: 12
Explanation: Buy on day 0 (price 1), and sell on day 1 (price 4).
&nbsp; Then buy on day 3 (price 1), and sell on day 6 (price 10). 
&nbsp; maximum profit = (4 - 1) + (10 - 1) = 12.
</pre>

 

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [0,1,1,1,10]
Output: 10
Explanation: Buy on day 1 (price 0), and sell on day 4 (price 10).
&nbsp; Note that you cannot engage in multiple transactions at the same time.
&nbsp; maximum profit = 10 - 0 = 10.
</pre>

 

Example 3:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [10,9, 8, 7]
Output: 0
Explanation: No transaction is done. maximum profit = 0.
</pre>

Maximize Profits In The Stock Market III

You have an array, <code>prices</code>, in which the ith element represents the price of stock on day i. 
Find the maximum profit with restrictions below: 

<ul>
	<li> You must always sell the stock before you can buy again.
	<li> You must have one "break" day after selling stock. You cannot buy stock on the next day. </li>
</ul>

Example:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [3,5,0,2,4]
Output: 4
Explanation: transactions = [buy, sell, break, buy, sell]
</pre>

Maximize Profits In The Stock Market With Break

You have an array, <code>prices</code>, in which the ith element represents the price of stock on day i. 

Find the maximum profit if you can perform at most one transaction and you must buy the stock before selling.


Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [8,1,4,2,8,9]
Output: 8
Explanation: Buy on day 1 (price 1), and sell on day 5 (price 9). maximum profit = 9 - 1 = 8.
</pre>

 

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [10,9, 8, 7]
Output: 0
Explanation: No transaction is done. maximum profit = 0.
</pre>

Maximize Profits In The Stock Market

Given a grid, where each cell can be a wall (<code>'W'</code>), an enemy (<code>'E'</code>) or empty space (<code>'0'</code>) (zero), return the total enemies you can kill with a single bomb. A bomb will kill all enemies in the same row and column from the place it's planted until it hits a wall. You are only allowed to place a bomb in an empty space.
Example:

<pre style="white-space: pre-wrap; word-break: keep-all;">Input: [ ["0","E","0","0"], ["E","0","W","E"], ["0","E","0","0"] ]
Output: 3 
Explanation: For the given grid,

Place a bomb at (1,1) kills 3 enemies.
</pre>

Optimize Bomberman

Given integer n that represents the number of stairs on a staircase, return the number of ways you can reach the top if you are only allowed to take 1 or 2 steps at a time.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: 2
Output: 2
Explanation: There are only two ways get to the top.
1. 1 step + 1 step
2. 2 steps
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: 3
Output: 3
Explanation: There are only three ways to get to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
</pre>

Staircase

Given a list of coins the represent different denominations and an amount of money you need to create, return the minimum number of coins needed to make up the amount of money. If the money cannot be made up by any combination of the coins return -1.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: coins = <code>[1, 2, 5]</code>, amount = <code>11</code> Output: <code>3</code> Explanation: 11 = 5 + 5 + 1</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: coins = <code>[2]</code>, amount = <code>3</code> Output: -1</pre>
Note: You are allowed to use infinite number of coins for each denomination.

Exchange Coins

Given a list of integers and a target integer called k, return true if the array has a continuous subarray that has at least 2 elements and sums up to a multiple of k.&nbsp;
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: [23, 2, 6, 4, 7] is a continuous subarray of size 5 and sums up to 42 which is a multiple of 6.
</pre>
&nbsp;

Contiguous Array Sum

Given the integer array, nums, perform any operation on the array.
An operation is defined as:
<ul>
<li>Choose any nums[i] and remove it to earn nums[i] points, then remove every element in the nums array such that they are equal to nums[i] - 1 or nums[i] + 1.</li>
</ul>
You begin with 0 points, return the max number of points you can accumulate by performing the operations.
&nbsp;
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: nums = [3, 4, 2]
Output: 6
Explanation: 
Remove 4 to earn 4 points, consequently 3 is removed.
Then, remove 2 to earn 2 points. 6 total points are earned.
</pre>
&nbsp;
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: nums = [2, 2, 3, 3, 3, 4]
Output: 9
Explanation: 
Remove 3 to earn 3 points, which results in removing both 2's and the 4.
Then, remove 3 again to earn 3 points, and 3 again to earn 3 points.
9 total points are earned.
</pre>
&nbsp;
&nbsp;

Maximize Points In Array Game

You have an array of non-negative integers, nums, in which the ith element represents cash that house i keeps. 

You are an expert at robbing houses. Find the maximum cash you can steal tonight with the restriction below: 

<ul>
	<li> You cannot rob adjacent houses. You must skip houses right next to the house that you rob.</li>
	<li> Houses are in a circle. Hence you cannot rob the first element and last element at the same time. </li>
</ul>

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [4,5,3]
Output: 5
Explanation: You cannot rob house 0 (cash = 4) and house 2 (cash = 3),
&nbsp; because they are adjacent houses.
</pre>

 

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [2,4,1,2,3]
Output: 7
Explanation: Rob house 1 (cash = 4) and house 4 (cash = 3).
&nbsp; Maximum cash = 4 + 3 = 7.</pre>

Rob Neighborhood II

You have an array of non-negative integers, nums, in which the ith element represents cash that house i keeps. 

You are an expert at robbing houses. Find the maximum cash you can steal tonight with the restriction below: 

<ul>
	<li> You cannot rob adjacent houses. You must skip houses right next to the house that you rob.</li>
</ul>

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [2,4,1,2]
Output: 6
Explanation: Rob house 1 (cash = 4) and then rob house 3 (cash = 2).
&nbsp; Maximum cash = 4 + 2 = 6.</pre>

 

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [3,4,1,4,10]
Output: 14
Explanation: Rob house 1 (cash = 4) and rob house 4 (cash = 10).
&nbsp; Maximum cash = 4 + 10 = 14.
</pre>

Rob Neighborhood

Given a string s, return the first instance of the longest contiguous palindrome substring.

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: &quot;ctctd&quot;
Output: &quot;ctc&quot;
Note: &quot;tct&quot; is the first instance of the longest substring that is a palindrome.
</pre>

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: &quot;caad&quot;
Output: &quot;aa&quot;
</pre>

Longest Palindrome In String

You are given a string, <code>s</code>, which only contains brackets ' ( ' and ' ) '. Find the length of the longest valid brackets. 

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: &quot;())&quot;
Output: 2
Explanation: The longest valid bracket substring is <code>&quot;()&quot;</code>
</pre>

 

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: &quot;<code>()(()))()</code>&quot;
Output: 6
Explanation: The longest valid bracket substring is <code>&quot;()(())&quot;</code>
</pre>

Longest Valid Brackets

Given an array of integers <code>nums</code>, find the largest sum of contiguous subarray that has at least one integer. 

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [-3,3,-1,7,-10,5]
Output: 9
Explanation:&nbsp;[3,-1,7] has the largest sum = 9.
</pre>

 

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: [4,3,2,0,10]
Output: 19
Explanation:&nbsp;[4,3,2,0,10] has the largest sum = 19.
</pre>

 

Next Step:

Can you solve it in O(n)?

Largest Sum Of Subarray

SWE Careers wants to reward one of its best employees the option to travel to N cities to write new algorithm problems but you are only allowed to take vacations in some particular cities and weeks. You need to schedule the travel to maximize the number of vacations to take but you need to follow these rules:
1. You start in the city indexed at 0 on a Monday and you are allowed to travel among the N cities from indexes 0 to N-1.
2. Cities are connected by flights represented by an N by N matrix called flights. If no flights exist from city i to city j then flights[i][j] is 0. If there is a flight from city i to city j then flights[i][j] = 1. flights[i][i] is 0 for all i.
3. You only have K weeks to travel and you only take at most one flight per day and you are only allowed to fly on each week's Monday morning. We ignore the time of flights since flight times are short.
4. In each city, you can only have a certain number of vacation days given in a N by K matrix called days. For example: days[i][j] means you can only take a maximum of that many vacation days in city i on week j.
Given the flights matrix and the days matrix, return the maximum number of vacation days you can take for K weeks.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: flights = [[0,1,1],[1,0,1],[1,1,0]] days = [[1,3,1],[6,0,3],[3,3,3]]
Output: 12
Explanation: Answer = 6 + 3 + 3 = 12. 
The best strategy is:
1st week : fly from city 0 to city 1 on Monday, and play 6 days and work 1 day. (Although you start at city 0, we could also fly to and start at other cities since it is Monday.) 
2nd week : fly from city 1 to city 2 on Monday, and play 3 days and work 4 days.
3rd week : stay at city 2, and play 3 days and work 4 days.
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: flights = [[0,0,0],[0,0,0],[0,0,0]] days = [[1,1,1],[7,7,7],[7,7,7]]
Output: 3
Explanation: Ans = 1 + 1 + 1 = 3. 
Since there is no flights enable you to move to another city, you have to stay at city 0 for the whole 3 weeks. For each week, you only have one day to play and six days to work. So the maximum number of vacation days is 3.
</pre>
Example 3:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: flights = [[0,1,1],[1,0,1],[1,1,0]] days = [[7,0,0],[0,7,0],[0,0,7]]
Output: 21
Explanation: Ans = 7 + 7 + 7 = 21 
One of the best strategies is:
1st week : stay at city 0, and play 7 days. 
2nd week : fly from city 0 to city 1 on Monday, and play 7 days.
3rd week : fly from city 1 to city 2 on Monday, and play 7 days.
</pre>
&nbsp;

Optimize Vacation

You are given an array of integers and the <code>i</code>-th number represents the cost required to climb one or two steps. Return the minimum cost required to travel to the top.&nbsp;
You may start at index 0 or 1.&nbsp;
&nbsp;
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: cost = [2, 3, 4]
Output: 3
Explanation: Cheapest is start on cost[1] and go to the top
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: cost = [2,10,3,5,2,55,2]
Output: 9
Explanation: Cheapest is start on cost[0], and go to cost[2], cost[4], and cost[6]
</pre>
Note:
<ol>
<li>All the integers are in the&nbsp;range <code>[0, 999]</code>.</li>
</ol>

Lowest Cost To Climb Stairs

Given 2 strings S and T, return the minimum contiguous substring W of S such that T is also a subsequence (non-contiguous) of W.&nbsp;
If there are multiple results, return the substring with the leftmost starting index. If there are no results then return an empty string.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: 
S = "abcdebdde", T = "bde"
Output: "bcde"
Explanation: 
"bcde" is the answer since it occurs before "bdde" even though both substrings contains T as a subsequence and has the shortest length.
"deb" is not an answer because T is not a subsequence since the order isn't the same.
</pre>
&nbsp;

Smallest Substring Subsequence

You are given a matrix with elements that are 0 or 1. Find the number of corner rectangles.

A corner rectangle is defined as 4 distinct 1s on the grid that form a rectangle. Only the corners need to have the value 1. Also, all four 1s used must be distinct from each other.

&nbsp;

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: grid = 
[[1, 0, 0, 1, 0],
 [0, 0, 1, 0, 1],
 [0, 0, 0, 1, 0],
 [1, 0, 1, 0, 1]]
Output: 1
Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
</pre>

&nbsp;

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: grid = 
[[1, 1, 1],
 [1, 1, 1],
 [1, 1, 1]]
Output: 9
Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.
</pre>

&nbsp;

Example 3:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: grid = 
[[1, 1, 1, 1]]
Output: 0
Explanation: Rectangles must have four distinct corners.
</pre>

&nbsp;

Note:

<ol>
	<li>The number of both rows and columns will be in the range <code>[1, 200]</code>.</li>
	<li>The number of <code>1</code>s in the grid will be at most <code>6000</code>.</li>
</ol>

&nbsp;

Count Corner Rectangles

Given 2 integers, n and k where n represents the number of posts on a fence and k representing the number of colors available, return the total number of ways to paint the fence such that no more than two adjacent fence posts have the same color.&nbsp;
Note: n and k are non-negative integers.
Example:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: n = 3, k = 2
Output: 6
Explanation: Suppose c1 is color 1, c2 is color 2. All the possible ways of painting the fence are:

&nbsp; post1 post2 post3 
 ----- ----- ----- ----- 
 1 c1 c1 c2 
&nbsp; 2 c1 c2 c1 
&nbsp; 3 c1 c2 c2 
&nbsp; 4 c2 c1 c1&nbsp; 
 5 c2 c1 c2
&nbsp; 6 c2 c2 c1
</pre>

Fence Painter

A row of n houses exist and they can only be painted with one of k colors. The cost of painting each house with a particular color is different. You also must paint all houses such that no adjacent houses can use the same color.
Given a 2D matrix, costs, that is size n x k and each value represents the cost, return the minimum cost to paint all houses. For example, costs[0][0] is the cost of painting house 0 with color. Another example: costs[1][2] is the cost of painting house 1 with color. Costs are all positive integers.
Example:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: [ [1,5,3], [2,9,4] ]
Output: 5
Explanation: One way to paint the houses such that we get the minimum cost is to paint house 0 with color 0, paint house 1 with color 2. Minimum cost: 1 + 4 = 5; 
&nbsp; Or we can also paint house 0 with color 2, paint house 1 with color 0. Minimum cost: 3 + 2 = 5. 
</pre>
Challenge: Solve this in O(nk) time complexity.

Home Painter II

Given a string, return the number of palindromic substrings.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: "abc"
Output: 3
Explanation: 3 palindromic strings: "a", "b", "c".
</pre>
&nbsp;
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: "aaa"
Output: 6
Explanation: 6 palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
</pre>
&nbsp;
Note:
<ol>
<li>The length of the input string won't exceed 1000.</li>
<li>If substrings have the same characters but different start and end indexes then count them as different strings.</li>
</ol>

Count Palindrome Substrings

Given a string, s, and a string that represents a regular expression pattern, p, implement an algorithm to check if pattern p matches pattern p. You only need to support <code>'.'</code> and <code>'*'</code>.
<pre style="white-space: pre-wrap; word-break: keep-all;">'.' Matches any single character.
'*' Matches zero or more of the preceding element.
</pre>
Note:
<ul>
<li><code>s</code>&nbsp;can be empty and contains only lowercase letters <code>a-z</code>.</li>
<li><code>p</code> can be empty and contains only lowercase letters <code>a-z</code>, and characters like&nbsp;<code>.</code>&nbsp;or&nbsp;<code>*</code>.</li>
</ul>
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" doesn't match the string "aa".
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
s = "aa"
p = "a*"
Output: true
Explanation:&nbsp;'*' means zero or more of the precedeng&nbsp;element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
</pre>
Example 3:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
s = "ab"
p = ".*"
Output: true
Explanation:&nbsp;".*" means "zero or more (*) of any character (.)".
</pre>
Example 4:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation:&nbsp;c can be repeated 0 times, a can be repeated 1 time. Therefore it matches "aab".
</pre>
Example 5:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
</pre>

Match Regular Expression

Given a screen that has dimensions: rows x columns and a sentence that is a list of strings, return the number of times the given sentence can fit on the screen.
Follow these rules:
<ol>
<li>A word cannot be split between 2 lines.</li>
<li>The sentence must maintain the same order on the screen.</li>
<li>Consecutive words must be separated by a single space.</li>
<li>There won't be more than 100 words in a given sentence.</li>
<li>A word won't be greater than 10 characters.</li>
<li>1 &le; rows, columns &le; 20,000.</li>
</ol>
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
rows = 2, cols = 8, sentence = ["hello", "world"]

Output: 
1

Explanation:
hello---
world---

The character '-' represents an empty space on the screen.
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
rows = 3, cols = 6, sentence = ["a", "bcd", "e"]

Output: 
2

Explanation:
a-bcd- 
e-a---
bcd-e-

The character '-'represents an empty space on the screen.
</pre>
Example 3:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input:
rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]

Output: 
1

Explanation:
I-had
apple
pie-I
had--

The character '-'represents an empty space on the screen.
</pre>

Fit Sentence On Screen

There is a weird printer that follows two rules:
<ol>
<li>The printer can only print sequences of the same character at a time.</li>
<li>For every turn, the printer prints characters starting from and ending at any place that will cover the original existing characters.</li>
</ol>
Given a string that contains only lowercase English letters, return the minimum number of turns the printer is needed to print the string.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: "aba"
Output: 2
Explanation: Print "aaa" first and then print "b" from the second place of the string, which will cover the existing character 'a'.
</pre>

Weird Printer

You are given an integer k which represents K number of eggs and an integer N which represents the number of floors in a building.
You want to find out the highest floor such that an egg won't break at that floor. For each move, you are allowed to drop an egg from any floor between 1 to N, if an egg breaks then you cannot drop it anymore.&nbsp;
Return the minimum number of moves to determine the highest floor such that an egg dropped will not break.
<div>
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: K = 1, N = 2
Output: 2
Explanation: 
Drop the egg from floor 1. If it breaks, we know with certainty that the first floor will break the egg.
If it doesn't break, drop the egg from floor 2. If it breaks, we know with certainty that the seccond floor will break the egg.
If it didn't break, then we know that the second floor won't break the egg.
So we return 2 because in the worst case we need 2 moves to find out the max height an egg can be dropped from without breaking.
</pre>
<div>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: K = 2, N = 6
Output: 3
</pre>
<div>
Example 3:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: K = 3, N = 14
Output: 4
</pre>
</div>
</div>
</div>

Dropping Eggs

Given a list of non-negative integers and a target integer, S. Return the total number of ways to add the integers to S such that you are only allowed to place + or - between the integers.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to add symbols to add up the nums to be target 3.
</pre>
Note:
<ol>
<li>The given array only contains positive integers and never exceed length 20.</li>
<li>The total sum of elements in the array never exceeds 1000.</li>
<li>Your output is guaranteed to be a 32-bit integer.</li>
</ol>

Number Of Ways To Sum

Given an integer&nbsp;n, return the number of structurally distinct binary search trees that can be created where the values store 1 .. n.
Example:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: 3
Output: 5
Explanation:
Given n = 3, you can create 5 structurally distinct BST's:

 1 3 3 2 1
 \ / / / \ \
 3 2 1 1 3 2
 / / \ \
 2 1 2 3
</pre>

Distinct Binary Search Trees

A monkey starts at the top left corner of a m by n grid and the monkey can only move down or to the right. The finish goal is at the bottom right corner. Return the number of distinct paths that the monkey can take from the top right corner to the bottom right corner.

Note: m and n will be at most 100.
Example 1:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: m = 3, n = 2
Output: 3
Explanation:
There are 3 ways to move from the top left to the bottom right.
1. Right -&gt; Right -&gt; Down
2. Right -&gt; Down -&gt; Right
3. Down -&gt; Right -&gt; Right
</pre>
Example 2:
<pre style="white-space: pre-wrap; word-break: keep-all;">Input: m = 7, n = 3
Output: 28</pre>

Distinct Paths

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

<ul>
	<li>The same word in the dictionary may be reused multiple times in the segmentation.</li>
	<li>You may assume the dictionary does not contain duplicate words.</li>
</ul>

Example 1:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: s = &quot;swecareers&quot;, wordDict = [&quot;swe&quot;, &quot;careers&quot;]
Output: true
Explanation: Return true because <code>&quot;swecareers&quot;</code> can be segmented as <code>&quot;swe careers&quot;</code>.
</pre>

Example 2:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: s = &quot;applepenapple&quot;, wordDict = [&quot;apple&quot;, &quot;pen&quot;]
Output: true
Explanation: Return true because <code>&quot;</code>applepenapple<code>&quot;</code> can be segmented as <code>&quot;</code>apple pen apple<code>&quot;</code>.
&nbsp; Note that you are allowed to reuse a dictionary word.
</pre>

Example 3:

<pre style="white-space: pre-wrap; word-break: keep-all;">
Input: s = &quot;catsandog&quot;, wordDict = [&quot;cats&quot;, &quot;dog&quot;, &quot;sand&quot;, &quot;and&quot;, &quot;cat&quot;]
Output: false
</pre>

Problem Title	Difficulty	Frequency in Interviews
Longest Palindrome In String	Medium
Largest Sum Of Subarray	Easy
Maximize Profits In The Stock Market	Easy
Exchange Coins	Medium
Match Regular Expression	Hard
Word Segments	Medium
Longest Valid Brackets	Hard
Staircase	Easy
Count Palindrome Substrings	Medium
Rob Neighborhood	Easy
Distinct Paths	Medium
Contiguous Array Sum	Medium
Smallest Substring Subsequence	Hard
Dropping Eggs	Hard
Distinct Binary Search Trees	Medium
Maximize Profits In The Stock Market III	Hard
Maximize Profits In The Stock Market With Break	Medium
Optimize Bomberman	Medium
Rob Neighborhood II	Medium
Lowest Cost To Climb Stairs	Easy
Number Of Ways To Sum	Medium
Home Painter II	Hard
Maximize Points In Array Game	Medium
Count Corner Rectangles	Medium
Optimize Vacation	Hard
Fence Painter	Easy
Count Slices	Medium
Fit Sentence On Screen	Medium
Two Button Keyboard	Medium
Four Button Keyboard	Medium
Weird Printer	Hard

Most Frequently Asked Dynamic Programming Interview Questions

Sort By: Company Questions

Sort By: Problem Type