【Pythonアルゴリズム】動的計画法（Dynamic Programming）

### Algorithim

### init dp list 
dp[0]  = 1
dp[1]  = -1
dp[2]  = -1
dp[3]  = -1
dp[4]  = -1
dp[5]  = -1
dp[6]  = -1
dp[7]  = -1
dp[8]  = -1
dp[9]  = -1
dp[10] = -1
dp[-1] = 0
dp[-2] = 0

### update process

root1: step +1
root2: step +2
dp[i] = root1 + root2 

### update dp list

# case: i = 1 

root1 = dp[0]  = 1 ### step +1
root2 = dp[-1] = 0 ### step +2
dp[1] = root1 + root2 = 1

# case: i = 2

root1 = dp[1]  = 1 ### step +1
root2 = dp[0]  = 1 ### step +2
dp[1] = root1 + root2 = 2

...

# case: i = 10

root1 = dp[9]  = 55 ### step +1
root2 = dp[8]  = 34 ### step +2
dp[10] = root1 + root2 = 89

### Python Code

### DP Bottom to Top
def dpFunc(n):
    """
    :type n: int
    :rtype: int
    """
    dp = [-1] * (n + 1)
    dp[0] = 1
    
    for i in range(1, n + 1):
        root_1 = dp[i - 1] if i - 1 >= 0 else 0
        root_2 = dp[i - 2] if i - 2 >= 0 else 0
        dp[i] = root_1 + root_2

### Algorithim

### init dp list 
dp[0]  = 1
dp[1]  = -1
dp[2]  = -1
dp[3]  = -1
dp[4]  = -1
dp[5]  = -1
dp[6]  = -1
dp[7]  = -1
dp[8]  = -1
dp[9]  = -1
dp[10] = -1
dp[-1] = 0
dp[-2] = 0

### update dp list

root1: step +1
root2: step +2
dp[i] = root1 + root2 

### recursive function

refFunc(num):
	if num < 0: return 0
	if dp[num]!=-1: return dp[num]
	else:
		root1 = refFunc[num-1] ### step +1
		root2 = refFunc[num-2] ### step +2
		dp[num] = root1 + root2 
		return dp[num]

### update process

root1: step +1
root2: step +2
dp[i] = root1 + root2
 
### update dp list

recFunc(10)
dp[10] = 89

### Python Code

### DP Top to Bottom
def dpFunc(n):
    """
    :type n: int
    :rtype: int
    """
    
    dp = [-1] * (n + 1)
    dp[0] = 1
    
    def recFunc(num):
        
        if num < 0: return 0
        if dp[num] != -1: return dp[num]
        else:
            root_1 = recFunc(num-1)
            root_2 = recFunc(num-2)
            dp[num] = root_1 + root_2
            return dp[num]

    return recFunc(n)