取金币

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param coins int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/cb33f5653a064b2eaf1fe30ba18f5977?tpId=196&tqId=40524&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title=
    参考：
        大神：牛客202157047号
    算法：
        题目说明：如果左边或右边没有金币，则金币数量视为1。为了方便计算，我们对coins数组进行扩展，在左右两侧各加一个1，得到tmpCoins。 [5, 6, 4, 8] ==> [1, 5, 6, 4, 8, 1]
        设dp[i][j]表示从下标i~下标j的区间，所能获得的最大积分
        状态转移方程：
            dp[i][i] = coins[i - 1] * coins[i] * coins[i + 1]
            对于区间[i, j]:
                边界考虑：
                    1）最后选取的数是左边界，即最后选取的是coins[i]
                        dp[i][j] = dp[i + 1][j] + coins[i - 1] * coins[i] * coins[j + 1]
                    2）最后选取的数是右边界，即最后选取的coins[j]
                        dp[i][j] = dp[i][j - 1] + coins[i - 1] * coins[j] * coins[j + 1]
                最后选取的数是k，i < k < j
                    dp[i][j] = max(dp[i][j], dp[i][k - 1] + coins[i - 1] * coins[k] * coins[j + 1] + dp[k + 1][j])
    复杂度：
        时间复杂度：O(n^3)
        空间复杂度：O(n^2)
    """

    def getCoins(self , coins):
        n = len(coins)

        coins = [1] + coins + [1]


        dp = [[0] * (n + 2) for _ in range(n + 2)]

        for i in range(1, n + 1):
            dp[i][i] = coins[i - 1] * coins[i] * coins[i + 1]
        for i in range(n, 0, -1):
            for j in range(i + 1, n + 1):
                left = dp[i + 1][j] + coins[i - 1] * coins[i] * coins[j + 1] # 最后选取的是coins[i]
                right = dp[i][j - 1] + coins[i - 1] * coins[j] * coins[j + 1] # 最后选取的是coins[j]
                dp[i][j] = max(left, right)
                for k in range(i + 1, j): # 最后选取的是coins[k]
                    dp[i][j] = max(dp[i][j],
                                   dp[i][k - 1] + coins[i - 1] * coins[k] *
                                   coins[j + 1] + dp[k + 1][j])
        # print dp

        return dp[1][n]


if __name__ == "__main__":
    sol = Solution()

    coins = [5, 6, 4, 8]

    res = sol.getCoins(coins)

    print res