Algorithms and Data Structures

  • Profound Academy

    • Status
      • 1
        Implementation
      • 2
        Bitwise operations
      • 3
        Prefix Sums
      • 4
        Sliding window / Two pointers
      • 5
        Modular Arithmetic
      • 6
        Number Theory
      • 7
        Binary Search
      • 8
        Basic Sorting
      • 9
        Greedy Algorithms
      • 10
        Basic Dynamic Programming
      • 11
        Recursion
      • 12
        Linked LIst
      • 13
        Queue & Stack
      • 14
        Binary tree + BST
      • 15
        Divide & Conquer + Advanced Sorting
      • 16
        Heap
      • 17
        Hashing
      • 18
        Graph Representation
      • 19
        BFS

  • Dynamic Programming

    Dynamic programming is the β€œart” of constructing a certain state based on the previous states. When doing computations, we often rely on the previous values calculated during the execution. Fibonacci numbers are a great example that can be calculated using dynamic programming:
    So, to calculate fib(2) we would use the values fib(1) and fib(0). Therefore, obtaining the value for fib(2) = 1. To get the next value in the Fibonacci sequence, we should make use of the value we calculated previously - fib(3) = fib(2) + fib(1) = 1 + 1 = 2. Similarly, fib(4) = fib(3) + fib(2) = 2 + 1 = 3 and fib(5) = fib(4) + fib(3) = 3 + 2 = 5, and the sequence goes on.
    On each iteration, we calculate the current value of the Fibonacci sequence using the previous states that we calculated beforehand. This can be implemented with a list:
    n = ...
    fib = [0, 1]       # fib[0] = 0, fib[1] = 1
    
    for i in range(2, n + 1):
        fib.append(fib[i - 1] + fib[i - 2])
    print(fib[n])
    For a value n = 5, the program would print 5, while for a value n = 7 it would print 13.
    The process of repeatedly calculating the current state (the current Fibonacci number in our case) using the previous states is the essence of Dynamic Programming.
    Β 
    πŸ’‘
    Dynamic programming is a technique to construct the current state based on the previous states.

    Challenge - Tribonacci numbers

    After playing with Fibonacci numbers, you got bored and decided to play with Tribonacci numbers instead. Tribonacci numbers are defined as:
    Your task is to find the n-th Tribonacci number.

    Input

    The input contains a single integer n (1 ≀ n ≀ 30).

    Output

    The output should contain the n-th Tribonacci number.

    Examples

    Input
    Output
    2
    1
    4
    2
    Β 

    Constraints

    Time limit: 1 seconds

    Memory limit: 512 MB

    Output limit: 1 MB

    To check your solution you need to sign in
    Sign in to continue