In this repo, there are 3 different kinds of implementations of common software-intensive problems (Fibonacci, Grid Traveler, Sum Problems and Construct Problems):
- Naive implementation;
- Dynamic implementation with memoization;
- Dynamic implementation with tabulation.
I couldn't find any sources only explaining tabulation, but here is a good source explaining both approaches.
More info about dynamic programming can be found here.
The study was guided by this class using JavaScript. This made me want to try to implement the same problems with different languages: Java, Swift, and Haskell. Currently, this is an ongoing project.
Consists of the implementation of the Fibonacci Sequence, where, given a number, the function calculates the value of passed index into the sequence.
Given a matrix with size M and N, how many paths can you find from point (x: 0, y: 0) to (x: M, y: N), with the only possible moves being going right and down.
Similar problems, but with different focuses. All 3 problems have the same 2 inputs: target number and a list of numbers. Here, we try to find if we can achieve the target number by adding numbers from the list.
- Can Sum: can sum numbers from the list to achieve the target number;
- How Sum: a sequence of numbers to be added to achieve a target number;
- All Sum: all possible sequence of numbers that when added, gives the target number.
Similar to the Sum problems, here we have a target word to achieve and a list of substrings that we can use as we please.
- Can Construct: if a word can be created given a list of strings;
- Count Construct: how many different ways a word can be created given a list of strings;
- All Constructs: which different ways a word can be created given a list of strings.
| Problem | Java | Swift | Haskell |
|---|---|---|---|
| Fibonacci | Code | Code | - |
| Grid Traveler | Code | Code | - |
| Sum problems | Code | Code | - |
| Construct problems | Code | Code | - |