Practice/Solve DP on Array Problems

How to Identify if Array problem has a DP solution?

Using Constraints: Generally, in Competitive Programming the required solution should perform nearly 10^7 to 10^8 operations, so if the array size N = 1000 to 5000 we can expect to have an N^2 DP solution, and for N = 100 we can have an N^3 DP solution. Minimize/Maximize Values: Dynamic Programming can be applied if the problem is to maximize or minimize any value over all possible scenarios. Various functions in the problem: If the question consists of functions f(x) as operations then we can try to think towards Dynamic programming. Greedy fails: If you can think of a test case where the Greedy solution fails, then the problem has a high chance of having a DP solution. Recursive Sub-Problems: Determining whether the problem has a recursive solution where an over-lapping subproblem occurs is a difficult task but if you manage to do that, then DP can be a solution if the constraints allow that....

Quick Approximation of DP Time & Space Complexity for Arrays:

Before coding the solution, we need to verify whether the time complexity of our solution fits the given constraints or not, we can approximate the time complexity using the below formula: Time Complexity = Total Number of States * ( 1 + Average number of Transitions per State) Space Complexity = Average number of States....

Why classical-DP problems differ than DP problems on Arrays?

The problems that we see on Competitive Programming platforms are mainly made up of two parts: Adhoc part Standard part The Adhoc part of the problem is the one that makes each problem unique and also the one that decides the difficulty of the problem. One needs to make several observations to deduce the Adhoc part into the standard solution. Good dp problems will often require you to make adhoc observations to figure out some properties that allow you to apply dp on them. Let’s us see how an Adhoc problem changes a standard DP problem: Problem: You are given N tiles 1 to N, and initially you are standing at 1. In one move you can make a jump of either 1 or 2 in forward direction. Determine the total number of ways you can reach from tile 1 to tile N. Example: N=4 Output: total 3 ways are possible Explaination: 1->2->3->4 1->2->4 1->3->4 Adhoc Part: The Adhoc part of the problem diverts the question towards thinking of moving on tiles from 1 to N in different ways, the programmer will dry run several test cases and make several observations in order to reach to the solution, he might even try to make some mathematical formula to calculate the solution. Standard Part: If observed carefully this question is nothing but print the N’th fibonacci number the simplest DP problem that might exist. each tile T can be reached only via previous two tiles that is T is dependent upon T-1 and T-2. Using This we can write the DP states as: Number _of_ways[i]= Number _of_ways[i-1] + Number _of_ways[i-2]...

DP for Precomputation on Arrays:

Storing Primality and Smallest Prime factor for First N natural number factors Using Seive Storing Factorials and Inverse Factorials for First N natural numbers:...

Recognizing which type of Standard DP can be used to solve Array Problems:

When tackling DP problems during a contest the most difficult task is to define the states and transitions for the problem. The states and transitions for problems are mostly the variations of existing standard DP problems, let us see how we can try to think towards a particular standard DP problem:...

Practice/Solve DP on Array Problems:

Problem Practice Link Minimum number of jumps to reach end (Jump Game) Solve Count number of coins required to make a given value (Coin Change II) Solve 0/1 Knapsack Problem Solve Sieve of Eratosthenes Solve Matrix Chain Multiplication Solve Longest Common Subsequence (LCS) Solve Longest Increasing Subsequence (LIS) Solve Longest Palindromic Substring Solve Save Your Life Solve Travelling Salesman Problem using Dynamic Programming Solve Floyd Warshall Algorithm Solve Count Unique Paths in matrix Solve Edit Distance Solve Cutting a Rod Solve...