[Kotlin] Algorithm - Dynamic Programming (DP)

Dynamic Programming(DP)

How to divide big problems into small problems, save the results from solving small problems, and use them to solve big problems again

How to solve a complex problem by dividing it into simple problems

Condition

Optional Substructure

• Big problems can be divided into small problems, and big problems can be solved by collecting answers to small problems.

Overlapping Subproblem

• The same small problems arise repeatedly.

Key technology

Memoization

• If the same calculation must be repeated, the previous calculated value is stored in memory (cache) and reused to eliminate redundant calculations.
• Use memory space to speed up overall execution.
• Calculates whenever results are needed (Lazy-Evaluation).
• It is used in various computational tasks such as Fibonacci sequence calculation, shortest path search, combination and permutation calculation.

Tabulation

• Solve small problems, store the results in an array or table, and recycle the stored values to solve big problems.
• Even non-required values are calculated in advance (Eager-Evaluation).
• It is useful for problems such as optimization problems and shortest path problems.

Top-Down Approach

• Use memoization as a way to approach from top to bottom.
• a way of solving big problems by dividing them into small ones
• Use a recursive call to transfer and recycle the results. Stack overflow may occur.

fun fibHelper(n: Int): Int {
    return fibonacci(n, IntArray(n + 1))
}

fun fibonacci(n: Int, dp: IntArray): Int {
    if (n < 2) return n
    if (dp[n] == 0) dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp)
    return dp[n]
}

Bottom-Up Approach

• Use tebulation as a bottom-to-top approach.
• A way to solve a small problem and gradually solve a big problem
• Through the repetition statement, the stored values are recycled by calculating the array one by one from zero in the ignition type.

fun fibonacci(n: Int): Int {
    val dp = IntArray(n + 2)
    dp[1] = 1
    for (i in 2..n)
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
}

Recursive vs. Dynamic Programming

The difference between dynamic programming and recursive can be compared by Fibonacci sequence calculation.

In the case of recursive, the same small problems are repeatedly calculated, and as n increases, the number of duplicate calculations increases.

/**
 * 재귀로 피보나치 수열 계산 구현
 */
fun fibonacci(n: Int): Int {
    if (n < 2) return n
    return fibonacci(n - 1) + fibonacci(n - 2)
}

Recursion Tree Structure

On the other hand, the dynamic programming method does not perform duplicate calculations because it stores and reuses calculation results.

Dynamic Programming Tree Structure(Call-solid line, reuse-dotted line)

Reference

https://www.spiceworks.com/tech/devops/articles/what-is-dynamic-programming/

https://didu-story.tistory.com/220

https://hongjw1938.tistory.com/47

https://code-lab1.tistory.com/7

https://freedeveloper.tistory.com/276

https://goo-gy.github.io/2019-12-09-memoization

https://stackoverflow.com/questions/6469437/what-is-the-difference-between-caching-and-memoization

https://velog.io/@nninnnin7/Dynamic-programming-1

https://hyeinisfree.tistory.com/25

https://dltjrals2.github.io/algorithm/algorithm-dynamic-programming

https://www.hanbit.co.kr/media/channel/view.html?cms_code=CMS4008657032

https://devsub.tistory.com/2

https://comdoc.tistory.com/entry/33-피보나치-수열과-동적-프로그래밍

[Kotlin] Algorithm - The remaining operational distribution law - Dico

모듈러 산순 분배 법칙

dico.me