Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
-4
votes
0answers
32 views
Get Possible sets of any given string [on hold]
I want to get result like this.
Example:
String text ="a";
String []result={"a"};
String text ="a b";
String []result={"a","b","a b"};
String text = "a b c";
String []result={"a","b","c","a b","b ...
3
votes
1answer
90 views
Number of unique sequences of 3 digits, given a length is equal to sum
This is the "Minion's bored game" problem from Google's "Foobar challenge":
There you have it. Yet another pointless "bored" game created by the bored minions of Professor Boolean.
The game ...
2
votes
1answer
24 views
Longest Increasing Sub-Sequence using Dynamic Programming in Python
I wrote the following function to find the longest increasing sub-sequence in an array (tuple, it doesn't work for a list since a list is mutable and it stores the results in a dictionary.). It uses ...
1
vote
0answers
28 views
Shortest bitonic tour
This a solution to the shortest bitonic tour using dynamic programming. Bitonic tour starts at the leftmost point then goes strictly rightward to the rightmost point and finally strictly leftward to ...
4
votes
2answers
53 views
Rod-Cutting Problem using dynamic programming
I wrote the following code for solving the Rod-Cutting Problem using dynamic programming:
Rod Cutting Problem: Given a rod of length n inches and an array of prices that contains prices of all ...
1
vote
0answers
42 views
Longest palindrome subsequence
This algorithm finds the longest palindrome that is a subsequence of a given input string in \$\Theta(n^2)\$.
Example
Input: character
Output: ...
0
votes
2answers
73 views
google foo.bar max path algorithm puzzle optimization [closed]
I got a programming puzzle described as follows:
Save Beta Rabbit
Oh no! The mad Professor Boolean has trapped Beta Rabbit in an NxN
grid of rooms. In the center of each room (except for ...
-2
votes
0answers
52 views
Can anybody help me with this (graph theory)?
I am preparing for job interviews and learning Analysis and design of algorithms. I have solved many problems using dynamic programming and greedy methods, but I am struck with this problem and unable ...
3
votes
2answers
45 views
Candie distribution algorithm
I am studying algorithms and I solved this problem under Dynamic Programming section:
Alice is a kindergarten teacher. She wants to give some candies to the
children in her class. All the ...
0
votes
1answer
27 views
Loading URLs via a case statement
I have the following code which loads in a URL based on the id of a user-clicked button. I'm looking to compress it down as much as possible, and make it more modular and reusable:
...
3
votes
2answers
145 views
High execution time of LCS length program in Python2
I was trying to solve the Longest Common Subsequence problem on a HackerRank exercise.
It's quite simple and straightforward, just print out the length of the LCS. I submitted this code:
...
2
votes
2answers
38 views
Find the best path amongst N random points
For an application with a graphical canvas, I want to generate N points. But then I want to link those points, and I want to find the best path through those points.
I wanted to use a dynamic ...
1
vote
1answer
63 views
Levenshtein distance with edit sequence and alignment in Java
I have this program that computes a Levenshtein distance of the two input strings, their edit sequence, and the alignment:
LevenshteinEditDistance.java:
...
4
votes
2answers
54 views
Number of ways to make change for an amount
Task
Write a program that, given the amount to make change for and a list of coins prints out how many different ways you can make change from the coins to STDOUT.
My approach
The number to make ...
2
votes
1answer
36 views
Optimally allocating a resource with time-varying demand and cost
I'm working on the following DP which finds the optimal way to allocate a resource. At each time step I can either allocate (0.2 resources) at cost C or not in which case the storage is reduced by the ...
2
votes
1answer
18 views
Auto registering class registry
I built this auto registering registry to look into a package and import all modules and register any classes that are a subclass of a base class. I use it as a registry for a model's choices in ...
4
votes
1answer
167 views
Finding the longest path, avoiding obstacles in a 2D plane
The Scenario
You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
0
votes
1answer
62 views
Longest contiguous Increasing Subset in java
I have tried to come up with a solution to the longest increasing subsequence problem.Can this solution be optimized further?
Example 1:
Input: {5,4,3,7,8,9,11}
Output: 3, 7, 8, 9, 11
Example 2:
...
2
votes
1answer
83 views
4
votes
5answers
237 views
Pass Triangle challenge
In order to solve this challenge:
Challenge Description
By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.
...
11
votes
2answers
113 views
Dynamic Programming: Fibonacci-like recurrence relation
This is a problem from my Introduction to Algorithms textbook.
Consider the infinite sequence of numbers An|n>0 = (1,1,3,4,8,11,...) defined recursively as follows.
$$
A_n = \left\{\begin{aligned}
...
4
votes
2answers
101 views
Optimal matrix chain multiplication in Java
Preliminaries
Given two matrices
$$
A = \begin{pmatrix}
a_{11} & a_{12} & \dots & a_{1q} \\
a_{21} & a_{22} & \dots & a_{2q} \\
\vdots & \vdots & \ddots & \vdots ...
2
votes
0answers
44 views
Recursive implementation of integer partition without re-arrangement
Problem: Integer partition without re-arrangement
Input: An arrangement S of nonnegative numbers {s1, . . . , sn} and an ...
8
votes
2answers
233 views
Quick Sum TopCoder (Brute Force solution)
Given a string of digits, find the minimum number of additions
required for the string to equal some target number. Each addition is
the equivalent of inserting a plus sign somewhere into the ...
11
votes
1answer
142 views
Counting paths in an n-dimensional grid that stay within the boundaries
Problem Statement
You are situated in an N dimensional grid at position (x1, x2, …, xN).
The dimensions of the grid are (D1, D2, …, DN). In one step, you can
walk one step ahead or behind in ...
0
votes
0answers
14 views
Time Complexity Analysis,Linear Sliding Window Algorithm Fails in SPOJ Aliens in a Train?
I need to find the largest interval with Value Less than a Limit Lt.
The Data is as Follows
For Every Test Case T
Number of elements N , limit Lt
N number of elements data
I wrote the ...
9
votes
3answers
318 views
Find the Nth number divisible by only 2,3,5, or 7
I recently participated in a small friendly competition and this was one of the questions:
A number whose only prime factors are 2, 3, 5 or 7 is called a humble
number. The first 20 humble ...
2
votes
1answer
55 views
Implementation of Longest Common Subsequence
So I implemented the LCS algorithm once using a 2-D matrix to store values while the other one used a python dictionary. I found the dictionary implementation was easier to implement and was a more ...
2
votes
0answers
91 views
Multiple 0-1 knapsack
I have a problem were the time in minutes of N songs are given and I have to write the maximum number of time in K CDs.
Input description
The first input line consists of two positive integers N ...
2
votes
1answer
53 views
Construct biggest stacked tower with restriction
Problem
The problem is to build the tallest tower made up of cylinders, respecting all the rules.
Will be arranged on the table, an amount of \$N\$ cylinders.
Each cylinder has one color: Red, ...
3
votes
1answer
227 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
364 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 ...
1
vote
1answer
183 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
309 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
522 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
135 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
65 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
113 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
1k 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
116 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.
...
3
votes
3answers
49 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
532 views
Implementation of Sequence Alignment in C++
Below is my implementation of the dynamic programming solution to the sequence alignment problem in C++11:
...
14
votes
5answers
1k 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
331 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
218 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, ...
6
votes
1answer
242 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
253 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
579 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
53 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
2k 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:
...
