All Questions
Tagged with dynamic-programming python-3.x
39 questions
4
votes
1
answer
117
views
Calculate optimal game upgrades, v2
This is the second iteration of the code I originally posted here: Calculate optimal game upgrades. Based on the feedback there, I chose to change the code to use a dynamic programming approach with ...
- 83
2
votes
1
answer
50
views
Optimal Extraction of Longest Sorted Sequence from Individually Sorted Bucket Arrays Without Repetitions
Consider a bucket array containing sorted and/or empty buckets, and the goal is to extract the longest possible sequence in sorted order, under the following conditions:
Only one element in each ...
- 121
2
votes
2
answers
166
views
Making my DP algorithm faster - longest palindromic substring
The following code is my solution to a LeetCode question - find the longest palindromic substring. My code is 100% correct, it passed once but it took too long, and in most of the reruns I hit a "...
- 123
3
votes
1
answer
118
views
Segmentation of list to minimize the largest sum
I have written the following code for diving a list 'seq' into 'k' segments such that the maximum sum of each segment is minimized. I have used dynamic programming to solve this problem. But my class &...
2
votes
1
answer
127
views
Coin partitions
I am looking to obtain the partitions of coins that sum to a target amount
So I tried search online, but every single website loves to use this problem to show the benefits of dynamic programming. ...
- 5,735
1
vote
2
answers
141
views
3
votes
1
answer
848
views
Divide array into three disjoint sets with equal sum
Problem definition : Array partition problem
Given an array of positive integers, divide it into three disjoint subsets having equal sum. These disjoint sets cover the complete array.
Example
Input: [...
- 389
3
votes
1
answer
231
views
Killing a Hydra - Overengineered
Background
This question is inspired by the question: Killing a hydra, and my response therein. I will restate the problem at hand in full so that this question is fully self contained
You can only ...
- 5,735
3
votes
2
answers
362
views
Divide a set into subset with some constraints
Problem:
Given a list L consisting of not necessarily unique non-negative integers, find the minimum number of subset with maximum sum ...
- 191
3
votes
0
answers
694
views
Split money into every possible combination of coin denominations
Background and objective of the code
Based on this Dev.to challenge, I wrote the Python code below (TIO link also available).
The task was to return the least number of coins in a given denomination ...
- 528
2
votes
1
answer
93
views
Is there a route to the end of the jump table?
I'm currently learning about Dynamic Programming and solving a "coding question" related to the topic.
Given an array of non-negative integers, you are initially positioned
at the first ...
- 307
3
votes
1
answer
357
views
Find the smallest number of perfect squares that sum to a target
Given a positive integer n, find the smallest number of perfect squares (for example, 1, 4, 9, 16, ...) that sum to n.
...
- 307
7
votes
1
answer
1k
views
Printing the number of ways a message can be decoded
My below solution to the following problem is exceeding the maximum recursion depth. I am looking for any improvements which i can make.
Problem
Alice and Bob need to send secret messages to each ...
- 121
5
votes
1
answer
351
views
Total number of non overlapping subsets
I am trying to solve this question. The essence of the problem is this:
Given a list of school classes with start and end times, find the total number of non-overlapping subsets.
I've written up a ...
- 1,051
6
votes
3
answers
1k
views
Minimum path sum in a triangle (Project Euler 18 and 67) with Python
Project Euler 18
Project Euler 67
As problem 67 is harder, I'll go with that one:
By starting at the top of the triangle below and moving to adjacent
numbers on the row below, the maximum total ...
- 2,790