1d dp

198. 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.

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.

// Choices: Skip this house, or include
class Solution {
    public int rob(int[] nums) {
        // the order is: prev2, prev1, curr
        int pre2 = 0, pre1 = 0;
        for(int curr: nums){
            int temp = pre1;
            pre1 = Math.max(pre2 + curr, pre1);
            pre2 = temp;
        }
        return pre1;
    }
    public int robIterTop(int[] nums) {
        int N = nums.length;
        int[] dp = new int[N + 2];       
        for(int i = N - 1; i >= 0; i--)
            dp[i] = Math.max(dp[i+1], nums[i] + dp[i + 2]);
        return dp[0];
    }
    public int robIterBottom(int[] nums) {
        int[] dp = new int[nums.length];      
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        return dp[nums.length-1];
    }
    // DFS will TLE
    int robDFS(int i, int[] nums){
        if(i >= N) return 0;
        if(dp[i] == 0)
            dp[i] = max(
                dfs(i + 1, nums), 
                nums[i] + dfs(i + 2, nums)
             )
        return dp[i];
    }
}

322. 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.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    int inf = Integer.MAX_VALUE;
    Arrays.fill(dp, inf);
    dp[0] = 0;
    
    for(int i = 1; i <= amount; i++)
        for(int c: coins)
            if(i - c >= 0 && dp[i - c] != inf)
                dp[i] = Math.min(dp[i], 1 + dp[i - c]);

    return dp[amount] == inf ? -1 : dp[amount];
}

139. 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.

Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false

dp[i]: Can string upto index (i - 1) be broken with words from dict
Choices: words in dict
"lootcode" dict=["code", "de", "loot"]
dp[e] = for all words in dict ends at `e` ("code", "de"),
         assume you've chosen it and try if we can
         the string before it: "loot****" or "lootco**"
 Recurrence:
 dp[i + 1] = any(s[i-w.len()+1:i] == w && dp[i-w.len()+1])
                      where w in dict

public boolean wordBreak(String s, List<String> wordDict) {
    int N = s.length();
    boolean[] dp = new boolean[N + 1];
    dp[0] = true;
    for(int i = 0; i < N; i++)
        for(String w : wordDict){
            // 01234 - if choice word is of len 2,
            // 012 is the new subproblem (4-2+1)
            if(
                i - w.length() + 1 >= 0 && 
                s.startsWith(w, i - w.length() + 1) &&
                dp[i - w.length() + 1]
            ){
                dp[i + 1] = true;
                break;
            }
        }
    return dp[N];
}