5868. 可互换矩形的组数

力扣https://leetcode-cn.com/problems/number-of-pairs-of-interchangeable-rectangles/

我真是太蠢了，居然用的是遍历做的。后来剪纸了一下，都超时。下面贴一下我的代码。

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        cnt = 0
        for i in range(len(rectangles)):
            w1,h1 = rectangles[i][0],rectangles[i][1]
            for j in range(i+1,len(rectangles)):
                w2,h2 = rectangles[j][0],rectangles[j][1]
                if w1/h1 == w2/h2:
                    cnt=cnt+1
        return cnt
                

class Solution:
    def interchangeableRectangles(self, rectangles: List[List[int]]) -> int:
        cnt=0
        dp=[[False for _ in range(len(rectangles))] for _ in range(len(rectangles))]
        for i in range(len(rectangles)):
            w1, h1 = rectangles[i][0], rectangles[i][1]
            for j in range(i + 1, len(rectangles)):
                if i>=1:
                    if dp[i - 1][j] == True and dp[i - 1][j - 1] == True and dp[i][j-1]== True:
                        dp[i][j] = True
                        cnt = cnt + 1
                    else:
                        w2, h2 = rectangles[j][0], rectangles[j][1]
                        if w1 / h1 == w2 / h2:
                            dp[i][j] = True
                            cnt = cnt +1
                else:
                    w2, h2 = rectangles[j][0], rectangles[j][1]
                    if w1 / h1 == w2 / h2:
                        dp[i][j] = True
                        cnt = cnt + 1
        return cnt
                

其实用组合公式就可以了，反思一下自己为啥没想到