석자 합병 문제 - 동태적 기획, 욕심

           DP  。      3   ：

(1) N   ，             ，    ：         2     ，                。   N      

  ：             ，        ，      ，           。              。

(2) N   ，             ，    ：         2     ，                。   N              （   ）。

(3)  (2)                ，           ，     ？
--------------------- 
  ：JeanCheng 
  ：CSDN 
  ：https://blog.csdn.net/gatieme/article/details/49206193 
    ：         ，         ！

import numpy as np


def merge_stones(stones):
    num_stones = len(stones)

    m = np.zeros(shape=(num_stones,num_stones))
    p = np.zeros(shape=(num_stones,num_stones))

    for i in range(num_stones - 1):
        m[i][i+1] = stones[i] + stones[i+1]

    for i in range(1,num_stones-1):
        for j in range(num_stones - 1 - i):
            k = j + i + 1

            min = 10000000000000
            for l in range(j+1,k):
                temp = m[j][l] + m[l+1][k] + np.sum(stones[j:k+1])
                if min > temp:
                    min = temp
                    min_p = l

            m[j][k] = min
            p[j][k] = min_p

    return m[0][num_stones-1],p


def print_ret(stones,p,start,last,first_part=False):
    if start < last:
        print('(',end='')
        mid = int(p[start][last])
        print_ret(stones,p,start,mid,True)
        print_ret(stones,p,mid+1,last,False)
        print(')',end='')
    else:
        print(stones[start],end='')

    if first_part:
        print(',',end='')


if __name__ == '__main__':
    # while True:
    #     num_stones = int(input('Input:
'))
    #     stones = []
    #     for s in map(int, input().split()):
    #         stones.append(s)
    #
    #     if num_stones == len(stones):
    #         merge_stones(stones)
    #     else:
    #         print('      ')

    max,p = merge_stones([4,4,5,9])
    print_ret([4,4,5,9],p,0,len([4,4,5,9])-1)