✏️
GitBook
  • Home
  • Projects
    • ORBI Group. Hotels Services
    • ORBI Group. Sales Support System
    • ORBI Group. Financial Management
    • ORBI Group. Client Cabinet
    • BP. Insurance management admin panel
    • Ciklum. Seaports fisheries containers tracking system
  • Higher Education
    • KNUTD (2018 - 2019)
    • School 42 (2017 - 2020)
  • FLG Preparation
    • Algorithms
      • Basics
        • Learn How To Learn
        • Algo task pattern
        • Space/time complexity
      • Two Pointers
        • Tasks
      • Fast and Slow Pointers
        • Tasks
      • Sliding Window
        • Tasks
      • Merge Intervals
        • Tasks
      • In-place Reversal of a Linked List
        • Tasks
      • Two Heaps
        • Tasks
      • K-Way Merge
        • Tasks
      • Top K Elements
        • Tasks
      • Subsets
        • Tasks
      • Modified Binary Search
        • Tasks
      • Greedy Techniques
        • Tasks
      • Backtracking
        • Tasks
      • Dynamic Programming
        • Tasks
        • 0/1 Knapsack Problem
      • Cyclic Sort
        • Tasks
      • Topological Sort
        • Tasks
      • Matrices
        • Tasks
      • Stacks
        • Tasks
    • Data Structures
      • Doubly Linked List
      • Stack
      • Queue
      • Heap
    • Frontend
    • Resources
  • Courses
    • Animations
    • JS Algorithms and Data Structures Course
      • Add Up To
      • Anagrams
      • Binary Search
      • Divide and Conquer
      • Frequency Counter
      • Sliding Window
      • Two Pointers
    • Nest.js
      • Logging
    • PostgreSQL
      • Sequelize
      • SUM
      • COUNT, DISTINCT (unique)
      • WHERE
      • AND, OR, BETWEEN
      • Practice 1
      • IN, NOT IN
      • ORDER BY
      • MIN, MAX, AVG
      • Practice 2
      • Pattern matching with LIKE
      • LIMIT, check for NULL (IS, IS NOT), GROUP BY, HAVING
      • UNION, INTERSECT, EXCEPT
      • Practice 3
      • INNER JOIN
      • LEFT, RIGHT JOIN
      • SELF JOIN
      • USING & NATURAL JOIN
      • AS
      • Practice 4
      • Practice 5. Subrequests
      • DDL - Data Definition Language
      • Practice 6. DDL
      • Primary & foreign keys
      • Check
      • Default
      • Sequences
      • INSERT
      • UPDATE, DELETE, RETURNING
      • Practice 7. DDL(2)
      • Проектирование БД
      • Нормальная форма (НФ)
      • Представление (View)
      • Создание представления
      • Обновляемые представления
      • Опция Check
      • Practice 8. Views
      • CASE WHEN
      • COALESCE & NULLIF
      • Practice 9. Logic
    • DevOps
      • Linux
        • File System
        • Command Line
        • Package Manager
        • VIM
        • Linux Accounts & Groups (Users & Permissions)
        • Pipes & Redirects
        • Shell / bash scripting
        • Environment Variables
      • Networking
      • SSH
      • Git for DevOps
      • Nexus. Artifact repository manager
      • Docker
      • Jenkins
  • Daily Log
    • 2023
Powered by GitBook
On this page
  • Framework to solve DP problems
  • Approaches
  • Good examples

Was this helpful?

  1. FLG Preparation
  2. Algorithms

Dynamic Programming

PreviousTasksNextTasks

Last updated 1 year ago

Was this helpful?

Framework to solve DP problems

  1. Define the objective function. Function you want to minimize or maximize in your problem.

  2. Identify base cases. These are the boundaries of the problem — the starting point of your DP algorithm.

  3. Write down the transition function (recurrence relation). Function to transit from one subproblem to another subproblem. Takes the system from one state to another.

  4. Identify the order of execution. Order in which subproblems are solved.

  5. Identify the location of the answer. For example, F(n) or F(0).

Approaches

  1. Bottom-Up (Tabulation). Iterative.

  2. Top-Down (Memoization). Recursive.

Good examples

LogoLoading...LeetCode
LogoN-th Tribonacci Number - LeetCodeLeetCode
https://github.com/andreygrehov/dp/blob/master/lecture4/lecture4.go