Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [dynamic-programming]

Questions about problems that can be solved by combining recursively obtained solutions of subproblems.

1
vote
1answer
30 views

How to minimize the average distance between pumps and cities?

There are n cities [1, 2, 3, .... n] and k available pumps. These pumps can be installed in k...
0
votes
1answer
20 views

DP recurrence relations: Coin change vs Knapsack

Take: KP recurrence relation $ max { [v + f(k-1,g-w ), f(k-1,g)] } $ if w <= g and k>0 CCP recurrence relation $ min {[1 + f(r,c-v), f(r-1,c)]} $ if v <= c and r>0 I don't ...
0
votes
0answers
44 views

Intuition behind Floyd-Warshall being faster

I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm: Let $dp[i][j][n]$ denote the shortest path from $...
0
votes
0answers
26 views

Dynamic Programming : Recovering Optimal Solution: Refer Tardos

"So far we have simply computed the value of an optimal solution; presumably we want a full optimal set of intervals as well. It would be easy to extend M-Compute-Opt so as to keep track of an optimal ...
0
votes
0answers
46 views

What will be an O(n) solution for this?

Suppose a given piece of work can be done at two processors. One at r and another at v. The job can run only at one processor at ...
2
votes
3answers
46 views

Algorithm to find smallest number divisible by N with sum of digits as N

Problem: Given $N$, find the smallest number divisible by $N$ whose sum of digits is equal $N$. For example: $n = 1$, answer is $1$ $n = 10$, answer is $190$ There is some dynamic programming ...
0
votes
1answer
45 views

Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

For my study I am supposed to develop an dynamic programming algorithm which solves the following simplification of the Knapsack problem in $O(v^*n^2)$ time ($v^*$ is the maximum value of all elements)...
0
votes
0answers
19 views

Find largest subset of compatible indices using $O(n^2)$ DP algorithm

Past year paper question We are given a set $S$ of $n$ pairs of real numbers $S = \{(a_1,b_1),...,(a_n,b_n) \}$ such that $a_1 \leq a_2 \leq ... \leq a_n$. We say that a pair of indices $(i,j)$ is ...
0
votes
0answers
14 views

counting subsequence with distinct elements in the group

how to solve it using dynamic programming? suppose if i have an array and containing elements between 0 and 5 and elements are repeated more than once i want to find the no of subsequences with ...
0
votes
1answer
38 views

Sum of zero nim sum series

The problem is proposed here and related to this question. Given $n$ and $k$, I would like to know how to compute$$\sum_{\substack{x_0 ⊕x_1⊕\cdots⊕x_k=0\\x_i≥0,\ 0≤i≤k\\\sum\limits_{i=0}^kx_i≤n-2k}}\...
0
votes
0answers
13 views

What are “self-adjusting computation” and “dynamic programming”, and how are they different?

According to this website: Self-adjusting computation refers to a model of computing where computations can automatically respond to changes in their data The papers linked on this page make ...
1
vote
0answers
29 views

Possible Distribution of coins

We are given a set of $n$ coins with denominations $v_1,v_2,\ldots,v_n$ and a number $x$. The coins are to be divided between to persons, with the restriction that each person's coins must add up to ...
2
votes
0answers
58 views

Balls in Bins with Pairwise Distance

Given $n$ bins in a row (numbering from $1$ to $n$) and $2k$ balls ($n \ge 2k$), one may put all balls into bins with each bin having at most one ball (there are $\binom{n}{2k}$ configurations). ...
1
vote
1answer
43 views

Algorithm Design for Linear Programming

I am trying to complete question and would like to avoid copying answers, but I do not necessarily understand what I am doing. I am working on the following problem: Suppose you are consulting ...
0
votes
0answers
22 views

Can any recursion implementation be written into a bottom-up DP implementation?

Can any top-down recursion implementation be written into a bottom-up DP implementation?
1
vote
1answer
49 views

Gerrymandering Problem: Variant on Set Partitioning

I was recently helping a friend with homework from a dynamic programming class, and this was the question: Given a set of n precincts P1 ,... Pn , each containing m votes, with <...
2
votes
0answers
20 views

Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
0
votes
0answers
18 views

Given graph with N nodes colored in K colors, count paths visiting each color exactly once

Let's say we have given graph of at most $N = 400$ nodes, and each node is colored in one of $K = 21$ colors. We need to count paths of length $K$, such that each node on the path is in one of the $K$ ...
2
votes
1answer
44 views

Making a profit as a high-dimensional store owner?

Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient. Let's say that I am some business owner with a set of $...
1
vote
3answers
87 views

Dynamic Programming vs Memoization

I am having trouble to understand dynamic programming. Mainly because of its name. As far as I understand, it's just another name of memoization or any tricks utilizing memoization. Am I ...
0
votes
1answer
102 views

Help writing a dynamic programming algorithm in English

It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party....
0
votes
1answer
17 views

Grid Based DP: How do we tweak the Travelling Salesman Problem to work with Grids

The question is: There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path exists, 1 means the cell is blocked and 2 means there exists gold in that cell. Task is to start from 0,...
1
vote
1answer
28 views

How to find the number of Binary Search Trees with given number of nodes and leaves?

With 7 nodes of distinct values (unique), how many Binary search trees (BST) can be formed such that: Exactly $1$ leaf node(s) present? Exactly $2$ leaf nodes present? I was able to solve the first ...
2
votes
1answer
33 views

longest sub-sequence in both directions

Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A. Example: A = cabca the sub-sequence S = abc is the ...
2
votes
2answers
51 views

How can I reduce the time of this program

I solved a problem similar to the knapsack problem. There are two packages with a capacity of $P$ on a production line. We want to put $N$ items in them with the weights $w_1,...w_n$ in a pre-defined ...
0
votes
0answers
61 views

The number of balanced trees with N node and L leaves

An algorithm is requested to calculate all balanced binary trees which can be built with $N$ nodes, having exactly $L$ leaves. A balanced tree is a binary tree in which the difference between the ...
-1
votes
2answers
139 views

How can I write this backtracking algorithm using dynamic programming?

Problem: There are $n$ points on a map, $p_1,..p_n$. There are two officers located initially at $(0,0)$ coordinate. They want to patrol all of these points with a minimum traveling (each officer ...
0
votes
0answers
45 views

How we can minimize number of boxes for packing objects

Imagine we have n objects with different weights. We know the order in which objects come into the packing machine. Packing machine have two boxes, their capacity are equal and constant. When an ...
1
vote
0answers
30 views

Given a binary tree of leaves with weights, find minimum weights for internal nodes (such that sum(weighti-weightj) is minimized for (i,j)∈E(T))

So this is a question within a bigger question for which I've reduced to this so far: If I have a tree (phylogenetic) with known weights for leaves, how would I find the weights for all internal ...
2
votes
0answers
28 views

Weighted Sorting Algorithm

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation. Is there any ...
1
vote
1answer
36 views

Can the compiler convert recursive algorithm into a dynamic programming

So I was going through the idea behind dynamic programming (memoization), and thought of this question. Can a compiler convert any recursion into a table filling DP solution, of course given the ...
0
votes
1answer
28 views

Optimizing the problem

I have a recurrence relation: f(a,b) = f(a-1,b)+f(a-2,b-1)+f(a-1,b-1) with conditions: f(0,0)=1, f(a,0)=1, f(0,a)=0, f(x,1)=2*x where the constraints: 1<=a<...
0
votes
0answers
17 views

Reach the nth stair using step a-b while some stairs are broken

Description A person is standing below at a staircase having $N$ steps. Considering he can take a leap of between $a\geq1$ and $b\leq N$ steps at a time. In the meanwhile, some of the stairs are ...
0
votes
1answer
19 views

Finding recurrence relations for dynamic programming algorithms

Consider a function $f(n)$ whose definition requires one to compute $f(1),f(2),..f(n-1)$ in order to evaluate $f(n)$. Suppose that some algorithm to compute $f(n)$ has time complexity that is given by ...
1
vote
2answers
44 views

FInding the combination with the least number of elements from and array of integers, given an integer sum

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
1answer
57 views

Minimum Number of Integers From a List that Add up to N (Dynamic Programming)

A problem I'm working on requires me to find the minimum # of integers from a given list that add up to $N$, or more specifically: Given a list $L$ of $K$ integers, $[a_1, a_2, ... , a_k$], where ...
0
votes
1answer
21 views

Maximum trailing zeros of the path

Problems: A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, ...
1
vote
1answer
94 views

How does the problem of “Scheduling to Minimize Lateness” exhibit optimal substructure?

The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos): Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ ...
2
votes
1answer
22 views

Graph Traversal Solutions for “Find all unique paths” Problem

I was studying the grid problem where a robot is at the top left position and wants to go to the bottom right position and you need to return the number of unique paths it can take to get there with ...
1
vote
1answer
45 views

Optimal substructure and dynamic programming for a variant of the rod cutting problem

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following. Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the ...
2
votes
1answer
35 views

No. of subsets whose element multiply to give a square number

I have been given an array whose elements lie between [1,70] and the size of array [1,10^5]. I have to find the total number of subsets whose all elements multiply to give a perfect square number. ...
2
votes
1answer
26 views

Count number of the ways to fill a N-lengthed binary string

From the problem, count the number of ways to fill a binary string of length $N$ with at least one $1$'s consecutive sequence of length $K$ and other $1$'s consecutive sequences have length no more ...
2
votes
1answer
130 views

Maximum Equal Sum K Subsequences

Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum. Example: ...
1
vote
1answer
22 views

How to implement recursive solution with large number or parameterized possible next steps

I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom ...
3
votes
1answer
82 views

Request for examples to show various types of subproblems in dynamic programming

Chapter 6 of "Algorithms" by Dasgupta, Papadimitriou, and Vazirani summarizes four types of subproblems that are quite common in dynamic programming. They are prefix/postfix of a string/sequence/...
1
vote
1answer
22 views

Recursive DP vs Graph Traversal solutions to path-based problems

I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can ...
2
votes
2answers
295 views

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T. This question is a simplification of ...
1
vote
0answers
70 views

Parenthesizing a product using dynamic programming

Here is a problem that I've been given to solve in time $O(n^2|\Sigma|)$. Given an alphabet $\Sigma$ and the product of every two elements in this alphabet (i.e., an arbitrary mapping $\cdot\colon ...
0
votes
2answers
49 views

Understanding algorithm for maximum sum of non-consecutive elements

There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it: https://stackoverflow.com/questions/4487438/...
3
votes
0answers
46 views

Sequence matching

Let $T$ and $P$ be respectively two sequences $t_1, · · · , t_n$ and $p_1, · · · , p_k$ of characters such that $k ≤ n$. The characters range over a finite alphabet Σ. With each position of $T$, we ...