Dynamic Programming

Problem Statement: Given a m x n binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area. Examples Input: matrix = [[1,0,1,0,0],[1,0,1,1,1],[1,1,1,...

Problem Description: Given an integer array arr with length n, and an integer k, you may partition arr into one or more contiguous sub-arrays, where each sub-array has length in the range [1, k] (b...

Problem Statement: Given an n * m matrix of ones and zeros, return how many square submatrices have all ones. Examples Example 1: Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1]] Output: 15 Expla...

Problem Description: Given a string s, partition s such that every substring of the partition is a palindrome. Return the minimum cuts needed for a palindrome partitioning of s. Examples Input: s =...

Problem Statement: You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array. You are asked to burst all the balloons. If you burst the...

Problem Statement: Given an expression, A, with operands and operators (OR, AND, XOR), in how many ways can you evaluate the expression to be true, by grouping it in different ways?. Operands are o...

Problem Description: We are given a stick of length N and a cuts array of size C. The stick has markings as shown, and the cuts array depicts the marking at which the stick needs to be cut (shown i...

Problem Statement: Given a chain of matrices A1, A2, A3,.....An, you have to figure out the most efficient way to multiply these matrices. In other words, determine where to place parentheses to mi...

Problem Statement: Given a chain of matrices A1,..., An denoted by an array of size n+1, find out the minimum number of operations to multiply these n matrices . Examples Input : [40, 20, 30, 10, 3...

Problem Description: Given an integer array nums, find the number of Longest Increasing Subsequences (LIS) in the array. The Longest Increasing Subsequence (LIS) is the longest subsequence where al...