All Questions
Tagged with dynamic-programmingrecursion
34 questions
10votes
2answers
300views
Undo format when format disappears
I was posed a question as follows: Given a sentence like "John is a bad man", lets say all the formatting disappears and you are left with one string "johnisabadman". Given a dictionary of words, ...
- 1,213
10votes
1answer
4kviews
Project Euler #14 -- longest Collatz sequence
I was reading this question and realized that I didn't know Python well enough to critique the algorithm. So I wrote a Java solution instead, which is inappropriate for that question. Since there's ...
- 6,984
8votes
2answers
2kviews
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
7votes
2answers
713views
Recursive function and memorization to find minimum operations to transform n to 1
I'm a new, self-taught programmer working on the Google FooBar challenge. I've submitted my answer (code at bottom) and it was accepted, but I'd like suggestions on how to improve my solution. ...
- 125
7votes
1answer
1kviews
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
6votes
1answer
3kviews
Longest common subsequence length and backtracking the string
Problem: Given two sequences, print the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “...
- 205
5votes
3answers
962views
LeetCode 678: Valid Parenthesis String, Recursion memoization to DP
How can the following recursion + memoization code be converted into a tabulation format dynamic programming solution? The code is working, but I want to improve it. The challenge I am facing is ...
4votes
2answers
131views
Find largest sum not involving consecutive values
There is a question to basically find the largest sum in an array, such that no two elements are chosen adjacent to each other. The concept is to recursively calculate the sum, while considering and ...
3votes
3answers
2kviews
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
3votes
2answers
921views
Memoized solution to Count number of ways to climb n steps
Problem statement : A Child is climbing up n steps with either 1 , 2, 3 hops ..how many ways can the child climb up the stairs? source: cracking the coding interview book. I have two solutions the ...
3votes
1answer
231views
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,745
3votes
1answer
386views
Number of unique sequences of 3 digits, given a length is equal to sum
This is the "Minion's bored game" problem from Google's "Foobar challenge": There you have it. Yet another pointless "bored" game created by the bored minions of Professor Boolean. The game is ...
3votes
1answer
319views
Efficiently calculate value of Pascal's Triangle using memoization and recursion
So reading about functional programming, applications to dynamic programming, and learning Scala. I figured I would try it out with a popular example, Pascal's Triangle, tests against known values ...
- 133
3votes
2answers
1kviews
Counting the number of ways to decode a string
I am working on problem where I need to decode a string: A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... '...
- 499
3votes
1answer
442views
Find the maximum possible summation of differences of consecutive elements
Array A contains the elements, \$A_1,A_2, \ldots, A_N\$. And array B contains the elements, \$B_1,B_2, \ldots, B_N\$. There is a relationship between \$A_i\$ and \$B_i\$: any element \$A_i\$ ...
- 261
