Dynamic programming Flashcards
Coin change - min number of coins
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
Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.
Example 3:
Input: amount = 10, coins = [10]
Output: 1
Constraints:
1 <= coins.length <= 300
1 <= coins[i] <= 5000
All the values of coins are unique.
0 <= amount <= 5000
/**
recursive approach
include coin = fn(coins[], amount - coins[i-1], n)
exclude coin = fn(coins[], amount, n-1)
Min(include coin, excluded coin)
*/
class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] dp = new int[n+1][amount+1];
if(coins.length==1 && amount %coins[0] != 0) return -1;
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
if(i == 0) dp[i][j]= amount+1; // i == 0
else if(j == 0) dp[i][j]=0; // amount = 0
else{
if(coins[i-1]<= j){
dp[i][j]= Math.min(dp[i-1][j], 1+dp[i][j-coins[i-1]]);
}
else{
dp[i][j]= dp[i-1][j];
}
}
}
}
return (dp[coins.length][amount] == amount+1) ? -1 : dp[coins.length][amount];
} }
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]). 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.
Example 1:
Input: m = 3, n = 7
Output: 28
Example 2:
Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
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]=1;
else{
dp[i][j]= dp[i-1][j]+dp[i][j-1];
}
}
}
return dp[m-1][n-1];
} }
Unique path 2
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:
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: There is one obstacle in the middle of the 3x3 grid above.
There are two ways to reach the bottom-right corner:
1. Right -> Right -> Down -> Down
2. Down -> Down -> Right -> Right
Example 2:
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Constraints:
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] is 0 or 1.
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int rows=obstacleGrid.length;
int cols=obstacleGrid[0].length;
if(obstacleGrid[0][0]==1)
return 0;
obstacleGrid[0][0]=1;
for(int i=1;i<rows;i++)
{
if(obstacleGrid[i][0]==1)
obstacleGrid[i][0]=0;
else
obstacleGrid[i][0]=obstacleGrid[i-1][0];
}
for(int j=1;j<cols;j++)
{
if(obstacleGrid[0][j]==1)
obstacleGrid[0][j]=0;
else
obstacleGrid[0][j]=obstacleGrid[0][j-1];
}
for(int i=1;i<rows;i++)
{
for(int j=1;j<cols;j++)
{
if(obstacleGrid[i][j]==1)
obstacleGrid[i][j]=0;
else
{
obstacleGrid[i][j]=obstacleGrid[i-1][j]+obstacleGrid[i][j-1];
}
}
}
return obstacleGrid[rows-1][cols-1];
} }
- Min Cost Climbing Stairs
Easy
11K
1.7K
Companies
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) {
for(int i =2; i<cost.length;i++){
cost[i]= cost[i]+ Math.min(cost[i-1], cost[i-2]);
}
return Math.min(cost[cost.length-1], cost[cost.length-2]);
} }
- Climbing Stairs
Easy
20.7K
719
Companies
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;
int[] dp = new int[n+1];
dp[0]=1;
dp[1]=1;
for(int i=2; i<dp.length;i++){
dp[i]= dp[i-1]+dp[i-2];
}
return dp[n];
} }
Total number of combination of coin to make amount
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
/**
recursive approach :
n = coins.length
Include the choice - fn(coins[], amount- coins[n-1], n)
Exclude the coice - fn(coins[], amount, n-1)
amount - Y axis = j
n - X axis = i
*/
class Solution {
public int change(int amount, int[] coins) {
int[][] dp = new int[coins.length+1][amount+1];
for(int i=0;i<dp.length;i++){
for(int j=0;j<dp[0].length;j++){
if(i==0 ) dp[i][j]=0; // there are no coins
else if(j==0) dp[i][j]=1; // there is no amount
else{
if(coins[i-1]<= j){
dp[i][j]= dp[i][j-coins[i-1]] + dp[i-1][j];
}
else
dp[i][j]=dp[i-1][j];
}
}
}
return dp[coins.length][amount];
} }
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
Example 2:
Input: n = 1
Output: [”()”]
Constraints:
class Solution {
List<String> output = new ArrayList<>();
public List<String> generateParenthesis(int n) {
dfs(n, 0, 0, "" );
return output;
}
private void dfs(int n, int open, int close, String curr){
if(curr.length()== n*2){
output.add(curr);
return;
}
if(open < n) dfs(n, open+1, close, curr+"(");
if(close < open) dfs(n, open, close+1, curr+")");
} }
- Partition Equal Subset Sum
Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
class Solution {
public boolean canPartition(int[] nums) {
int sum=0;
for(int i=0;i<nums.length;i++)
{
sum+=nums[i];
}
System.out.println(" Sum is :"+sum);
if(sum % 2 != 0 )
return false;
else
return findSubSetrecursive(nums,sum/2, nums.length);
}
private boolean findSubSetrecursive(int[] nums, int sum, int n)
{
boolean[][] t= new boolean[n+1][sum+1];
for(int i=0;i<t.length;i++)
{
for(int j=0;j<t[0].length;j++)
{
if(i ==0 && j==0 )
t[i][j]=true;
else if(i ==0 && j != 0)
t[i][j]=false;
else if(i != 0 && j==0)
t[i][j]=true;
else if(nums[i-1]<= j)
{
t[i][j]=t[i-1][j-nums[i-1]] || t[i-1][j];
}
else
t[i][j]=t[i-1][j];
}
}
return t[n][sum];
// return true;
}
}
