In this article, we have explained How to approach a Dynamic Programming problem with an example. The approach depends on the constraints of the problem at hand.

DP problems are one of the most important topics for interviews, and can be mastered only with practice.

For most of the students DP problems are actually easy to understand, but difficult to recognize when and how to apply it to solve a problem.

So how to approach DP problems??

1 : Always start with greedy solution.
2 : If greedy solution doesn't work, solve the problem using recursion, trying out all possiblities.

"Now we are sure that we have a working solution"

3 : A big hint you can get weather a problem is solvable using DP or not, is from the constraints for a given problem.

"Lets take n as our constraint for a problem" and considering time limit is 1 or 2 seconds then,

4 : If n <= 15, your recursive solution, or we can say backtracking solution works fine, good to go and start coding. So time complexity should be exponential.

5 : If n <= k * 10000 so order of 10^4, high chances are there that you need to apply 2-d DP to solve the problem. (1 <= k <= 5). So time complexity should be O(n^2).

6 : If n <= k * 100000 so order of 10^5, here a greedy solution or 1-d dp can be used to solve the problem. So time complexity should be O(n).

"It may seem difficult, but as told earlier practice is needed to be good at solving DP problems".

To understand it better, lets look at a problem and try to use the above points to solve the problem.

"Problem": Make Array Strictly Increasing

Problem says,
"Given two integer arrays arr1 and arr2, return the minimum number of operations (possibly zero) needed to make arr1 strictly increasing.

In one operation, you can choose two indices 0 <= i < arr1.length and 0 <= j < arr2.length and do the assignment arr1[i] = arr2[j].

If there is no way to make arr1 strictly increasing, return -1."

Example-
Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].

Constraints:

1 <= arr1.length, arr2.length <= 2000
0 <= arr1[i], arr2[i] <= 10^9

Solution Approach:

We can see from the constraint that n <= 2000 which fits in our 5th point.

How to approach this problem?
First idea that comes to our mind is greedily apply operations to make arr1 strictly increasing,
so, arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Lets iterate through arr1 and try do apply operations if needed greedily
1
1 5
1 5 3 (here we need to do an operation and change 3 with an element in arr2 such that new value is greater than 5)
1 5 ? we dont find any number in arr2 that is greater than 5, so according to our greedy solution, there is no solution, so it returns -1.

But wait..

What if we had changed second element in arr1 (5) with element (2) in arr2.
now arr1 -> [1,2,3,6,7] and now arr1 is strictly increasing, so minimum operations needed is 1, so we return 1.

So we see that greedy didn't work here, next idea should be to just brute force all the possiblities,
and now solution wil definitely work,
Time : n^m (exponential) where n - arr1.length and m - arr2.length
Since for every element in arr1 we have an option to do operation and change it with an element from arr2.

Then simply apply memoization, to avoid any repeated calculations.
Time Complexity : O(n * m)
Space Complexity: O(n * m)
Where n -> size of arr1, m -> size of arr2

But wait,
How to get dp recurrence relations now??
We can get it from our brute force recursive solution,
in brute force solution for each element in arr1, we try to do operation with each element in arr2, and then recursively call it for other elements in arr1,

so it would be like,
---->>>> i1 - > curr index in arr1, and i2 - > curr index in arr2

int recurse(arr1, arr2, i1, i2, prev_element_in_arr1) {
// so two states, dp[i1][i2]
// if we want/have to do an operation on element i1, now instead of trying all, we find the best operation, ie. min element greater than prev element, let it be k

int case1 = recurse(arr1, arr2, i1 + 1, k + 1, arr[k]);
// second case is no need of operation needed,
int case2 = recurse(arr1, arr2, i1 + 1, k, arr[i1]);

}

JAVA CODE:

class Solution {
    int[][] memo = new int[2001][2001];
    public int makeArrayIncreasing(int[] arr1, int[] arr2) {
        for (int[] mem : memo) {
            Arrays.fill(mem, -1);
        }
        // since the order of elements doesn't matter, we sort arr2 so can easily find upper or lower bound using binary search
        Arrays.sort(arr2);  
        int ans = minOperations(arr1, arr2, 0, 0, Integer.MIN_VALUE);
        return ans < 2000 ? ans : -1; 
    }
    private int minOperations(int[] arr1, int[] arr2, int index, int loIndex, int prev) {
        if (index >= arr1.length) { // no more elements left, i -> curr index
            return 0;
        }
        int k = upperBound(arr2, prev); // k -> replaceble value in arr2 for making array strictly increasing
        if (memo[index][k] != -1) {
            return memo[index][k];
        }
        int operationNeeded = (k < arr2.length) ? 1 + minOperations(arr1, arr2, index + 1, k + 1, arr2[k]) : 2000;
        int noOperation = arr1[index] > prev ? minOperations(arr1, arr2, index + 1, k, arr1[index]) : 2000;
        return memo[index][k] = Math.min(operationNeeded, noOperation);
    }
    private int upperBound(int[] arr2, int prev) {
        int lo = 0, hi = arr2.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (arr2[mid] > prev) {
                hi = mid;
            }else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

Additional techniques to solve a problem :

1 : If you have a working solution for a problem with time complexity of O(n^2) and want to optimize to O(n) complexity, try using prefix sum, or a sliding window technique, or stack data structure.

2 : If you have a working solution with time and space complexity of O(n), single linked list and doubly linked lists are really usefull to optimize it to O(1) space.

3 : When question asks you to find minimum or maximum of something, then a good technique is to apply binary search on range in which answer is possible, and then checking if that for mid answer is satisfying the conditions or not, and if it satisfies then say for minimum possible answer go to left part otherwise right part.

Detailed explanation about all these techniques will be covered in my next blog.

"I hope you enjoyed this, and was usefull for you all"!!

"If you find something worng in the blog, please do comment".

Thank you all!