Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
3
votes
0answers
36 views
Subset sum whose set contains only positive integers
I was trying to write a dynamic programming algorithm using a bottom up approach that solves the subset sum problem's version where the solution can be either an empty set and the initial set can only ...
5
votes
2answers
44 views
Finding the rod pieces in the rod cut issue
I have been reading the chapter 15 of "Introduction to Algorithms" (3rd edition) by Cormen, etc. The chapter 15 is about dynamic programming, and the first example they show us is the "rod cut ...
0
votes
1answer
31 views
LeetCode Minimum Path Sum algorithm
I am attempting to solve the Minimum Path Sum algorithm problem and I have a working solution, however there was an unwritten requirement that the algorithm not exceed an unspecified amount of time ...
4
votes
1answer
54 views
HackerRank - Candies
Here is the solution I've written for Hacker Rank Candies challenge.
It uses dynamic programming (memoization in a boxed array).
I'm interested on what could be done to improve this code in term of ...
3
votes
1answer
81 views
Calculating the sum of array elements to the left and right
I am using C++ to code the following logic:
An Array is given we have to traverse the array such that sum of array elements to its left must be equal to sum of elements to its right.
BTW this is ...
6
votes
3answers
73 views
ChessMetric - Topcoder Challenge
My solution for the topcoder ChessMetric challenge seems really slow. I feel like there should be a better way, but I'm not sure.
Challenge Description
Suppose you had an n by n chess board ...
4
votes
1answer
38 views
AvoidRoads - TopCoder Challenge
I'm learning Dynamic Programming, following the topcoder guide. I just solved the AvoidRoads challenge. It passes all the test cases, but I don't have much experience, so I don't know if it's good.
...
7
votes
2answers
65 views
Minimum number of coins problem using dynamic programming - follow up
I previously posted a code here. It turns out that the code is not following the correct dynamic programming principles and instead it was based on a greedy approach. Hence, I started again, keeping ...
10
votes
3answers
565 views
Coin Change: Minimum number of coins
Problem:
You are given n types of coin denominations of values \$v(1) < v(2) < ... < v(n)\$ (all integers). Assume \$v(1) = 1\$, so you can always make change for any amount of money ...
1
vote
2answers
68 views
BadNeighbors - Topcoder puzzle
I'm learning Dynamic Programming, following the topcoder guide. I just solved the BadNeighbors puzzle. It passes all the test cases, but I don't have much experience, so I don't know if it's good.
...
4
votes
3answers
36 views
Max contiguous slice in Ruby
I need to compute the max contiguous slice in an array. I wrote this function, but I am not sure if it is correct or I am missing edge cases. I ran several cases.
...
2
votes
1answer
44 views
Implementation of Sequence Alignment in C++
Below is my implementation of the dynamic programming solution to the sequence alignment problem in C++11:
...
13
votes
5answers
748 views
DP example for “Power of Two” in Python
I'm not familiar with Python but want to provide a code snippet for an SO question about Dynamic Programming.
The snippet should show the bottom-up approach of DP.
The function ...
10
votes
1answer
113 views
House-coloring optimization challenge
I have an interview coming up in the next few weeks, and I'm choosing to be interviewed in Python. I began programming in Python (it was about four years ago), so the syntax is natural to me, but I ...
10
votes
2answers
207 views
Undo format when format disappears
I was posed a question as follows:
Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, ...
5
votes
1answer
74 views
Longest Increasing Subsequence
I am learning dynamic programming and I have written down some code for longest increasing subsequence. I would like to know if there is any case or any area of improvement in the terms of ...
6
votes
2answers
82 views
Counting Increasing Subsequences of size K recursive
The original description of the problem can be found here, its input here and its expected output here.
The problem:
Given a integer sequence a1 ... an (-10000
\$\leq\$ ai \$\leq\$ 10000). ...
3
votes
4answers
119 views
Find the minimum number of coins
I'm trying to learn dynamic programming and the most popular one is to find the minimum number of coins for the change. I come up with this but I just want to improve this code which I think it could ...
5
votes
1answer
50 views
Optimal way to annihilate a list by removing items from the ends
I'm stuck with a contest problem.
Description:
What is the minimum number of moves to annihilate an int array where the possible moves are:
Remove both the first and last elements if they are ...
4
votes
2answers
384 views
Finding all the subsets in an array of integers that sum to a given target
Problem Statement:
Given an Array if ints, Find out all the subsets in the Array that
sum to a given target value.
Example:
If the input array is:
...
5
votes
1answer
405 views
Minimum number of coins - (dynamic programming solution - topdown approach)
This is a problem from topcoder tutorials
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 ...
8
votes
1answer
148 views
Reading, processing and counting an array setting limits
Last weekend my teacher asked me to create code to solve a problem:
Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array ...
2
votes
1answer
298 views
Solving the rod-cutting problem using dynamic programming
I've written what I believe is a valid dynamic programming solution to a variation of the rod cutting problem. In this problem, the goal is to make as few cuts as possible on a rod of length n.
I ...
1
vote
0answers
246 views
DP algorithm to find minimum average wait for customer-serving system
Below is the code to find the minimum average waiting time for customers at a store. I want improve the time complexity of the code. As an overview of the logic, I start from ...
4
votes
1answer
135 views
Optimizing a dynamic programming solution for “Oil Well”
I'm trying to solve the Oil Well problem on Hackerrank using dynamic programming and it works. However, it times out for some of the test cases. I wanted to know how this program can be improved so ...
1
vote
1answer
173 views
Coin problem through brute force
I have some code that will brute force solve the following problem:
Given a set of x coins and a target sum to reach, what is the fewest number of coins required to reach that target?
The code ...
7
votes
1answer
534 views
Project Euler #14 — longest Collatz sequence
I was reading this question and realized that I didn't know Python well enough to critique the algorithm. So I wrote a Java solution instead, which is inappropriate for that question. Since there's ...
3
votes
1answer
243 views
Calculate possible balances in piggy-bank by weight
I have solved Piggy-Bank problem on SPOJ using dynamic programming.
The question asks you to get the minimum value that is possible with given weight (\$w\$) and one or more coins (\$n\$) with given ...
5
votes
1answer
181 views
Word break problem with dynamic programming
This is the original question.
I have implemented it in both ways. If I enter the word "icecream", should I output "ice" "cream" and also "icecream", or just "ice" and "cream"?
Is this a good ...
2
votes
1answer
62 views
Memoization for calculating minimal traversal distance within a positive matrix
The code below is for calculating the minimal traversing distance from the top left point of the matrix to the bottom right point of the matrix.
GitHub
Here is the core functionality. Please note ...
3
votes
1answer
183 views
Google CodeJam Round D APAC Test
Problem A:
Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the ...
3
votes
1answer
150 views
Dynamic Programming for printing additive numbers up to digits n
Edit: I am hoping to get some review / make sure I am understanding dynamic programming correctly.
I am trying to print out all additive numbers up to digits n using dynamic programming. Additive ...
3
votes
2answers
262 views
Longest Common Subsequence and Longest Subsequence Palindrome
The following code computes:
The longest common subsequence between two strings, where a subsequence of a sequence does not have to consist of contiguous elements of the sequence.
The longest ...
8
votes
3answers
345 views
Handling shared state among a lot of elements in Angular
I am working on a project in Angular where I have a number of similar data objects. When you click on anyone of them it's state and amount of data shown will change. All of the objects start in the ...
2
votes
2answers
318 views
Longest collatz sequence using dynamic programming
I am trying to solve longest collatz sequence problem under 1000000 with the below code. Can anyone suggest a faster way to approach this problem? I was thinking of dynamic programming, but I'm ...
4
votes
3answers
713 views
Project Euler 81 (minimum path sum through a matrix)
Problem Statement:
In the 5 by 5 matrix below,
131 673 234 103 18
201 96 342 965 150
630 803 746 422 111
537 699 497 121 956
805 732 524 37 331
...
11
votes
3answers
889 views
Substitution cipher algorithm performance boost
This algorithm is meant to read a string of numbers on an input, a naive substitution cipher code (A = 1, B = 2, ..., Z = 26) and output the number of ways the code could be interpreted (e.g. 25114 ...
1
vote
2answers
92 views
Making operations more dynamic
I am trying to build something that will allow us to configure "custom" validation for each customer. So if a customer wants to see a value contain a specific char, be specific length, or equal ...
4
votes
1answer
1k views
Determining maximum profit to be made from selling shares
Question
Your algorithms have become so good at predicting the market that you
now know what the share price of Wooden Orange Toothpicks Inc. (WOT)
will be for the next \$N\$ days.
...
2
votes
2answers
169 views
Calculating the number of prime numbers to solve the puzzle
How can the following program execution time improved? I have used dynamic programming in both "recursive" as well as "prime" function, but I'm not getting the efficient execution time.
There is ...
12
votes
5answers
3k views
Dynamic programming with Fibonacci
I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code.
...
4
votes
1answer
127 views
NGON (many polygons) on SPOJ
I am trying to solve NGON problem. I am using bottom up dynamic programming here. Recurrence function is:
$$\begin{array}{rl}
f(a,b) &= f(a-1,b) + f(a-1,b-1)\,a_i ...
10
votes
1answer
96 views
Loading Data Warehouse with Dynamic SQL
For a data warehousing project I ran into the following:
Custom fields that users can create, modify and delete, that should be loaded into the data warehouse as they are when the ETL happens.
On ...
2
votes
1answer
260 views
Determine if subset in int array adds up to a given input integer
Given a set of non-negative integers, and a value sum, determine if there is a subset
of the given set with sum equal to given sum. On similar lines, Partition problem is to determine whether a given ...
4
votes
2answers
173 views
The Three-machine proportionate flow shop problem with unequal machine
As part of an Academic project I wrote the following code, according to the algorithm (verbal). When I checked the rest of the article I notice that the efficiency should be \$O(n^2)\$ and I wrote ...
4
votes
1answer
192 views
Dynamic programming with Project Euler #18
I just wanted to get an opinion on my dynamic-programming Haskell implementation of the solution to Project Euler problem 18.
The Problem:
By starting at the top of the triangle below and moving ...
5
votes
2answers
2k views
Optimizing O(m n) solution for longest common subsequence challenge
Given two strings string X of length x1 and string Y of length ...
7
votes
1answer
165 views
Three-machine proportionate flow shop problem with unequal machine
As part of an academic project I wrote a code about dynamic programming that solves the "Three-machine proportionate flow shop problem with unequal machine".
In flow shop scheduling it is usually ...
10
votes
3answers
632 views
Optimizing “Herd Sums” problem using dynamic programming
I'm trying to solve a practice problem and all is well except for the last 2 inputs my solution is too slow. Just one loop is slowing it down I think.
Herd Sums
Execution Time Limit: 2 ...
5
votes
2answers
785 views
Finding alternating sequence in a list of numbers
Please be brutal and treat this as me coding this up for an interview.
A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between ...
