Questions tagged [dynamic-programming]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
14 views

Formulating a bottom-up dynamic programming premise for a board game

The game being played here has the following rules, played be a singular player: there is a 5x5 board, where some tiles are highlighted and some are not. From here, the player can highlight the blank ...
Some Guy's user avatar
1 vote
0 answers
33 views

Dynamic Programming: Counting *cycles* consisting of distinct numbers

I was thinking about this question and thought about it for quite a while but couldn't come up with an answer. Firstly, we fix two sets $R$ and $S$. We consider "cycles", which are tuples in ...
Gareth Ma's user avatar
  • 111
0 votes
1 answer
19 views

Distinguishing Between Two mixed integer Programming Problems: Is Concavity of the Price Function the Key Difference(besides the cost of backlogging)?

I've been examining two mixed integer programming problems presented in two different papers. I've noticed some similarities between them but I'm having trouble distinguishing the key differences. ...
Alex's user avatar
  • 1
0 votes
0 answers
24 views

Optimality in greedy task

There is a well-known problem of the best time to buy and sell stock. Assume now we have two arrays, SELL and BUY. Each time SELL[i] > BUY[i]. Assume we have initial budget B, and we can buy any ...
openspace's user avatar
  • 151
1 vote
2 answers
39 views

Zero sum game: dp recursion strategy

Trying to solve the zero-sum problem described here, where two opponent players at each turn can choose to collect 1, 2 or 3 stones with different values, with the objective of getting more points at ...
rickyviking's user avatar
0 votes
1 answer
44 views

How to cover elements with minimum amount of elements

I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem. I have elements from 1 to n and I am trying to cover all of the elements using the ...
Ally Zane's user avatar
0 votes
0 answers
30 views

House Robber Problem Variation with Risk/Cost to Rob Each House

I came across a modification of the classic house robber problem where there is a cost to robbing each house, and we want to maximize the amount robbed using the array (exactly as in the original ...
user197328534535's user avatar
1 vote
1 answer
27 views

Constrained precedence parsing

This is a simple variation on precedence parsing for which I haven't been able to prove the existence of an efficient algorithm. Is this a known problem? The setup is as follows: we are given $n$ ...
Mario Carneiro's user avatar
0 votes
0 answers
27 views

Algorithms for finding number of sequences with length N and displacements less than k

The sequences are made up of only digits. A displacement is defined as pair $(i, j)$ such that $i > j$ and $A[i] < A[j]$. For example, 423 has 2 displacements. The question is to find the number ...
Mahdi Khodabandeh's user avatar
0 votes
1 answer
55 views

Why does the non-adjacent sum problem have optimal substructure?

In my algorithms class, my professor presented the problem of finding the largest sum of non-adjacent elements in an array. For example, if we have $[1,4,3,8,5]$ the largest sum of non-adjacent ...
jem do's user avatar
  • 1
-2 votes
1 answer
57 views

Find Number of subsequences such that bitwise OR is same as sum

Suppose there is an array having at most 10 elements between 1 to 10^18. Suppose the array has elements B1,B2,.Bn. We can choose sequence A1,A2,A3,..An such that 0<=Ai<=Bi. Count How many ...
abcd's user avatar
  • 1
0 votes
0 answers
26 views

Upper bound of traveling salesman problem via dynamic programming

For a set of $n$ cities, the total time to compute OPT (see Fomin & Kratsch, Chapter 1) is given to be \begin{equation} \sum_{k=1}^{n-1} O\left(\left(\begin{...
Jung's user avatar
  • 101
0 votes
0 answers
26 views

Is there a sorting program or formula to sort and place individuals in classes based on preferences

I am looking for a formula or program to help place people in classes based on their preferences. The elements of the problem are: There are 30 class choices a student can pick from. There are 400 ...
Nick B. 's user avatar
1 vote
1 answer
87 views

Placing K gas stations among n cities to minimize distance

There are $n$ cities on a highway with coordinates $x_1$ , . . . , $x_n$ and we aim to build $K < n$ gas stations to cover these cities. Each gas station has to be built in one of the cities, and ...
Muffinlicious's user avatar
2 votes
1 answer
34 views

Checking forbidden moves in Renju

I am trying to detect forbidden moves for black in a game called Renju. First, here is an explanation of how Renju works. Renju is a board game played on a 15x15 Go board. There are two players in the ...
Kyaw Shin Thant's user avatar
2 votes
0 answers
59 views

Recurrence Relation for Longest Increasing Subsequence Problem

I am trying to solve the Longest Increasing Subsequence(LIS) Problem using different OPT Function than the one which normally used. I have been given this question as an extra credit and I have been ...
Sabe's user avatar
  • 21
2 votes
2 answers
399 views

Select a subset of k intervals which form maximum length if we take union of these k intervals

Suppose we have $n$ intervals given in the form of (startTime,EndTime). I wish to calculate maximum length of the region that is exactly union of $1<=k<=n$ intervals. Note that there are 2 cases ...
Kitwradr's user avatar
  • 123
1 vote
2 answers
75 views

How do I find the most even combination for two arrays

I have two arrays that both contain n elements (positive,non zero, not negative) {x1....xn} {y1....yn} I want to pair them up optimally, one from each array, so that the pairs come out as even as ...
Ally Zane's user avatar
0 votes
1 answer
55 views

Compute the maximum length of an increasing digital subsequence given an array of digits

Consider the following exercise from chapter Dynamic Programming in the book Algorithms by Jeff Erickson. Let $D[1 .. n]$ be an array of digits, each an integer between $0$ and $9$. A digital ...
Mohammad.Rostami's user avatar
1 vote
0 answers
129 views

Tabular Meta-Learning in RL

There are various meta-learning algorithms in RL that are proposed for settings when we have a (deep) neural network and the policy (or the value function) are parameterized as such. Can these methods ...
Perissiane's user avatar
0 votes
1 answer
47 views

Confused on Bellman Ford

We have a graph where we want to get from node u to v in the shortest path possible. I understand how Bellman-Ford works when we have exactly i edges to go from u to v or at most i edges to get from u ...
smarty_pants's user avatar
1 vote
1 answer
77 views

Another Game Theory Problem

We have an array of integers of length N(even). A and B play a game where A selects a number followed by B without replacement until the array becomes empty(Both A and B select N/2 elements each). The ...
Identicon's user avatar
0 votes
0 answers
36 views

Is there always a Dynamic Programming Solution underlying a greedy solution to any algorithmic problem?

According to CLRS book, Introduction to Algorithms, Nevertheless, beneath every greedy algorithm, there is almost always a more cumbersome dynamic-programming solution As the word "almost" ...
Divyanshu Dwivedi's user avatar
1 vote
0 answers
61 views

Find maximum number of vertex-disjoint paths of length $k$ in a tree with no restrictions for the paths

I am working currently on Path-Packing problems and found this Book: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf My question is about exercise 23b on page 184. Here is ...
Mark Hase's user avatar
0 votes
0 answers
16 views

Changing the order of assignment in a state machine algorithm for Best Time to Buy and Sell Stock problem

Here's a smaple solution to Best Time to Buy and Sell Stock III problem: ...
Sgg8's user avatar
  • 101
2 votes
1 answer
60 views

Is this varient of longest increasing nested sets problem NP-hard?

There are two types of sets $\mathcal{X} = \{X_{1}, X_{2}, \ldots, X_{n_{1}} \}$ and $\mathcal{Y} = \{Y_{1}, Y_{2}, \ldots, Y_{n_{2}}\}$ such that $X_i, Y_j \subseteq [m]=[\mathrm{poly}(n)]$ and $n = ...
Blanco's user avatar
  • 613
-1 votes
2 answers
365 views

Longest increasing subsequence when a number can be added to all numbers in a subarray

A sequence $(a_1,a_2, \dots, a_n) $ and natural numbers $n$ and $k$ are given. We want to calculate the longest (strictly) increasing subsequence of sequence $(b_1,b_2, \dots, b_n)$ for which there ...
Hjm's user avatar
  • 37
0 votes
1 answer
133 views

What is the best way to solve the coin change problem using dynamic programming?

I have found two ways of applying dynamic programming to the coin change problem of finding the minimum number of coins from a given set of denominations to make a given sum. I wanted to know if one ...
JeanMi's user avatar
  • 111
0 votes
1 answer
48 views

Given a list of pairs (cost,points) and a number k, find the maximum sum of points with sum of costs less than or equal to k

Given a list of $n$ pairs (cost,points) and number $k$ ($0 \le k$), find the maximum possible sum of points s.t their sum of costs no more than $k$. return the maximum possible sum of points and their ...
NirF's user avatar
  • 228
1 vote
1 answer
94 views

Finding minimal moves to move boxes into m floors

Assume a tower with $n$ floors. Each floor contains $C_i$ boxes such that $C_i>0$ for all $1\le i\le n $ Moving $C_i$ boxes from floor $i$ to floor $j$ where $i>j$ costs $C_i\cdot(i-j)$ and we ...
Danny Blozrov's user avatar
1 vote
0 answers
17 views

Optimal expression ordering with short-circuit evaluation [duplicate]

Let $E_1, E_2, \ldots, E_n$ be boolean-valued expressions, each with an associated evaluation cost and probability of returning true. For simplicity, assume these ...
Tavian Barnes's user avatar
0 votes
0 answers
49 views

Finding the diameter of a N-ary tree graph, without using BFS

As the title hints, I'm looking for a dynamic programming/greedy approach to find the diameter of a N-ary tree graph. This must be done in linear time. The problem states that the graph is undirected ...
Aishgadol's user avatar
  • 316
-3 votes
1 answer
41 views

Given a list of numbers L and a target k, is there a subset of numbers from L whose product is k?

Is there any dynamic way of solving this problem? I would thank any help, I know the Subset sum Problem, but for solving it dynamically u have to create a matrix but here is not posible as the colums ...
SEBASTIAN ROJAS BUENO's user avatar
1 vote
1 answer
559 views

Minimal number of positive intervals to cover all positive elements

I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray&...
Aishgadol's user avatar
  • 316
1 vote
1 answer
106 views

Single machine scheduling with profit and deadline constraints

The problem is described as such: Given $n$ tasks $\{J_1, \ldots , J_n\}$where each task has a deadline and a ‘profit’. So for some $i \in \{1,\ldots , n\}$, $J_i=\{t_i,p_i\}$ where $t_i$ is the ...
Aishgadol's user avatar
  • 316
1 vote
1 answer
36 views

Heterogenous Resource Allocation Using Dynamic Programming

I'm working on a resource allocation problem, where there are $n$ different Items and $m$ different tasks ($n\geq m$). Also, The profit of assigning subset $I=\,(\, |I|\leq n)$ of items to task $j$ is ...
pronerd7's user avatar
0 votes
0 answers
32 views

How to compute a closed form solution of Hamilton-Jacobi-Bellman equation?

The following paper provides a HJB equation and its closed form solution for a special case. https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/3943/vanryzin_optimal_dynamic_pricing.pdf ...
nemy's user avatar
  • 113
0 votes
2 answers
115 views

Time complexity of finding the minimum by dynamic programing

How can I calculate the complexity of computing $MD(b)$, where $b=(b_1,b_2,\dots,b_n)$? $$MD(s) = \max(s)-\min(s) + \min(MD(s\setminus\{\max(s)\}), MD(s\setminus\{\min(s)\}))$$ where $s$ is a finite ...
Hjm's user avatar
  • 37
0 votes
1 answer
43 views

Maximal Profit of 'legal' cutting of a board

I'm facing this problem for some time now, I've tried a greedy approach yet I result to trying a DP-ish approach, only to get stuck at a standstill. Given a board of length $n$, and an increasing ...
Aishgadol's user avatar
  • 316
-1 votes
1 answer
49 views

how to find the most optimal path for this problem?

There are N islands and there is one pirate. The pirate can start out from any one of the n islands and has the option of either staying on the same island for the next day or moving to a different ...
mewowo's user avatar
  • 1
0 votes
1 answer
41 views

maximum length of the sequence (a[i],b[i]) such that if $b[i]='<'$ then $a[i+1]<a[i]$ and if $b[i]='>'$ then $a[i+1]>a[i]$

Let $N$ be a number and consider the sequence of $a[i]$, $b[i]$ with $i=1,n$ where $a[i]$ are positive integers and $b[i]$ is the sign '$<$' or '$>$'. Find the maximum length of the subsequence(...
shangq_tou's user avatar
-3 votes
1 answer
95 views

how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000

how to count all pairs such that w^x=y^z, where 1<=w,x,y,x<=n and 1<=n<=1000000 for example for n=3, there is 15 solutions 1^1=1^1 1^1=1^2 1^1=1^3 1^2=1^1 1^2=1^2 1^2=1^3 1^3=1^1 1^3=1^2 1^...
Abcd Dcba's user avatar
1 vote
1 answer
105 views

Is there an efficient way to solve this problem?

Given a series of n numbers, I need an algorithm that runs in worst case O(n*k) to figure out how many arrangements of those n numbers will give me a score of exactly k. Note that the series does not ...
brownturtle's user avatar
0 votes
3 answers
133 views

is there an O(n^2) approach to this problem?

Given an array of N elements, I need to split it into k subarrays, where k can be between 2 <= k <= N. A sub-array's score is determined by: (left boundary point - right boundary point of the ...
stillmute's user avatar
1 vote
1 answer
89 views

What is the proper way to approach a competitive coding problem?

***Climbing Stairs Problem: https://leetcode.com/problems/climbing-stairs/ 1) Take the "***Climbing Stairs" Problem for instance: If I was given a problem like this on a test after mastering ...
Sai Surisetti's user avatar
0 votes
0 answers
30 views

Maximum Accumulated Balance after Purchasing Machines

A company is able to earn x dollars per day without any machines. However, there are n machines available for purchase. The <...
XYZ's user avatar
  • 11
0 votes
0 answers
76 views

Prove that the total number of parenthesizations of n matrices is Ω(4^n/n^3/2)

Is it possible to prove the total number of parenthesizations of n matrices is Ω(4^n/n^3/2) using the Induction Method? Recurrence formula from CLRS book When n = 1, the sequence consists of just one ...
learner_b's user avatar
0 votes
0 answers
225 views

Binary Matrix covered with squares to cover all 1's in min cost

So I recently came across a question in my Algorithms class. Given a binary matrix of N X N. we can do following operation any number of times we can take a square of size M X M (1 <= M <= N) ...
Kira Yoshikage's user avatar
5 votes
2 answers
2k views

Why does the order of the nested loops matter when solving the Coin Change problem?

The Coin Change problem is stated as: Given an integer array coins[ ] of size N representing different denominations of currency and an integer sum, find the number of ways you can make sum by using ...
Elad Maimoni's user avatar
0 votes
1 answer
20 views

Algorithm to optimise the cost to choose a subset of array

I have been on this problem for very long time, Lets assume we have a shopping list eg:{milk,bread,coke,orange,apple,..} and the shop only sells pack of thing and ...
Prithvi Raj's user avatar

1
2 3 4 5
19