All Questions
Tagged with combinatorics dynamic-programming
7 questions
1
vote
1
answer
106
views
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 ...
- 59
8
votes
4
answers
2k
views
Project Euler #15: counting paths through a 20 × 20 grid
I've recently solved Project Euler's 15th problem stating:
Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom ...
- 83
3
votes
1
answer
1k
views
Counting subsets with sum not exceeding some limit
I am facing a variation of a subset sum problem. I have to count the number of subsets with sum less than or equal to some integer(limit). I think the optimal solution for this problem would be the ...
- 133
-3
votes
1
answer
3k
views
Counting the number of ways to break an amount into coins
I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations:
quarter: 25 cents
dime: 10 cents
nickel: 5 cents
pennies: 1 cent
There are an ...
- 471
1
vote
2
answers
294
views
SPOJ - Alphacode - Exceeds Time Limit
I'm trying to solve Alphacode on SPOJ. The challenge is to count the ways to split a string of up to 5000 digits into a sequence of numbers, each ranging from 1 to 26.
It works fine for small ...
- 179
12
votes
1
answer
441
views
Counting paths in an n-dimensional grid that stay within the boundaries
Problem Statement
You are situated in an N dimensional grid at position (x1, x2, …, xN).
The dimensions of the grid are (D1, D2, …, DN). In one step, you can
walk one step ahead or behind in any ...
- 231
4
votes
1
answer
240
views
NGON (many polygons) on SPOJ
I am trying to solve NGON problem. I am using bottom up dynamic programming here. Recurrence function is:
$$\begin{array}{rl}
f(a,b) &= f(a-1,b) + f(a-1,b-1)\,a_i +\frac{f(a-1,b-2)\,a_i(a_i-1)...
- 183