Questions about problems that can be solved by combining recursively obtained solutions of subproblems.
0
votes
0answers
20 views
DP Recurrence Relation Finding [duplicate]
How do people find the DP Recurrence relation while solving contest problems (like in SPOJ, topcoder etc.)
I have read Cormen and many other algorithms book. But they just explain only one or two of ...
2
votes
1answer
71 views
How to master Dynamic Programming? [duplicate]
I am having hard times learning Dynamic Programming.
I looked around the web and found many tutorials with examples.
Each time I tried to figure out how to solve a new problem before looking at the ...
0
votes
1answer
28 views
Proving correctness of the algorithm for convex polygon minimum cost triangulation
I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be ...
3
votes
1answer
32 views
Select optimal subintervals from array
I have an input array and I have to select an indefinite number of intervals from it so that the "profit" is maximal and I have exactly T elements selected in total, where T is given. Profit means the ...
1
vote
1answer
42 views
Time Complexity Upper Bound of Memoized DP Problems
I find it fairly easy to generate an upper bound for nearly any iterative solution (e.g. look at the limits on each loop, etc.), and can oftentimes create an upper bound for normal recursive ...
0
votes
1answer
72 views
Confusion related to dynamic programming [closed]
I was going through this dynamic programming problem. However, I have a confusion
In the third picture, having the black border, I didn't get how the
For each, we try each string of the k ...
1
vote
2answers
160 views
Count unhappy numbers in a large interval
An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1.
For example, $23\rightarrow ...
1
vote
0answers
100 views
Activity Selection in Dynamic Programming
I'm trying to write pseudocode for the Activity Selection Problem in dynamic programming as opposed to Greedy Algorithm. The recurrence I have is:
...
-6
votes
1answer
160 views
Maximizing profit
Problem:
Given 11 numbers
{N1,N2,N3,N4,N5,N6,N7,N8,N9,N10,N11}
where
N1:amount of profit from product A
N2:amount of profit from Product B
N3:amount of ...
3
votes
3answers
160 views
Finding all solutions to subset sum for integers with bounded weights
Suppose I have the set of weights $W = \{w_1,w_2,\ldots,w_{50}\}$ where each $1 \le w_i \le 60$ is an integer. I am interested in determining all subsets (not just one, and not just the number of ...
0
votes
2answers
91 views
Broken stick problem
We have a broken stick. For every part, we know it's length. Our task is to connect all parts (glue them), that we will use as small amount of glue as possible.
The amount of glue need to connect ...
4
votes
1answer
162 views
Smallest string length to contain all types of beads
I read this question somewhere, and could not come up with an efficient answer.
A string of some length has beads fixed on it at some given arbitrary distances from each other. There are $k$ ...
4
votes
1answer
177 views
Find maximum distance between elements given constraints on some
I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements:
The element 1 is in position 1, and element N must be ...
3
votes
2answers
251 views
Modified paths Counting in a Rectangle
I was solving the following problem. But I am not able to think of an efficient algorithm for this modified version of problem. The problem statement is:
We are given K Rectangles. The dimensions ...
1
vote
1answer
111 views
String similarity problem
We are given two strings $x=x_1,x_2,x_3,\ldots,x_m$ and $y=y_1,y_2,y_3,\ldots,y_n$ over some finite alphabet.
We consider the problem of converting $x$ to $y$. Using the following operations:
...
