All Questions
Tagged with dynamic-programming python
819 questions
-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
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
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
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
3
votes
4
answers
153
views
How to efficiently solve the Maximum Product Subarray problem in Python?
I’m trying to solve the Maximum Product Subarray problem, which is described as follows:
Given an array of integers (positive, negative, or zero), find the maximum product of any contiguous subarray.
...
- 41
0
votes
1
answer
71
views
Why is this DFS + Memoization solution for selecting indices in two arrays too slow while a similar approach is more efficient?
I was solving LeetCode problem 3290. Maximum Multiplication Score:
You are given an integer array a of size 4 and another integer array b of size at least 4.
You need to choose 4 indices i0, i1, i2, ...
- 2,052
2
votes
1
answer
37
views
No solution found in GEKKO when modelling a tank level
I'm trying to simulate the level of a tank that has two inlet flows and one outlet. The idea is that after this will be used in a control problem. However, I can't get it to work with gekko but it did ...
- 45
1
vote
0
answers
119
views
How can I find the length of the longest common substring between two strings efficiently?
I have two strings, s1 and s2, and I need to find the length of the longest substring that appears in both strings. The substring must be contiguous in both s1 and s2.
For example:
If s1 = "...
1
vote
1
answer
215
views
Branch and bound problem, how to enumerate all of the possibilities?
Here is a problem that was in a past exam for Advanced algorithms in my studies,it's on 5 points over 3 hours so should take approximately 1H but I am struggling to find the solution for the first ...
0
votes
1
answer
105
views
Optimizing dynamic programming solution for Abbreviation problem- Hackerrank
So I personally favor coding dynamic programming solutions using a top-down approach. Especially in python because it lends itself to a rather easy recursive implementation using the cache decorator, ...
- 123
3
votes
1
answer
84
views
Counting the number of positive integers that are lexicographically smaller than a specific number
Say I have a number num and I want to count the number of positive integers in the range [1, n] which are lexicographically smaller than num and n is some arbitrary large integer. A number x is ...
- 225
5
votes
1
answer
414
views
Longest complete subsequence of ordered vowels [duplicate]
Given a string made up of "a", "e", "i", "o", or "u", find the longest subsequence of vowels in order. For example, is the string is "aeiaeiou&...
- 71
0
votes
0
answers
50
views
Detect Cyclic Islands on a Matrix
On a binary matrix M, a cyclic island is a region of 1s where the region encircles itself (horizontal, vertical and cross directions are allowed)
Given a matrix M,
Allowing neighbors to be in any of ...
- 93
0
votes
1
answer
59
views
Python Flask App Freezes with Large Data: Seeking Optimization Advice
I'm developing a Python Flask application to find combinations of numbers from dataset that sum up to a target value. The app works fine with smaller datasets but freezes when processing larger ...
- 1