import numpy as np

# approche naive - Complexite : exponentielle O(2n)
def Combinaison(n,k) :
    """Version récursive naïve"""
    if (k == 0) | (k == n) :
        return 1;
    else :
        return(Combinaison(n-1,k-1) + Combinaison(n-1,k))
#test
print( Combinaison(5,2))

# approche Programmation dynamique avec memoisation - Complexite :  O(nk)
def CombinaisonMem(n,k, mat) :
    if (k == 0) | (k == n) :
        return 1;
    else :
        if mat[n,k]>0 :
            return mat[n,k]
        else :
            return CombinaisonMem(n-1,k-1,mat) + CombinaisonMem(n-1,k,mat)
        # Complexite :  O(n*k)
n=5
k=2
mat = np.zeros((n+1,k+1), int) # matrice resultante
print( "mem", CombinaisonMem(n,k, mat))

# approche Programmation dynamique itérative - Complexite :  O(nk)
def Combinaison_Dynamique(n,k):
    mat_res = [[ 0 for j in range (k+1)] for i in range (n+1)]
    # ou  mat_res =  np.zeros((n + 1, k + 1))
    for i in range (n+1):
        mat_res[i][0] = 1
        for j in range (1,k+1): 
            mat_res[i][j] = mat_res[i -1][j] + mat_res[i -1][j -1]
    return mat_res[n][k]
print( "iter", Combinaison_Dynamique(5,2))
#Complexité de la solution: O(nk)