We’re rewarding the question askers & reputations are being recalculated! Read more.

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
1answer
634 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 ...
2
votes
0answers
143 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 ...
2
votes
0answers
638 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 <...
0
votes
2answers
426 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 ...
2
votes
1answer
53 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 ...
3
votes
2answers
44 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 ...
7
votes
1answer
2k 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 ...
4
votes
2answers
77 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\...
3
votes
1answer
73 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" ...
3
votes
3answers
138 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 ...
4
votes
1answer
444 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 ...
2
votes
1answer
192 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: ...
1
vote
1answer
993 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'...
3
votes
2answers
141 views

Knapsack01 problem, written in c#

Is this code written in a decent style? Appreciate some feedback : ) ...
2
votes
0answers
36 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 ...
3
votes
1answer
410 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 ...
3
votes
2answers
2k 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 ...
3
votes
3answers
1k 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 ...
1
vote
1answer
486 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 ...
0
votes
1answer
118 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 ...
4
votes
1answer
850 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. ...
7
votes
3answers
144 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 ...
3
votes
0answers
123 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: ...
2
votes
2answers
2k 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 \$...
1
vote
0answers
282 views

ADACOINS - Ada and Coins TLE (SPOJ)

Ada the Ladybug has several coins in her wallet. She is wondering, how many different values [sum of some subset of coins] is she able to make (in given range). Input The first line contains two ...
1
vote
0answers
154 views

Buying Apples - SPOJ

THIS is the link to the problem on SPOJ. I thought it would be better to give the link to the problem instead of me trying to explain as the question is not very clear at first sight. I was able to ...
3
votes
1answer
147 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\$ ...
2
votes
0answers
895 views

minimum window subsequence leetcode dynamic programming solution

Given strings S and T, find the minimum (contiguous) substring W of ...
2
votes
1answer
66 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 ...
6
votes
1answer
242 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 ...
5
votes
1answer
530 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 ...
1
vote
0answers
126 views

x as the sum of unique integers raised to power n

I've done this problem using recursion. But I'm not sure that could this be optimized for bigger values of x using memoization. ...
1
vote
1answer
596 views

Compute the number of ways a given amount (cents) can be changed

Given an infinite number of different coin types (such as pennies, nickels, dimes, quarters) find out how many ways n cents can be represented. My code appears to work (although I am curious to ...
3
votes
1answer
249 views

Counting subsets with sum not exceeding some limit

I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the ...
2
votes
1answer
308 views

HackerRank Equal with Scala

For studying Scala, I wrote some code to solve the Equal problem on HackerRank. But I am stuck on test case #15 due to timeout. Christy is interning at HackerRank. One day she has to distribute ...
1
vote
1answer
70 views

Largest divisible subset optimization

So this is my solution to the following leetcode problem: https://leetcode.com/problems/largest-divisible-subset/description/ How could I optimize this code? I think the run time is \$\mathcal{O}(n^2)...
7
votes
1answer
183 views

Dynamic Programming with Project Euler problem 67

I am a beginner with python and programming in general. I started teaching myself about 2 months ago. I've been working my way through Project Euler and a few similar sites to build my chops, and ...
-3
votes
1answer
2k views

Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
2
votes
1answer
635 views

Coin Change Problem with Memoization

Purpose Another take on the classic Change-making Problem: Given some set of coins and a value, find the minimum number of coins necessary to add up to this value In my implementation, instead of ...
0
votes
1answer
173 views

Count number of ways to achieve a sum [closed]

The Question : Utkarsh being a very talkative child, was scolded by his teacher multiple times. One day, the teacher became very angry and decided to give him a very rigorous punishment. He ...
2
votes
1answer
786 views

Regular Expression Matching: Recursive and DP-based implementation

Problem Statement: Implement regular expression matching with support for '.' and '*'. '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching ...
3
votes
0answers
50 views

Number of ways to complete a plan

I worked on a dynamic programming problem. Here is its link. I have to find the number of ways respecting the constraint that user doesn't go to the Gym for two consecutive days. ...
3
votes
1answer
308 views

Path Finding using Dynamic Programming

I was trying to implement a dp + graph problem. After completing the solution I tried to compare it with solution in tutorial to figure out which one was better and to find a way to improve mine if I ...
2
votes
1answer
436 views

Find the length of the longest Common Subsequence

I have a DP based implementation for the Longest Common Subsequence(LCS) problem to find the length of the LCS. I wanted to know if there is room for improvement in terms of efficiency(space/time). ...
7
votes
2answers
512 views

Recursive function and memorization to find minimum operations to transform n to 1

I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution. ...
1
vote
2answers
76 views

NAddOdd - Topcoder - Single Round Match 714 Round 1 - Division I, Level Two

I am interested in DP problems from the past couple of days and am trying to solve various problems on topcoder. To be very frank could not even solve a single one till now. I went through https://...
5
votes
3answers
1k views

Maximum path sum in a triangle with prime number check

I was given this algorithm task: You will have a triangle input below and you need to find the maximum sum of the numbers according to given rules below; You will start from the top and move ...
2
votes
0answers
605 views

Hackerrank: Max Score

Problem statement Consider an n-element sequence of integers, A = {a0, a0, ..., an-1}. We want to perform \$n\$ operations on \$A\$, where each operation is defined by the following sequence of ...
0
votes
1answer
155 views

Using dynamic to avoid code duplication when wrapping an API

I am dealing with 3 different types of cameras from the same manufacturer and want to write a wrapper for their API. The API structure is like this: Camera1 and Camera2 use the class ...
6
votes
1answer
1k views

Longest common subsequence length and backtracking the string

Problem: Given two sequences, print the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “...