import numpy as np
                                ##### Exercice 1 #####
def coeffBinRec(n,p):
    if p > n:
        return 0
    elif p == 0 :
        return 1
    else :
        return coeffBinRec(n-1,p-1)+coeffBinRec(n-1,p)



##### Principe de mémoïsation #####
dico = {} # Dictionnaire dans lequel les valeurs sont stockées

def coeffBin(n,p):
    if (n,p) in dico:
        return dico[(n,p)]
    else:
        if p == n:
            dico[(n,p)] = 1
        elif p == 0:
            dico[(n,p)] = 1
        else:
            dico[(n,p)] = coeffBin(n-1,p-1) + coeffBin(n-1,p) # Mémoïsation
        return dico[(n,p)]


##### Principe de bas en haut #####
def coeffBin2(n,p):
    t = np.zeros((n + 1, p + 1),dtype = np.int64)
    for i in range(n-p+1):
        t[i, 0] = 1
    for i in range(1, p + 1):
        t[i, i] = 1
    for i in range(2, n + 1):
        for j in range(max(1,p-(n-i)), min(p,i) + 1):
            t[i, j] = t[i - 1, j - 1] + t[i - 1, j]
    return t[n, p]


                                ##### Exercice 2 #####
def sommeRec(P,i,j):
    if i == len(P)-1 :
        return P[i][j]
    else:
        return P[i][j] + max(sommeRec(P,i+1,j),sommeRec(P,i+1,j+1))


##### Principe de mémoïsation #####
dico2 = {} # Dictionnaire dans lequel les valeurs sont stockées

def sommeRecMem(P,i,j):
    if (i,j) in dico2:
        return dico2[(i,j)]
    else:
        if i == len(P)-1:
            dico[(i,j)] = P[i][j]
        else:
            dico[(i,j)] = P[i][j] + max(sommeRec(P,i+1,j),sommeRec(P,i+1,j+1))
        return dico[(i,j)]

##### Principe de bas en haut #####
def sommeRecBasHaut(P):
    n = len(P)
    Q = [[P[i][j] for j in range(i+1)] for i in range(n)]
    for i in range(n - 2,-1,-1):
        for j in range(i + 1):
            Q[i][j] = Q[i][j] + max(Q[i + 1][j], Q[i + 1][j + 1])
    return Q[0][0]

                                ##### Exercice 3 #####
import numpy as np

dico = {}

def distance(b,c,i,j):
#    M = np.zeros(len(b) + 1,len(c) + 1)
    if (i,j) in dico:
        return dico[(i,j)]
    else:
        if i == 0:
            dico[(0,j)] = j
        elif j == 0:
            dico[(i,0)] = i
        else:
            if b[i-1] == c[j-1]:
                dico[(i,j)] = distance(b,c,i - 1,j - 1)
            else:
                dico[(i,j)] = min(distance(b,c,i - 1,j),distance(b,c,i,j - 1),distance(b,c,i - 1,j - 1)) + 1
        return dico[(i,j)]

                                ##### Exercice 4 #####
def sousTab1(T):
    n = len(T)
    sMax = T[0]
    dMax = 0
    fMax = 1
    for d in range(n):
        for f in range(d + 1,n + 1):
            s = sum(T[d:f])
            if s > sMax or (s == sMax and f-d < fMax-dMax) :
                sMax = s
                dMax = d
                fMax = f
    return T[dMax : fMax], sMax

def Maximum(L):
    m = L[0]
    ind = 0
    for i in range(len(L)):
        if L[i] > m:
           ind, m = i,L[i]
    return m,ind

def sousTab2(T):
    n = len(T)
    sMax = [T[0]]
    dMax = [0]
    for i in range(n-1):
        sMax.append(max(sMax[i] + T[i + 1], T[i + 1]))
        if sMax[i + 1] == T[i + 1]:
            dMax.append(i + 1)
        else :
            dMax.append(dMax[i])
    m, ind = sMax[0], 0
    for i in range(n):
        if sMax[i] > m:
            m,ind = sMax[i],i
        elif sMax[i] == m and i-dMax[i] < ind - dMax[ind]:
            m,ind = sMax[i],i
    return T[dMax[ind]:ind+1],m


                                ##### Exercice 5 #####
import numpy as np

def orga(I):
    n = len(I)
    M = [I[0][2]]
    for k in range(1,n):
        i = k
        while I[i][1] > I[k][0] and i >= 0:
            i = i-1
        if i < 0:
            M.append(max(M[k-1],I[k][2]))
        else :
            M.append(max(M[k-1],M[i]+I[k][2]))
    return M[n-1]

def orga2(I):
    n = len(I)
    M = [I[0][2]]
    intervalles = [[0]]
    for k in range(1,n):
        m = -np.inf
        i = None
        for j in range(k):
            if I[j][1] < I[k][0] and I[j][1] > m:
                m, i = I[j][1],j
        if i == None:
            if M[k - 1] > I[k][2]:
                intervalles.append(intervalles[k - 1])
                M.append(M[k-1])
            else:
                intervalles.append([k])
                M.append(I[k][2])
        else :
            if M[k - 1] > I[k][2] + M[i]:
                intervalles.append(intervalles[k - 1])
                M.append(M[k-1])
            else:
                intervalles.append(intervalles[i]+[k])
                M.append(I[k][2]+M[i])
    return M[n-1], intervalles[n - 1]

I = [(1,2,100),(1,3,200),(4,5,200),(3,7,400),(6,7,100),(8,10,200),(6,10,400)]