Skip to main content

Questions tagged [dynamic-programming]

Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.

Filter by
Sorted by
Tagged with
3 votes
2 answers
1k views

Counting the number of ways to decode a string

I am working on problem where I need to decode a string: A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... ...
user5447339's user avatar
2 votes
1 answer
781 views

Given a string and a word dict, find all possible sentences

I have been trying to figure out how to meet space and time complexity requirements for the following leet code question. I have come up with two versions, one that meets the time requirements and ...
Perplexabot's user avatar
8 votes
2 answers
447 views

(Codewars Kata) Memoised Log Cutting

(I am not sure of the official CS name for the problem in question, so I just gave it the name of the kata). Problem CLEAR CUTTER'S NEEDS YOUR HELP! The logging company Clear Cutter's ...
Tobi Alafin's user avatar
  • 1,796
3 votes
2 answers
252 views

Longest common subsequence solution

I've seen this today on a mock interview and wanted to give it a try. I'd love to hear some feedback from you guys. This is my second attempt at the problem, initially I had a mess of ...
fpezzini's user avatar
  • 306
3 votes
1 answer
110 views

Simple DP problem solved in compile time

The problem is taken from one of recent SO questions: Finding max sum of matrix elements with following constraints: Exactly one row element has to be included in the sum If element at (i, j) is ...
paler123's user avatar
  • 291
2 votes
1 answer
61 views

Number of way to render an amount of money

I made an algorithm to train my skill in dynamic programming and I would like to have feed back on it. This algorithm takes a money system (int) and have a certain ...
J. Toulmonde's user avatar
2 votes
3 answers
904 views

Leetcode #91 - Number of ways to decode a string

I'm working on problem 91 on Leetcode.com called Decode Ways and I've successfully managed to get a working recursive solution but it results in Time Limited ...
springathing's user avatar
1 vote
3 answers
1k views

Subarray Sum Equals K

I've written a solution to the following leetcode problem: Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example ...
loremIpsum1771's user avatar
0 votes
1 answer
2k views

Javascript Fibonacci with dynamic programming

Trying to applying what seen on What Is Dynamic Programming and How To Use It (here: https://www.youtube.com/watch?v=vYquumk4nWw ) Obviuously this is the final code, after removing the recursion. I ...
TheQult's user avatar
  • 268
1 vote
1 answer
994 views

Odd Even Subarrays

I've been trying to understand Dynamic Programming lately, here's the question I just attempted: You are given an array A of N positive integer values. A subarray of this array is called an Odd-...
Pranjal Verma's user avatar
-2 votes
1 answer
1k views

Dynamic Programming solution for one pile nim game

I have solved the following problem using dynamic programming: Little Deepu and his Girlfriend 1. To paraphrase, We have two players Little Deepu and Kate and M items in the bag B, also we have ...
Sidharth Singh's user avatar
1 vote
0 answers
90 views

selecting 5 best players out of 2 team

Let us assume that we need to develop an application which can select best 11 players to score maximum points. The application will select the best players after completion of a match. The rules are ...
ss321c's user avatar
  • 19
5 votes
3 answers
2k views

Find smallest number of squares that sum to a number

Leetcode problem 279 “Perfect Squares” is: Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) I wrote the following solution: ...
loremIpsum1771's user avatar
3 votes
1 answer
771 views

Minimum steps to 1 to find minimum operations to transform n to 1

I was doing this JavaScript problem called "Minimum steps to 1." You can find the problem here. Given a positive integer - num, Following is a list of possible operations which can be performed on ...
NinjaG's user avatar
  • 2,469
3 votes
1 answer
2k views

Coin sum dynamic programming in Python

I am preparing for an interview, and here's a popular problem on the dynamic programming. And I want to see if there's any feedback or code review for my solution at dynamic programming question. <...
NinjaG's user avatar
  • 2,469
3 votes
1 answer
10k views

Solving maze problem with backtracking solution using stack

I solved the maze backtracking question using a stack however could not find any other solution like that anywhere (to validate my solution is actually a valid one). The problem statement is as ...
crazyPixel's user avatar
3 votes
1 answer
410 views

Demonstration of the Largest Square Submatrix

Challenge Using the C++ language, have the function MaximalSquare(strArr) take the strArr parameter being passed which will ...
austingae's user avatar
  • 1,080
8 votes
4 answers
2k views

Project Euler #15: counting paths through a 20 × 20 grid

I've recently solved Project Euler's 15th problem stating: Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom ...
Gentlebud's user avatar
3 votes
2 answers
920 views

Memoized solution to Count number of ways to climb n steps

Problem statement : A Child is climbing up n steps with either 1 , 2, 3 hops ..how many ways can the child climb up the stairs? source: cracking the coding interview book. I have two solutions the ...
DntFrgtDSemiCln's user avatar
3 votes
1 answer
127 views

5 CPU's Task scheduling N process

Question. There are 5 CPUs and N number of tasks in the queue. You have to use minimum CPUs to process the tasks. A task is of format [arrival time, time to process the task]. Note: ...
Arjun Sunil Kumar's user avatar
6 votes
3 answers
2k views

Performance of dynamic Fibonacci generator and dead rabbits

I would like to improve my code style and its efficiency. I'm just moving beyond the standard recursive approach to a lot of simple algorithms. This post has two code snippets with slightly ...
julianstanley's user avatar
4 votes
1 answer
1k views

Solving the Burst Balloon problem using Dynamic Programming

Continuing where I left off previously to solve the problem described here, I've now solved the same using dynamic programming (following Tikhon Jelvis blog on DP). To refresh, the challenge is to ...
user3169543's user avatar
2 votes
0 answers
461 views

Smith-Waterman algorithm for local sequence alignment with affine gap penalties

The following is a summary from the top of my head so please correct me if I'm wrong. See the Wikipedia article for more. This is about determining the (score / edit distance of the) most similar ...
ngmir's user avatar
  • 121
3 votes
0 answers
2k views

Robot on a Grid: Find a path between two corners with forbidden cells on the road

Problem statement The problem is defined in the book as following: 8.2 Robot in a Grid Imagine a robot sitting on the upper left corner of grid with r rows and <...
Igor Soloydenko's user avatar
0 votes
2 answers
943 views

Number of Paths (BackTracking) in Java

Illustration You're testing a new driverless car that is located at the Southwest (bottom-left) corner of an n×n grid. The car is supposed to get to the opposite, Northeast (top-right), corner ...
Anirudh Thatipelli's user avatar
2 votes
1 answer
79 views

Dynamic programming to solve two printers with different speeds

I solved this problem using a Class, but thought I might try to figure out this memoization thing. Problem There are two printers that print pages at different speeds (X, Y). What is the minimum ...
Raystafarian's user avatar
  • 7,159
3 votes
2 answers
63 views

Splitting uppercase letters based on a dictionary

A few days ago I learned about the dynamic programming approach to problem-solving; the thing is, I'm still not sure I am fully grasping the concept. I decided to write an algorithm that takes a ...
Pat's user avatar
  • 31
8 votes
1 answer
4k views

Minimum cost path of matrix using Python

I was reading this article about finding the minimum cost path from (0,0) to any (m,n) point in a matrix. Using python the ...
kingJulian's user avatar
3 votes
2 answers
145 views

Finding sum of sub vector satisfying inequality

I am asked to implement code that checks if there is a sub vector that has a sum, v_l, that would satisfy \$ \frac{1}{4}mn + 1 \leq v_l \leq v - \frac{1}{4} m n - 1\...
albusSimba's user avatar
3 votes
1 answer
91 views

Dynamic DOM Text Editor Performance

I am creating a text editor that will need to work in the browser, syntax highlight, and allow users to edit files up to 50MB in size (i.e. the space allowed by indexedDB) without an "out of memory" ...
Jack G's user avatar
  • 133
3 votes
3 answers
329 views

SPOJ Emoticon challenge

I tried this spoj problem and solved it using Dynamic Programming, but I was getting Time Limit Exceeded. The challenge is to count the number of occurrences of the subsequence "KEK" in each input ...
Turtle's user avatar
  • 165
5 votes
1 answer
666 views

Longest Arithmetic Progression Algorithm

Problem Statement: > Given a sorted array, find the length of the longest arithmetic progression in it. Examples: numbers = new int[]{1, 3, 4, 5, 7, 8, 9} The length is 5, and the ...
Jianmin Chen's user avatar
  • 2,396
2 votes
1 answer
230 views

Check the equality for each subset of a string S against the target T and return a count

I wrote the following code to solve this leetcode problem: ...
Fahd Ahmed's user avatar
1 vote
1 answer
2k views

Project Euler Problem 31 (Coin Sum)

I just finished Project Euler 31: Coin sums, which asks how many ways there are to make £2 using British coins (1p, 2p, 5p, 10p, 20p, 50p, £1, and £2). When I compared my code and the problem review'...
Quang Truong's user avatar
3 votes
2 answers
166 views

Knapsack01 problem, written in c#

Is this code written in a decent style? Appreciate some feedback : ) ...
reviewee's user avatar
2 votes
0 answers
50 views

Optimizations for Knapsack with 3 dimensions

Problem Statement: I am given a set of prices for \$n\$ items I have to find out what is the maximum value I can get with \$M\$ money by selecting exactly \$C\$ items without exceeding the amount of ...
ng.newbie's user avatar
  • 171
3 votes
1 answer
924 views

SPOJ - Alphacode, using dynamic programming

I am currently trying out a programming problem, SPOJ Alphacode, that involves dynamic programming. In an encoding system where A=1, B=2, …, Z=26, a message 25114 ...
ianc1339's user avatar
  • 222
4 votes
2 answers
3k views

Dynamic programming solution to "Climbing Stairs"

This is the "Climbing Stairs" problem from leetcode.com: You are climbing a stair case. It takes \$n\$ steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many ...
NinjaG's user avatar
  • 2,469
3 votes
3 answers
2k views

Tower Hopper problem recursive approach

The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from ...
jeremy radcliff's user avatar
1 vote
1 answer
915 views

Solving "Quadruple sum" problem using dynamic programming

I am trying to learn dynamic programming using hash table. I was given this the "Quadruple sum" problem from firecode.io as a challenge: Given a sorted array of integers and an integer target, find ...
NinjaG's user avatar
  • 2,469
0 votes
1 answer
456 views

Maximum sub array sum equal to k

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. For example: Input: nums = [1,1,1], k = 2 Output: 2 ...
MrKickass's user avatar
4 votes
1 answer
1k views

Maximum sum of non-consecutive elements of an array

You are given a list of houses on a street, with the numeric value representing the amount of money stashed away in each house. Write a method to find the maximum amount of money you can steal. ...
NinjaG's user avatar
  • 2,469
8 votes
3 answers
294 views

Splitting a rectangular chocolate bar

I'm having trouble with my school homework. I have a chocolate bar that consists of either black, white or black&white (mixed) squares. I'm supposed to divide it in two groups, one that has only ...
Peter's user avatar
  • 81
3 votes
0 answers
144 views

Convert top-down subset sum to bottom-up

I have written the code for calculating subset-sum and also printing the first encountered non-empty subset from the left that sums up to the given sum. My code in Java is as follows: ...
ng.newbie's user avatar
  • 171
3 votes
2 answers
4k views

"What is the fastest solution for finding the maximum sum of a subarray?"

Question Given an array, find the longest continuous sub-array which has maximum sum. My Approach First, I solved this problem using dynamic programming which effectively solved the problem in \$...
enigma6174's user avatar
3 votes
1 answer
430 views

Find the maximum possible summation of differences of consecutive elements

Array A contains the elements, \$A_1,A_2, \ldots, A_N\$. And array B contains the elements, \$B_1,B_2, \ldots, B_N\$. There is a relationship between \$A_i\$ and \$B_i\$: any element \$A_i\$ ...
kumarmo2's user avatar
  • 261
2 votes
0 answers
1k views

minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
noman pouigt's user avatar
2 votes
1 answer
90 views

dynamic programming solution for a string ending with 0, 1 or 2

A string that contains only 0s, 1s, and 2s is called a ternary string. Find a total ternary ...
noman pouigt's user avatar
6 votes
1 answer
975 views

Printing bowTie pattern in efficient and pythonic way

I've posted code/library to GitHub for first time over here. The code is pretty simple. It generates a BowTie pattern of given size and characters. I did attempt to implement DP by calculating only ...
Anil_M's user avatar
  • 163
4 votes
1 answer
789 views

Count ways to reach the n’th stair

I have solved Leetcode climbing-stairs problem which is stated as: There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a ...
arshovon's user avatar
  • 205