Tagged Questions
Dynamic programming is an algorithmic technique for efficiently solving problems with a recursive structure containing many overlapping subproblems.
0
votes
0answers
5 views
Print the solution to the MEMOIZED-ROD-CUT
I'm reading about the "rod-cut" problem presented in the 15th chapter of the "Introduction to Algorithms" book (3rd ed.) by CLRS. There's an exercise, 15.1.4, which asks us:
Modify MEMOIZED-CUT-ROD ...
0
votes
0answers
20 views
Find the most efficient grouping of a series of intervals
I have an application where I have a series of non overlapping fixed width intervals, each of which have a given key. Each interval has the same width, and there may be contiguous intervals. ...
0
votes
1answer
26 views
ArrayIndexOutofBoundsException in Knapsack Scala
I am trying to solve Knapsack problem in Scala using dynamic programming .As a part of requirement I also need to show which items are picked to be filled in Knapsack.But I am getting "...
-4
votes
0answers
23 views
Dynamic programming (C++) - Coin Change [on hold]
I have a function 'bool change(int* nominals, int n, int amount, int* result)'. 'nominals' array is the array of positive integers ('n' is the size of 'nominals' array), any combination of those ...
1
vote
2answers
58 views
Java: How to create the shortest palindrome of a string by inserting the minimum number of characters?
I currently have the following implementation that handles finding the shortest palindrome with a given string by inserting the minimum number of characters, but only handling character insertions at ...
0
votes
0answers
11 views
Contact form 7- dynamically create input fields
I am using contact form 7 plugin. I want to add input fields like text box dynamically into form. I have following code but not sure how to use it in contact form 7.
<script>
$('#myTable').on('...
0
votes
1answer
15 views
Number of paths in mXn grid
Is there a way to find the number of paths in mXn grid moving one cell at a time either downward, right or diagonally down-right using Permutation, starting from (1,1) and reaching (m,n)? I know there ...
-1
votes
1answer
42 views
+50
Interesting assignment of values to a tree
Given a tree with X number of nodes we need to assign values to each node. You are also given two arrays A[] and B[] each of size X. Assignment to nodes should be done in such a manner that if you ...
1
vote
1answer
53 views
RodCutting: when the rod is bigger than the array length
How can I modify the methods cutRod and bottomUpCutRod to hold lengths that are bigger than the array length. For example, currently p has length 11, how can I cut the rod of length 15, 20 , etc, ...
-2
votes
0answers
20 views
Deleting a Dynamically created object or object pointer [closed]
I wanted to ask if we need to delete a dynamically created object or object pointer. If it is being created in the constructor. If i do not delete it, will there be any problems in my computer or my ...
2
votes
1answer
30 views
Minimum cost of choosing items from n buckets
I have n numbers of buckets. Each bucket contains 3 items - say I1, I2 & I3. Each item has their own cost associated. You have to pick items from each bucket such that items picked from 2 ...
-1
votes
1answer
67 views
Algorithm to find ideal starting spot in a circle [closed]
So the problem I have been debating is as such:
Your are given an array of integers representing a circle. Then, you have to pick spot in the circle to start. From the place you start, you compare ...
1
vote
0answers
28 views
Maximum number divisible by another one created from sum of previous numbers
There are given numbers 1, 2, ...., b-1. Every number of these can be used a[1], a[2], ...., a[b-1] times.
From them the biggest possible number (from data given) has to be concatenated, while sum of ...
-3
votes
0answers
27 views
Dynamic Programming
I found this interesting DP problem on a site (Or what I think is DP anyway). It involves being given an array of size n and then finding out what number of sets of elements can be removed from it to ...
5
votes
4answers
108 views
Efficient algorithm to find number of elements less than a query
I have two unsorted arrays a and b. For every element a[i] I need to find the number of elements b[j] such that b[j] < a[i]. In addition b may contain duplicates which should not be counted. Both ...
-2
votes
2answers
44 views
Find minimum cost of tickets
Find minimum cost of tickets required to buy for traveling on known days of the month (1...30). Three types of tickets are available : 1-day ticket valid for 1 days and costs 2 units, 7-days ticket ...
-1
votes
0answers
43 views
Dynamic Programming Logic
For homework, I need to implement dynamic programming to solve a problem that roughly asks:
Given a vector of values of items V, determine the least number of additions
of individual values to reach ...
0
votes
2answers
49 views
Java: How to implement Word Break?
I'm trying to understanding the following Java + Dynamic Programming implementation (https://pingzhblog.wordpress.com/2015/09/17/word-break/):
public class Solution {
public boolean wordBreak(...
-1
votes
0answers
45 views
Milly and the Magic Numbers [duplicate]
Can someone suggest optimized solution?
Milly likes to solve problems very much. Today she is solving a problem in which she has N, L and R and she has to find out the total count of Magic Numbers in ...
-1
votes
1answer
56 views
How to implement Word Break using Dynamic Programming in Java? [closed]
I'm following the Word Break implementation and trying to understand: https://pingzhblog.wordpress.com/2015/09/17/word-break/
But I do not get the Dynamic Programming part of it, especially how just ...
2
votes
3answers
92 views
Time and space complexity of dynamic programming algorithm
This algorithm is from Cracking the Coding Interview, 5th Edition, found here: https://www.geekbooks.me/book/view/cracking-the-coding-interview-5th-edition
A child is running up a staircase with n ...
-1
votes
0answers
37 views
Dynamic knapsack java implementation: with item list
I've run into trouble while programming a dynamic knapsack problem implementation. Aditionally to returning the maximum value of the knapsack of size W, i need to return the list of items used to fill ...
4
votes
2answers
133 views
Knapsack algorithm with proper ratio constraint and weight constraint
Problem:
You're a juice maker looking for the best suppliers for your business. The suppliers are selling concentrates that have 3 ingredients: X:Y:Z in different proportions. Your juice needs to have ...
0
votes
1answer
41 views
Find Maximal values that can be acquired from N
There are n number of Houses (1,2,3,...,n). A thief have to start from house 1 and reach house n to steal the maximum. He can steal the house and he can leave. If at all he stole in any house, the ...
0
votes
0answers
77 views
Maximum sum in a torus
I am trying to solve the following dynamic programming question on uva online judge:
A grid that wraps both horizontally and vertically is called a torus.
Given a torus where each cell contains ...
-5
votes
0answers
34 views
expected value when you play optimally in a game of chances [closed]
You have a box which has G green and B blue coins. You are playing a game: pick a random coin from the box. If the coin is green you get Rupee 1 and if it is blue you pay Rupee 1. At any moment (...
0
votes
1answer
40 views
Dynamic Programming for coin change
A given amount x should be changed in a coin system C = {c1, c2, … ck} such that each coin ci has a given weight wi. We would like to calculate the total weight of the possible changes. Two changes ...
1
vote
1answer
48 views
can i optimize this function even more
well , I'm looking for ways to optimize a function that i wrote as an answer to this problem in python:
"Given a square matrix of integers with each row containing the time it takes to get to the ...
1
vote
1answer
31 views
Dynamic Programming - “maximize” matrix chain multiplication
I'm now practice dynamic programming by myself. For the classic problem "matrix-chain multiplication" is to find the minimize number of scalar multiplication. Which is,
M[i,j] = 0 if i=j
= Min(...
0
votes
0answers
17 views
Python:Viterbi Algorithm for POS Tagging
I have created a transition matrix (A) and emission matrix (B). After this i am trying to write viterbi algorithm implementation in python to get the best path. But i am not finding any good ...
0
votes
0answers
37 views
n Partitions with fixed number of elements
I have given an Array of Integers and should partition it so the difference of the sums is minimal. The size of a partitions is fixed (3), so there are n/3 partitions. I should output all the ...
-2
votes
0answers
20 views
Scanner waits for Enter press before continuing with the code for no reason JAVA [duplicate]
I'm supposed to calculate the max amount of coins to be collected given that I can't collect coins from two "Monsters" right after each other, I must skip one to be able to collect coins.
I solved it ...
1
vote
2answers
46 views
Find No of divisor
I have 1 programming question asking to find count of numbers between (1 and x) that is divisible
by 2 and factor of 2 + 3 and factor of 3 + 5 and factor of 5.
I solved it and Algo is below-
...
0
votes
0answers
29 views
Getting the sequence instead of length of e maximum increasing subsequence
I am trying to figure out how to get the sub-sequences of
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
I managed to find examples on how to get the length of a longest increasing sub-...
0
votes
1answer
30 views
Match an abbrevations like “ccd” , “bbq”, “phd” etc to most similar string from a set of strings
I have a list of abbrevations like "ccd" , "bbq", "phd" etc.
For example let's take "bbq" , we try to map this abbrevation to a list of strings,
Barbeque Nation - The actual answer should be this
...
0
votes
0answers
34 views
Decode Morse (Dynamic Programming) without spaces, but with given possible words and return all solutions/sentences
I have a morse code with no spaces in between the letters, so base on a given list of possible words i must return la solutions/sentences.
msg = '-.---.-' message to decode
WORDS = ['K', 'TET', '...
0
votes
1answer
36 views
Solving SUPW from ZCO 2014
While practicing for the upcoming ZCO I cam across this problem , here is an excerpt from it,
In ICO School, all students have to participate regularly in SUPW.
There is a different SUPW activity ...
0
votes
0answers
22 views
TSP, DP Vs brute force, memorizing brute to making it dp
i'm trying to write a Dynamic Programming solution for TSP in python, i didnt have much problems with the brute recursive solution, so when i got it i said its done, i just memorize the results so i ...
1
vote
1answer
51 views
Splitting a string into words with dynamic programming
In this problem we've to split a string into meaningful words. We're given a dictionary to see If the word exists or not.
I"ve seen some other approaches here at How to split a string into words. Ex: ...
11
votes
6answers
441 views
Length of longest subarray of sum less than or equal to k
In an interview I was asked this question: given some array of positive integers s, find the length of the longest subarray such that the sum of all its values is less than or equal to some positive ...
0
votes
0answers
34 views
Dynamic Programming, Arithmetic Progression, Time complexity issues
Given an array of size n (1<=n<=200000) with each entry a[i] ( 1<=a[i]<=100), find all the number of subsequences that form Arithmetic progression.
Subsequences are the sequences where you ...
0
votes
1answer
45 views
Why Longest common string can not recursive first and output latter
Here i want to output the longest common string using dynamic programming algorithm ,code below is my implementation.what make me wired is the output A C A D C B, it's obviously wrong, and if i ...
-1
votes
0answers
16 views
SPOJ, Dynamic Programming - COURIER
I am stuck in the problem COURIER of SPOJ http://www.spoj.com/problems/COURIER/ . I have written the code http://ideone.com/KEEb4u and have run it for a lot of test cases. It is giving correct ...
-1
votes
2answers
63 views
Does this pattern reduce to a simple formula, possibly a recursive one?
I've brute-force written out up to N=4 and I'm wondering if it's possible to express this in a simple recursive formula.
f({A}) = 1 * (A)
= A
f({A,B}) = 2 * (A + B) + 1 * (A) + 1 * (B)
...
2
votes
1answer
51 views
Maximum sum of non adjacent elements in a 2D array
I'm trying to look for an algorithm that will help me find the maximum sum of non adjacent elements in a 2D array.
For 1D arrays, I've found helpful solutions from:
1) http://www.geeksforgeeks.org/...
0
votes
0answers
23 views
Matrix Chain Multiplication Recursion
I'm trying to implement MCM using recursion but my code always fail after the second diagonal.
As an example, this is the results of the test case of { 20, 15, 10, 30, 5, 25, 15 }
using ...
1
vote
0answers
59 views
Longest Convex Subsequence
Note, I already looked at this solution: Longest convex subsequence in an array
I've looked at the solution above but I fail to understand it. What I know is that the property for a convex ...
0
votes
0answers
7 views
Elementary shortest path with resource constraints for VRP using dynamic progrmming
I am trying to solve an Elementary shortest path problem with resource constraints for VRP using dynamic programming. But I couldn't find any good example of the implementation of the algorithm. Can ...
0
votes
0answers
28 views
How do i solve COWGIRL SPOJ vn?
how do i solve this COWGIRL SPOJ problem(http://vn.spoj.com/problems/COWGIRL/)
"Given m,n. Count the number of ways to make a matrix size MxN of 0s and 1s that satisfy: no any sub matrix of 2x2 that ...
1
vote
1answer
14 views
paint fence in Lintcode - python solution with Memory Limit Exceeded
I'm solving the paint fence problem in lintcode with Python. In the python code, I defined a list with only 4 elements and run the loop to update the last three elements according to the recurrence ...
