Dynamic Programming Flashcards
- 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?
public int climbStairs(int n) {
// the number of distinct ways we can go from one step to another is
// by a single step (1) or double step (2)
// so to get to step 5 you need to know the possible ways to get step 3
// and the possible ways to get to 4, adding + 2 and + 1 to those gets you
// to step 5 from those.
// ex. 3, to get to step 1, we have 1. to get to step 3, we go 1 + 2
// to get to step 2 we have 1 + 1 and 2, so you add 1 -> 1 + 1 + 1, 2 + 1
// we only need the output though so we just can take those numbers and that
// is the actual number to get to the result
if (n == 1) {
return n;
}
// cache used to hold calculated values
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
// ^ you can actuall just use the number of steps away as 2 variables to hold these values
// we only need the prev 2 to figure out how to get there
for( int i = 3; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
// only want numnber of steps to n
return dp[n];
}
- 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.
public int coinChange(int[] coins, int amount) {
// solve each amout up to amount, if we can't solve amount return -1
int[] dp = new int[amount + 1]; // 0 indexed going to amount itself
// initalize dp w/ unreliable value
Arrays.fill(dp, amount + 1);
// 0 is 0 coins
dp[0] = 0;
// for each amount find the min number of coins to make it
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
// check to see if our coin is less than i
if (coins[j] <= i) {
// we can take this coin in
dp[i] = Math.min(dp[i], 1 + dp[i - coins[j]]);
// ^ we take the current min, or 1 coin + the number of coins to make up the previous calculated amount. So, if you have 4 coins in dp[5], you are on coin 2, so you check at position 3 to see if adding a coin to that is less than what we have.
}
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
- 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].
public int lengthOfLIS(int[] nums) {
// dp array to keep track of subsequences leading to nums.length
int[] dp = new int[nums.length];
Arrays.fill(dp, 1); // All index's are increasing subsequences of length 1
// check subsequence for each pos
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j] && dp[i] <= dp[j]) {
dp[i] = dp[j] + 1;
}
}
}
return Arrays.stream(dp).max().getAsInt();
}
- 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.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
// Dynamic Programming Problem since its solving smaller problems
public boolean wordBreak(String s, List wordDict) {
int n = s.length();
int maxLength = 0;
for (String word : wordDict) {
maxLength = Math.max(maxLength, word.length());
}
// solve for word of length 1 up to s length
// store temp states, we are checking each letter if it works
// all values default false in java
boolean[] dp = new boolean[n + 1];
dp[0] = true; // "" is true in any dictionary
// left and right pointers
for (int i = 0; i <= n; i++) {
for (int j = i - 1; j >= 0; j--) {
if (i - j > maxLength) {
continue;
}
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n]; }
- House Robber
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.
Example 1:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2:
Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.
public int rob(int[] nums) {
// edge cases
if (nums == null || nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
if (nums.length == 2) {
return Math.max(nums[0], nums[1]);
}
// Actual Algorithm
int[] dp = new int[nums.length]; // 0'd
Arrays.fill(dp, -1);
dp[0] = nums[0]; // one house is correct
dp[1] = Math.max(nums[0], nums[1]);
// loop
for (int i = 2; i < dp.length; i++) {
dp[i] = Math.max(dp[i-2] + nums[i], dp[i-1]);
}
return dp[nums.length-1]; }
