python - 有没有办法可以使用动态编程来表示这个循环

Question

我有一个循环条件，它的时间复杂度为 O(N^2)，我想使用动态编程执行相同的计算。我已经采取了以下步骤来实现这一目标，但我在某个时候遇到了困难，我真的不知道到底该怎么做才能得到想要的结果。

    credits_count = Counter(credits)
    recurring_credits = [credit for credit in credits_count.keys() if credits_count[credit] > 1 and credit >= 1000]
    non_rec_group = len(recurring_credits)
    credit_group = []
    per = 5/100
    for i in range(len(credits)):
        found_group = False
        for j in range(len(recurring_credits)):
            low_range = recurring_credits[j] - (per*recurring_credits[j])
            high_range = recurring_credits[j] + (per*recurring_credits[j])
            
            if credits[i] >= low_range and credits[i] <= high_range:
                found_group = True
                credit_group.append(j)
                break
                
        if not found_group:
            credit_group.append(non_rec_group)
            non_rec_group += 1


credits = [4.0, 13155.62, 160929.27, 43580.43, 115000.0, 100.0, 5.0, 4.0, 2220.09, 160229.27, 55055.42, 8.0, 115.0, 5.75, 100000.0, 5060.85, 51675.2, 160929.27, 8.0, 100000.0, 200.0, 10.0, 9141.07, 160929.27, 48094.73, 8.0, 100000.0, 12721.54, 8.0, 44014.51, 258784.72, 200000.0, 100.0, 5.0, 14552.21, 42183.84, 140542.72, 200.0, 10.0, 8.0, 95000.0]       

上述循环的输出是：

    print(credit_group)
[2, 3, 0, 4, 5, 6, 7, 8, 9, 0, 10, 11, 12, 13, 1, 14, 15, 0, 16, 1, 17, 18, 19, 0, 20, 21, 1, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 1] 

动态部分：

n1, n2 = len(credits), len(recurring_credits)
results = [0 for _ in range(n2-1) for _ in range(n1-1)]
for i in range(len(credits)):
#     found_group = False
    for j in range(len(recurring_credits)):
        if credits[i] == recurring_credits[j]:
            low_range = recurring_credits[j] - (per*recurring_credits[j])
            high_range = recurring_credits[j] + (per*recurring_credits[j])
            if credits[i] >= low_range and credits[i] <= high_range:
                results[i] = 1+results[i]
            else:
                results[i] = 1+results[non_rec_group]
            

标签： pythonalgorithmdynamic-programming