All Questions
12 questions
3
votes
2
answers
144
views
A more efficient algorithm in finding the number of distinct decompositions a number has using only repdigits
This is a problem from a previous semester that I am trying to upsolve. I am trying to solve a problem involving the total number of ways of decomposing a number using only repdigits. A repdigit is a ...
- 51
1
vote
1
answer
258
views
fusing inner lists within list function to return highest possible integer dynamic programming
new to programming and currently trying to challenge myself and learn dynamic programming. I have this question to implement a function that takes an array and outputs the 'highest cuteness' of the ...
- 11
-1
votes
1
answer
91
views
Why does timeit results in almost constant time for all memoization runs?
We compute the Fibonacci number:
def fibo_memo(i, memo={}):
if i <= 0:
return 0
elif i == 1:
return 1
elif i in memo:
return memo[i]
else:
memo[i] = ...
- 3,631
1
vote
2
answers
145
views
How can I improve its runtime
Problem Statement: 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 coins that ...
- 478
1
vote
2
answers
282
views
How do I speed up this code? longest palindrome substring problem
I am working on the Leetcode problem to find the longest palindrome substring of a string. Here is my code.
def longest_palindrome_substring(string):
array = [i for i in string]
# ...
- 119
3
votes
4
answers
752
views
Number of even XOR-ed subarrays
Find the number of subarrays with even XOR (XOR of subarray means XOR of its elements).
For eg:
l=[1,2,3,4] # ----> Answer of this is 4
(Explanation: [2],[4],[1,2,3],[1,2,3,4]---> These are ...
- 121
0
votes
2
answers
315
views
Python __getitem__ performance between lists and dicts
I've implemented a dynamic programming algorithm (bottom-up).
As a quick fix I've used dictionaries instead of fixed sized arrays for the DP table, but given my input size (n up to 50k, m up to 100), ...
- 577
0
votes
0
answers
258
views
How can I efficiently merge two sets of ordered pairs, excluding pairs that are lower on both values from any other pair?
As part of a dynamical programming assignment, I find myself having to do the following.
I have two sorted lists of length 2 tuples (ordered pairs, representing scores on two criteria). One pair of ...
-1
votes
1
answer
431
views
Number of valid sequences
A sequence of n numbers is considered valid if the sequence begins with 1, ends with a given number j, and no two adjacent numbers are the same. Sequences may use any integers between 1 and a given ...
- 39
2
votes
2
answers
197
views
A performance discussion on DP
Look at the codes below, I use two ways to solve the problem (simple recursive and DP). Why is the DP way slower?
What's your suggestion?
#!/usr/local/bin/python2.7
# encoding: utf-8
Problem: There ...
- 138
3
votes
1
answer
506
views
How to speed up Python string matching code
I have this code which computes the Longest Common Subsequence between random strings to see how accurately one can reconstruct an unknown region of the input. To get good statistics I need to iterate ...
user2171391
44
votes
4
answers
11k
views
FSharp runs my algorithm slower than Python
Years ago, I solved a problem via dynamic programming:
https://www.thanassis.space/fillupDVD.html
The solution was coded in Python.
As part of expanding my horizons, I recently started learning ...
- 11.3k