Dynamic Programming

Fibonacci Numbers

long long F(long long n){
  if(n<=1) return 1;
  return F(n-1)+F(n-2);
}

Runtime is similar to the actual definition of Fibonacci numbers: \(T(n)=\begin{cases} \Theta(1) & n\leq1 \\ T(n-1)+T(n-2)+\Theta(1) & n>1\end{cases}\) \(F(n)=\begin{cases} 1 & n\leq1 \\ F(n-1)+F(n-2)+1 & n>1 \end{cases}\)

Problem:

• To calculate F(50), it is necessary to calculate F(48) and F(49)
• To calculate F(49), necessary to calculate F(48)
• It gets worse

Possible solution:

• To avoid calculating values multiple times, store intermediate calculations in a table
• When storing intermediate results, this process is called memoization
• We save (memoize) computed answers for possible later reuse, rather than re-computing the answer multiple times

Memoized version:

long long F(long long n, bool isFirstCall= false){
  static long long *memo;
  if(isFirstCall){
    if(memo != NULL){delete[] memo;}
    if(n !=0){
      memo = new long long [n+1];
      for(int i=0; i<n+1; i++){
        memo[i]=0;
      }
    }
  }
  if(n<=1) return 1;
  if(memo[n]==0)
  memo[n]=F(n-1)+F(n-2);
  return memo[n];
}

use ‘static’ instead of global variables.

Top-down and Bottom-up Algorithms

This also allows for another approach:

• Our implementation is top-down
• From the very top, we break the problem into sub-problems
• All divide-and-conquer algorithms we have seen are top-down

Alternative approach is bottom-up approach

• Solve smaller problems and use these to build a solution for the problem
• Merge sort could be implemented bottom-up
  • Divide the array into groups of size m and sort each group with insertion sort
  • Merge adjacent pairs into groups of size 2m where possible
  • Repeat this successively until the entire list is sorted

  long long F(long long n){
    if(n<=1) return 1;
    long long ret=1, prev=1;
    for(long long i=2l i<=n; i++){
      ret=ret+prev;
      prev=ret-prev;
    }
    return ret;
  }
  

Dynamic Programming

In solving optimization problems, the top-down approach may require repeatedly obtaining optimal solutions for the same sub-problem. Dynamic programming is distinct from divide-and-conquer, as the divide-and-conquer approach works well if the sub-problems are essentially unique

• Storing intermediate results would only waste memory

If sub-problems re-occur, the problem is said to have overlapping sub-problems

source

“K-MOOC 허재필 교수님의 <인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고> 강좌의 15-1 동적계획법의 방법론 이해 중(http://www.kmooc.kr/courses/course-v1:SKKUk+SKKU_46+2020_T1)”

back next

Comments

Post comment

Loading...