看似一致的面积问题
这两道题看起来是比较类似的,都是求二维矩阵中的面积问题,但是两题的解题思路完全不一致。
第一道题可以使用使用二维dp数组表示构成最大正方形的最长边长,但是第二题不行,它边长是由长宽构成,如果使用动态规划,那么需要两个dp数组,一个代表最长宽,一个代表最长高。
如果用第二题dp代表最大矩形面积,这样又会没有递推关系。
但是关于矩形面积都有一个统一思路就是求,最长宽高,得到最长的宽高也就得到了最大矩形面积
221. 最大正方形——正方形最大面积
...About 2 min
这两道题看起来是比较类似的,都是求二维矩阵中的面积问题,但是两题的解题思路完全不一致。
第一道题可以使用使用二维dp数组表示构成最大正方形的最长边长,但是第二题不行,它边长是由长宽构成,如果使用动态规划,那么需要两个dp数组,一个代表最长宽,一个代表最长高。
如果用第二题dp代表最大矩形面积,这样又会没有递推关系。
但是关于矩形面积都有一个统一思路就是求,最长宽高,得到最长的宽高也就得到了最大矩形面积