All Questions
Tagged with dynamic-programming c
18 questions
11
votes
3
answers
3k
views
Coin Change: Minimum number of coins
Problem:
You are given n types of coin denominations of values \$v(1) < v(2) < ... < v(n)\$ (all integers). Assume \$v(1) = 1\$, so you can always make change for any amount of money \$C\$. ...
- 449
8
votes
2
answers
2k
views
Counting Increasing Subsequences of size K recursive
The original description of the problem can be found here, its input here and its expected output here.
The problem:
Given a integer sequence a1 ... an (-10000
\$\leq\$ ai \$\leq\$ 10000). Where ...
user70000
8
votes
3
answers
305
views
Splitting a rectangular chocolate bar
I'm having trouble with my school homework. I have a chocolate bar that consists of either black, white or black&white (mixed) squares. I'm supposed to divide it in two groups, one that has only ...
- 81
8
votes
2
answers
264
views
Minimum number of coins problem using dynamic programming - follow up
I previously posted a code here. It turns out that the code is not following the correct dynamic programming principles and instead it was based on a greedy approach. Hence, I started again, keeping ...
- 449
8
votes
1
answer
169
views
Reading, processing and counting an array setting limits
Last weekend my teacher asked me to create code to solve a problem:
Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array length. ...
- 349
6
votes
1
answer
121
views
Optimal way to annihilate a list by removing items from the ends
I'm stuck with a contest problem.
Description:
What is the minimum number of moves to annihilate an int array where the possible moves are:
Remove both the first and last elements if they are equal ...
- 63
5
votes
3
answers
312
views
Largest contiguous sub-array sum
Challenge
Determine the largest contiguous sum of integers in a list.
Specifications
The first argument is a path to a file.
The file contains multiple lines.
Each line is a test case represented by ...
- 9,839
4
votes
2
answers
5k
views
Project Euler #15 -- count possible lattice paths
I'm not a C programmer, just wanted to make a fast solution to the problem.
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 ...
- 626
4
votes
1
answer
238
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
4
votes
1
answer
590
views
Google CodeJam Round D APAC Test
Problem A:
Vincenzo decides to make cube IV but only has the budget to make a square maze. Its a perfect maze, every room is in the form of a square and there are 4 doors (1 on each side of the room)...
- 201
3
votes
3
answers
2k
views
Tower Hopper problem recursive approach
The Tower Hopper problem gives us an array of values representing heights that express how far we can jump from a certain tower, and asks whether there's a way to get from ...
- 1,159
3
votes
2
answers
160
views
Count the number of ways to obtain a sum, with consecutivity restriction
A cricketer can score 1, 2, 4 or 6 in a ball. Find in how many ways the player can score a total of "n" runs without hitting 3 consecutive boundaries. Note: Scoring 4 or 6 is considered as a boundary. ...
- 31
3
votes
2
answers
5k
views
Longest collatz sequence using dynamic programming
I am trying to solve longest collatz sequence problem under 1000000 with the below code. Can anyone suggest a faster way to approach this problem? I was thinking of dynamic programming, but I'm ...
leo
2
votes
5
answers
299
views
Sum of bitwise XOR of each subarray weighted by length
here is the problem statement
You are given an array a of length n consisting of non-negative integers.
You have to calculate the value of \$\sum_{l=1}^n \sum_{r=l}^n f(l,r)\cdot (r - l + 1)\$ where \...
2
votes
0
answers
140
views
Bellman-Ford algorithm implementation
I have used an adjacency list to represent the graph.
This implementation is based on the procedure given in the book 'Introduction to Algorithms'.
...
- 321