Dynamic Programming

When to Use DP

The problem can be broken down into "overlapping subproblems" - smaller versions of the original problem that are re-used multiple times
The problem has an "optimal substructure" - an optimal solution can be formed from optimal solutions to the overlapping subproblems of the original problem

Unfortunately, it is hard to identify when a problem fits into these definitions. Instead, let's discuss some common characteristics of DP problems that are easy to identify.

The first characteristic

The first characteristic that is common in DP problems is that the problem will ask for the optimum value (maximum or minimum) of something, or the number of ways there are to do something. For example:

What is the minimum cost of doing...
What is the maximum profit from...
How many ways are there to do...
What is the longest possible...
Is it possible to reach a certain point...

The second characteristic

The second characteristic that is common in DP problems is that future "decisions" depend on earlier decisions. Deciding to do something at one step may affect the ability to do something in a later step. This characteristic is what makes a greedy algorithm invalid for a DP problem - we need to factor in results from previous decisions. Admittedly, this characteristic is not as well defined as the first one, and the best way to identify it is to go through some examples.

Example 1 : House Robber problem

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. Alert will send to police if two adjacent houses were broken into on the same night.

nums = [2, 7, 9, 3, 1]

In this problem, each decision will affect what options are available to the robber in the future. For example, with the test case nums = [2, 7, 9, 3, 1]nums = [2, 7, 9, 3, 1], the optimal solution is to rob the houses with 22, 99, and 11 money. However, if we were to iterate from left to right in a greedy manner, our first decision would be whether to rob the first or second house. 7 is way more money than 2, so if we were greedy, we would choose to rob house 7. However, this prevents us from robbing the house with 9 money. As you can see, our decision between robbing the first or second house affects which options are available for future decisions.

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

In this problem, we need to determine the length of the longest (first characteristic) subsequence that is strictly increasing. For example, if we had the input nums = [1, 2, 6, 3, 5]nums = [1, 2, 6, 3, 5], the answer would be 4, from the subsequence [1, 2, 3, 5][1, 2, 3, 5]. Again, the important decision comes when we arrive at the 6 - do we take it or not take it? If we decide to take it, then we get to increase our current length by 1, but it affects the future - we can no longer take the 3 or 5. Of course, with such a small example, it's easy to see why we shouldn't take it - but how are we supposed to design an algorithm that can always make the correct decision with huge inputs? Imagine if nums contained 10,00010,000 numbers instead.

The Framework

To solve a DP problem, we need to combine 3 things:

A function or data structure that will compute/contain the answer to the problem for every given state.
1. Typically, top-down is implemented with a recursive function and hash map
2. Bottom-up is implemented with nested for loops and an array.
3. When designing this function or array, we also need to decide on state variables to pass as arguments.
A recurrence relation to transition between states.
Base cases, so that our recurrence relation doesn't go on infinitely.

House Robber Problem

nums = [2, 7, 9, 3, 1]

Logic : At current element, select it or don't select it.

Without DP

class Solution {
    private int[] memo;
    public int rob(int[] nums) {
        return robHelper(nums, 0);
    }
    public int robHelper(int[] nums, int i) {
        if (i >= nums.length) {
            return 0;
        }
        int sol1 = nums[i] +  robHelper(nums,i+2);
        int sol2 =  robHelper(nums,i+1);
        int result = Math.max(sol1, sol2);
        return result;
    }
}

With DP



class Solution {
    private int[] memo;
    public int rob(int[] nums) {
        this.memo = new int[100];
        Arrays.fill(memo, -1);
        return robHelper(nums, 0);
    }
    public int robHelper(int[] nums, int i) {
        if (i >= nums.length) {
            return 0;
        }
        if (memo[i] != -1){
            return memo[i];
        }
        int sol1 = nums[i] +  robHelper(nums,i+2);
        int sol2 =  robHelper(nums,i+1);
        int result = Math.max(sol1, sol2);
        memo[i] = result;
        return result;
    }
}

Min Cost Climbing Stairs

You are given an integer array cost where cost[i] is the cost of i'th 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.

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.

class Solution {

    private HashMap<Integer, Integer> memo = new HashMap<Integer, Integer>();

    public int minCostClimbingStairs(int[] cost) {

        return minCostClimbingStairsHelper(cost, cost.length);
    }

    public int minCostClimbingStairsHelper(int[] cost, int i) {

        if (i <= 1) {
            return 0;
        }

        if (memo.containsKey(i)) {
            return memo.get(i);
        }
        int result1 = cost[i-1] + minCostClimbingStairsHelper(cost,i-1);
        int result2 = cost[i-2] + minCostClimbingStairsHelper(cost,i-2);

        int result = Math.min(result1, result2);
        memo.put(i, result);

        return result;
    }
}

Shyam Kunda