Dynamic Programming

House Robber | Dynamic Programming

Problem: You have n houses with certain amount of money stashed in each house. You can not steal any adjacent houses. Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can steal. Solution: This is a simple dynamic programming problem. The key is Read More →

Edit Distance – DP Problem

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character Input: str1 = “cat”, str2 = “cut” Output: Read More →

Distinct Subsequences

Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is Read More →

Given a triangle, find the minimum path sum from top to bottom

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = Read More →

Robot in an MXN grid

Problem: A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid . How many possible unique paths are there? Approach 1(Recursion): Let NumberOfPaths(m, n) be Read More →

What is the Probability that a Knight Stays on Chessboard

knight_moves

Given the size of the chess board and initial position of the knight, what is the probability that after k moves the knight will be inside the chess board. Note:- 1) The knight makes its all 8 possible moves with equal probability. 2) Once the knight is outside the chess board it cannot come back Read More →

Min Number of Platforms Required for a Railway Station

At a bus-station, you have time-table for buses arrival and departure. You need to find the minimum number of platforms so that all the buses can be placed as per their schedule. For example consider the above example. arr[] = {9:00, 9:40, 9:50, 11:00, 15:00, 18:00} dep[] = {9:10, 12:00, 11:20, 11:30, 19:00, 20:00} All Read More →

Maximum size square sub-matrix with all 1s

Problem: Given a binary matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s. Example: Consider the below matrix. 0 1 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 The Read More →

The Coin Problem – Dynamic Programming

Given a list of N coins, their values (V1, V2, … , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use as many coins of one type as we want), or report that it’s not possible to select coins in such a way Read More →

Non overlapping maximum subsequence

Given n sequences, and starting and stopping point of every sequence with its score. For eg. no of sequences = 5 start stop score 0 4 4 3 10 11 6 8 8 7 15 10 11 15 4 All scores are positive. You have to find the maximum subset of non overlapping sequences having Read More →