Dynamic Programming

0. 

1. examples:

def fib(n):

  if n == 1 or n == 2:

    result = 1

  else 

     result = fib(n-1) + fib(n-2)

  return result

this is very in-efficient, O(2^n), and we use the following solution, which is called memoized solution

def fib(n, memo):

  if memo[n] != null:

    return memo[n]

  if n ==1 or n ==2:

    result = 1

  else 

    result = fib(n-1, memo) + fib(n-2, memo)

  memo[n] = result

  return result

Memo is an array, store memo = {1, 1, 2, 3, 5, 8 ,...}

def fib_bottom_up(n):

  if n ==1 or n ==2: 

    return 1

  bottom_up = new int[n+1]

  bottom_up[1] =1

  bottom_up[2] =1

  for i from 3 to n:

    bottom_up[i] = bottom_up[i-1] + bottom[i-2]

  return bottom_up[n]

上一篇:Neural Network Programming Deep Learning with PyTorch


下一篇:Java 的API(API: Application(应用) Programming(程序) Interface(接口))