【LeetCode】0011 盛最多水的容器

https://leetcode-cn.com/problems/container-with-most-water

代码：

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

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        weights = [[0 for _ in range(len(height))] for _ in range(len(height))]
        for i in range(1, len(weights)):
            for j in range(len(weights) - i):
                for k in range(j, j + i):
                    if min(height[j], height[j + i]) * i < max(weights[j][k], weights[k][j + i]):
                        weights[j][j + i] = max(weights[j][k], weights[k][j + i])
                    else:
                        weights[j][j + i] = min(height[j], height[j + i]) * i
        return max(max(row) for row in weights)
    
    


if __name__ == '__main__':
    height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
    print(Solution().maxArea(height))

思路：这道题上面的代码并不能完全AC（会超时，但是实际上结果是对的），但是贴出来是因为这错误太经典了2333。

这道题（我）采用了动态规划的思想，先是解决一个长度的，再找两个长度的最优解再找三个的以此类推，这样要用到三层循环，应该是n^3，但是这样虽然找出了结果，但是会超时，因为代价太大了，对于这道题，暴力也无非是n^2，这不禁让我陷入了沉思。

后来我想明白了，并不是什么都可以用动态规划以达到最好的效果，这道题使用左右指针向里移动（每次移动较小的一边），是最好的解法，因为移动较小的一边说明当前容器如果要扩大，一定是较小的一边是短板（木桶原理，对吧）这样一直记录最大值。

至于为什么这道题暴力复杂度甚至优于动归，原因就是这道题并不存在多个子结构的集合优于全局。因此动归相当于多算了好多无用功。