Dynamic Programming Flashcards
- Minimum Path Sum
Medium
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.
Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
class Solution {
public int minPathSum(int[][] grid) {
for(int i =0;i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
if(i==0 && j!=0){
grid[i][j]=grid[i][j]+grid[i][j-1] ;
}
else if(j==0 && i!=0){
grid[i][j]=grid[i][j]+grid[i-1][j] ;
}
else if(j!=0 && i!=0){
grid[i][j]=grid[i][j]+Math.min(grid[i-1][j],grid[i][j-1]);
}
}
}
return grid[grid.length-1][grid[0].length-1];
}
}
- Coin Change
Medium
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.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
Example 3:
Input: coins = [1], amount = 0
Output: 0
class Solution {
public int coinChange(int[] coins, int amount) {
//Edge cases single element
if(coins.length == 1 && amount%coins[0]!=0){
return -1;
}
int n = coins.length;
int[][] dp = new int[n+1][amount+1];
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
if(i==0){ // we have no coins but need to make amount so not possible put anything greater than amount
dp[i][j]=Integer.MAX_VALUE-1;
}
else if(j==0){ // Amount to be made is 0 so there is no such combination of coins
dp[i][j]=0;
}
else{
if(j>=coins[i-1]){
/**
Choice 1 : Include fn(coins[], amount - coins[n-1], n) == Keep n coz we can take same coin multiple times.. unbounded knapsack
Choice 2 : Not include fn(coins[], amount, n-1)
*/
dp[i][j]=Math.min(1+dp[i][j-coins[i-1]],dp[i-1][j]);
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
}
//Edge cases..
if(dp[n][amount]> amount){
return -1;
}
else{
return dp[n][amount];
}
}
}
- Climbing Stairs
Easy
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?
Example 1:
Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
Example 2:
Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
class Solution {
public int climbStairs(int n) {
if(n ==1){
return 1;
}
//Intializing array to n+1, as we will be ignoring 0 index
int[] arr = new int[n+1];
arr[1]=1;
arr[2]=2;
for(int i =3;i<n+1;i++){
arr[i]=arr[i-1]+arr[i-2];
}
return arr[n];
}
}
- Min Cost Climbing Stairs
Easy
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Example 1:
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Example 2:
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
class Solution {
public int minCostClimbingStairs(int[] cost) {
if(cost.length == 1){
return cost[0];
}
if(cost.length == 2){
return Math.min(cost[0],cost[1]);
}
for(int i = 2;i<cost.length;i++){
cost[i]=cost[i]+Math.min(cost[i-2],cost[i-1]);
}
return Math.min(cost[cost.length-2],cost[cost.length-1]);
}
}
- Coin Change II
Medium
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
Example 1:
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int [][]dp = new int[n+1][amount+1];
for(int i =0;i<dp.length;i++){
for(int j = 0;j<dp[0].length;j++){
//if there are no coins, there is no way to make amount
if(i==0){
dp[i][j]=0;
}
//if amount is 0 and we have coins then the possible way is 1.
else if(j==0){
dp[i][j]=1;
}
else{
//Choice 1(include coin): fn(coins[], amount-coins[n-1],n)
//Choice 2(not include coin): fn(coins[],amount, n-1)
//addition of choice 1 + choice 2 gives numbers of ways to make an amount
if(j>=coins[i-1]){
dp[i][j]=dp[i][j-coins[i-1]]+dp[i-1][j];
}
else{
dp[i][j]=dp[i-1][j];
}
}
}
}
return dp[n][amount];
}
}
Console
- Longest Palindromic Subsequence
Medium
Given a string s, find the longest palindromic subsequence’s length in s.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: s = “bbbab”
Output: 4
Explanation: One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input: s = “cbbd”
Output: 2
Explanation: One possible longest palindromic subsequence is “bb”
class Solution {
public int longestPalindromeSubseq(String s) {
StringBuilder sb = new StringBuilder();
sb.append(s);
String s1 = sb.reverse().toString();
int[][] dp = new int[s.length()+1][s1.length()+1];
for(int i =0;i<dp.length;i++){
for(int j = 0;j<dp[0].length;j++){
if(i==0||j==0){
dp[i][j]=0;
}
else if(s.charAt(i-1)==s1.charAt(j-1)){
dp[i][j]=1+dp[i-1][j-1];
}
else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[s.length()][s1.length()];
}
}
- Delete Operation for Two Strings
Medium
Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 = “sea”, word2 = “eat”
Output: 2
Explanation: You need one step to make “sea” to “ea” and another step to make “eat” to “ea”.
Example 2:
Input: word1 = “leetcode”, word2 = “etco”
Output: 4
class Solution {
public int minDistance(String word1, String word2) {
int[][] dp = new int[word1.length()+1][word2.length()+1];
for(int i =0;i<dp.length;i++){
for(int j =0;j<dp[0].length;j++){
if(i==0||j==0){
dp[i][j]=0;
}
else if(word1.charAt(i-1)==word2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
int commonLength = dp[dp.length-1][dp[0].length-1];
int output = word1.length()+word2.length()-2*commonLength;
return output;
}
}
- Longest Common Subsequence
Medium
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, “ace” is a subsequence of “abcde”.
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = “abcde”, text2 = “ace”
Output: 3
Explanation: The longest common subsequence is “ace” and its length is 3.
Example 2:
Input: text1 = “abc”, text2 = “abc”
Output: 3
Explanation: The longest common subsequence is “abc” and its length is 3.
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int [][] dp = new int[text1.length()+1][text2.length()+1];
for(int i =0;i<dp.length;i++){
for(int j =0;j<dp[0].length;j++){
if(i==0||j==0){
dp[i][j]=0;
// continue;
}
else if(text1.charAt(i-1)==text2.charAt(j-1)){
dp[i][j]=dp[i-1][j-1]+1;
}
else{
dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[text1.length()][text2.length()];
}
}
- Unique Paths
Medium
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.
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for(int i =0;i<m;i++){
for(int j =0;j<n;j++){
if(i==0||j==0){
dp[i][j]=1;
}
else{
dp[i][j]=dp[i-1][j]+ dp[i][j-1];
}
}
}
return dp[m-1][n-1];
}
}
- Unique Paths II
Medium
You are given an m x n integer array grid. There is a robot 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.
An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle.
Return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The testcases are generated so that the answer will be less than or equal to 2 * 109.
Example 1:
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if(obstacleGrid[0][0]==1) return 0;
else{
obstacleGrid[0][0]=1;
}
for(int i = 0;i<obstacleGrid.length;i++){
for(int j =0;j<obstacleGrid[0].length;j++){
if(i==0 && j!=0){
if(obstacleGrid[i][j]==1){
obstacleGrid[i][j]=0;
}
else{
obstacleGrid[i][j] = obstacleGrid[i][j-1];
}
}
if(j==0 && i!=0){
if(obstacleGrid[i][j]==1){
obstacleGrid[i][j]=0;
}
else{
obstacleGrid[i][j] = obstacleGrid[i-1][j];
}
}
if(i!=0 && j!=0){
if(obstacleGrid[i][j]==1){
obstacleGrid[i][j]=0;
}
else{
obstacleGrid[i][j] = obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
}
}
}
}
return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
}
}
- The Maze
Medium
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball’s start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
You may assume that the borders of the maze are all walls (see examples).
Example 1:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
Example 2:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2]
Output: false
Explanation: There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.
Example 3:
Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1]
Output: false
Constraints:
m == maze.length
n == maze[i].length
1 <= m, n <= 100
maze[i][j] is 0 or 1.
start.length == 2
destination.length == 2
0 <= startrow, destinationrow <= m
0 <= startcol, destinationcol <= n
Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
The maze contains at least 2 empty spaces.
class Solution {
int[] dirX = {0, 1, 0, -1};
int[] dirY = {-1, 0, 1, 0};
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
int m = maze.length;
int n = maze[0].length;
boolean[][] visited = new boolean[m][n];
return dfs( m, n ,maze,start,destination,visited);
}
public boolean dfs(int m,int n, int [][]maze, int[] curr, int [] destination,boolean [][] visited){
if (visited[curr[0]][curr[1]]) {
return false;
}
if(curr[0]==destination[0] && curr[1]==destination[1]){
return true;
}
visited[curr[0]][curr[1]] = true;
for(int i =0;i<4;i++){
int curr_x = curr[0];
int curr_y = curr[1];
while(curr_x >= 0 && curr_y>=0 && curr_x < m && curr_y < n && maze[curr_x][curr_y]==0){
curr_x =curr_x+dirX[i];
curr_y = curr_y+dirY[i];
}
if (dfs(m, n, maze, new int[]{curr_x - dirX[i], curr_y - dirY[i]}, destination,visited)) {
return true;
}
}
return false;
}
}
- Is Subsequence
Easy
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Example 1:
Input: s = “abc”, t = “ahbgdc”
Output: true
Example 2:
Input: s = “axc”, t = “ahbgdc”
Output: false
Constraints:
0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.length()>t.length()){
return false;
}
Queue<Character> q = new LinkedList<>();
for(int i =0;i<s.length();i++){
q.add(s.charAt(i));
}
for(int j = 0;j<t.length();j++){
if(!q.isEmpty()&& t.charAt(j)==q.peek()){
q.poll();
}
}
if(q.isEmpty()){
return true;
}
return false;
}
}</Character>
- Maximum Product Subarray
Medium
Given an integer array nums, find a
subarray
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.
Example 1:
Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
class Solution {
public int maxProduct(int[] nums) {
int min = nums[0];
int max = nums[0];
int result = nums[0];
int length = nums.length;
if(length ==0)return 0;
for(int i =1;i<nums.length;i++){
int temp_max = Math.max(maxnums[i],Math.max(minnums[i],nums[i]));
min = Math.min(maxnums[i],Math.min(minnums[i],nums[i]));
max = temp_max;
result = Math.max(result, max);
}
return result;
}
}
Console
