Dynamic Programming (DP)

Longest palindrome subsequence problem (LPS) is the problem to find the length of longest subsequence in a string that is a palindrome. This can be done using Dynamic Programming in O(N^2) time.

The main goal of solving the Assembly Line Scheduling problem is to determine which stations to choose from line 1 and which to choose from line 2 in order to minimize assembly time. We solve this using Dynamic Programming.

There are d dice each having f faces. We need to find the number of ways in which we can get sum s from the faces when the dice are rolled. We have explored a Dynamic Programming solution to Dice Throw problem.

Given an array of n positive integers, find the sum of the maximum sum decreasing subsequence (msds) of the given array such that the integers in the subsequence are sorted in decreasing order.

In this problem (Longest Decreasing Subsequence), you are given an array of length N. You have to find the longest decreasing subsequence (LDS) from the given array. We have solved this using Dynamic Programming.

In this problem (Longest Common Decreasing Subsequence), we are given 2 arrays and we need to find out the longest common decreasing subsequence from those two arrays. This can be solved using Dynamic Programming.

In this problem (Maximum Sum Increasing Subsequence), we are given an array and we need to find out the maximum sum increasing subsequence from that array. This can be solved using Dynamic Programming.

In the Wildcard Pattern Matching problem, we find if a pattern matches a given input string. We will be using a Dynamic Programming approach with the time complexity of O(m * n), here m and n represent length of string and pattern respectively.

Given a string of integers, find the count of sub-strings of given string which are divisible by 6. This problem can be solved using Dynamic Programming in O(N) time complexity where N is the length of the string.

Given a square matrix of size N * N, where each cell is associated with a specific cost. Find the path with maximum average value in the 2D matrix. The path should start from top left point and end at bottom right point.

In this problem, we are given a number, we need to find the number of ways to reach it using increments of 1 and 2, given consecutive 1s not allowed.

You are given an array of n integers. The task is to find the sum of the subarray which has the smallest possible sum.

Divide and conquer optimization is used to optimize the run-time of a subset of Dynamic Programming problems from O(N^2) to O(N logN). We have demonstrated it with an example.

Knuth's optimization is used to optimize the run-time of a subset of Dynamic programming problems from O(N^3) to O(N^2). We have explained this with a sample problem.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money the robber can rob tonight without alerting the police. We have solved this problem using Dynamic Programming.

We need to find total number of substrings that are divisible by 8 but not 3 in the given string. We have solved this problem using Dynamic Programming in linear time O(N) where the brute force approach takes O(N^2) time.

Given an array of size N. Find the minimum number of increment or decrement operations to make the array in increasing order. In each move, we can add or subtract 1 to any element in the array.

The problem states that given a number or a score, we need to find the number of ways to reach it using increments of 1 and 2 with a constraint that consecutive 2s aren't allowed. We will solve this using Dynamic Programming in linear time O(N).

In this problem, we have to formulate an algorithm to find the minimum number of characters to be deleted to make the string a palindrome. This can be solved using the Dynamic Programming approach for longest palindromic subsequence in O(N^2) time.

In this article, we have explored the longest palindromic substring problem for which brute force takes O(N^3) time while a Dynamic Programming approach takes O(N^2) time.