5,721 questions
-1
votes
1
answer
34
views
What is correct path tracking in Floyd-Warshall algorithm?
There are several descriptions of the Floyd-Warshall algorithm, including the one in Wikipedia where path tracking logic described like in the pseudo-code below (copy from Wikipedia https://en....
- 73
-1
votes
0
answers
86
views
Is this DP function correct for the given prompt?
S(n) = 1 if n = 1
2 if n = 2
S(n - 1) + S(n - 2) if n is even
2S(n - 1) - S(n - 2) if n is odd and n > 2
SOLUTION:
def layup_s(n):
# given base cases
if n == 1:
...
- 1
0
votes
0
answers
24
views
Why does int in my DP array cause overflow in Coin Change II problem?
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<unsigned int > dp(amount+1, 0);
dp[0]=1;
for (int value: coins){
...
- 13
2
votes
2
answers
65
views
Getting all distinct subsets from subset sum problem with target T using Dynamic Programming
In the classic subset sum problem, there are a set S and a target t, and the goal is to find a subset of S whose sum is t. This variant has a pseudo-polynomial time solution.
In a variant of the ...
- 189
4
votes
1
answer
76
views
Struggling with bottom up approach for This Kattis Problem: The mailbox manufacturers
Problem link : https://open.kattis.com/problems/mailbox
It feels like a variation of Egg dropping problem but i cant seem to wrap my head around how I am unable to do this. It is also tagged as an ...
- 57
0
votes
0
answers
35
views
how to return dynamic columns with multiple records with out passing a columns to functions returning "record" in PostgreSQL [duplicate]
I have a table like below
create table public.test_dynamic_data_tbl(col1 int,col2 character varying,col3 double precision);
insert into public.test_dynamic_data_tbl values(1,'test1',12)
insert into ...
- 1
0
votes
0
answers
38
views
Valid Parenthesis String, Recursion with memoization to DP
How can the following recursion + memoization code be converted into a tabulation format dynamic programming solution?
The code is working but I want to improve it.
The challenge I am facing is ...
1
vote
2
answers
77
views
Why does my A* algorithm expand nodes differently when using heapq vs. a set for the open set?
I'm implementing an A* search algorithm for a maze solver in Python. Initially, I maintained the open set as a plain set and selected the node with the lowest f-score using:
current = min(open_set, ...
- 21
2
votes
2
answers
80
views
Match indexes from 1 to n with n given arrays so that sum of elements is minimal
Originally I faced a problem: I had three arrays of the same length (say, a, b, c), and I needed to choose indexes i, j, k distinct from each other that the sum a_i + b_j + c_k would be minimal. I ...
- 63
1
vote
2
answers
69
views
Number of ways to reach A to B by climbing one step, two steps or three steps at a time
I was solving a test on an online platform and the problem statement was similar to this.
Stuart has to go from one place to other (A-> B) and he can jump either 1 step, 2 step or 3 steps at a time....
- 5,275
-1
votes
3
answers
133
views
Coin change - A test case is failing
The problem goes like this:
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of ...
- 5,275
2
votes
1
answer
134
views
Maximum the sum of lengths of two nondecreasing subsequence of given array
It is a famous question which asked about finding longest nondecreasing subsequence from a given array. The question is well studied and have O(n log n) time complexity solutions.
I have encountered a ...
- 4,768
3
votes
2
answers
112
views
How to optimize the performance of nested loops with dynamic data structure updates in Python?
How can I optimize this code for better performance while maintaining the correctness of dynamic updates?
Is there a way to restructure the nested loop or use a different approach to reduce the time ...
2
votes
4
answers
219
views
How to align two string's offset given a list of substrings offsets?
Given a and b relating to a list of substrings in c:
a = "how are you ?"
b = "wie gehst's es dir?"
c = [
("how", "wie"),
("are", "gehst's&...
- 123k
0
votes
1
answer
76
views
solution to factorial problem using dynamic programming resulting in more time than simple recursion
I was just starting out with dynamic programming and tried solving factorial problem using the same, i used binary tree for underlying data structure, but when i thought of comparing it with normal ...
