# Category: Dynamic Programming

## Weighted Interval Scheduling Problem

Given a list of jobs where each job has a start and finish time, and also has profit associated with it, find maximum profit subset of non-overlapping jobs.

## Box Stacking Problem

Given a set of rectangular 3D boxes, create a stack of boxes which is as tall as possible. A box can be placed on top of another box if the dimensions of the 2D base of the lower box are each strictly larger than those of the 2D base of the higher box. Multiple instances …

## Find total ways to achieve given sum with n throws of dice having k faces

Calculate total number of ways to achieve given sum with n throws of dice having k faces.

## Determine negative-weight cycle in a graph

Given a directed weighted graph, report a negative-weight cycle in the graph if any. A negative-weight cycle is a cycle in graph whose edges sum to a negative value.

## Find ways to calculate a target from elements of specified array

Write a program to count number of ways to calculate a target number from elements of specified array by using only addition and subtraction operator. The use of any other operator is forbidden.

## Collect maximum value of coins in a matrix

Given a M x N matrix where each cell contains a coin of some denomination, collect maximum value of coins by traversing the grid. The first traversal starts from the top-left corner of the matrix and end at the bottom-left corner and the second traversal starts from the top-right corner and end at the bottom-right …

## Count all paths in a matrix from first cell to last cell

Given a M x N rectangular grid, efficiently count all paths starting from the first cell (0,0) to the last cell (N-1,M-1) in the grid. We can either move down, or move towards right from a cell.

## Find length of longest path in the matrix with consecutive characters

Given a M x N matrix of characters, find the length of longest path in the matrix starting from a given character. All characters in the longest path should be increasing and consecutive to each other in alphabetical order.

## Check if a string matches with a given wildcard pattern

Given a string and a pattern containing wildcard characters, write an efficient algorithm to check if the input string matches with the wildcard pattern or not.

## Find all employees who directly or indirectly reports to a manager

Given a map containing employee to manager mappings, find all employees under each manager who directly or indirectly reports to him.

## Pots of Gold Game using Dynamic Programming

In Pots of gold game, there are two players A & B and pots of gold arranged in a line, each containing some gold coins. The players can see how many coins are there in each gold pot and each player gets alternating turns in which the player can pick a pot from one of …

## Find minimum cuts needed for palindromic partition of a string

Given a string, find minimum cuts needed to partition it such that each partition is a palindrome.