1.递归

将一个数据序列中的相同的数字放在同一个篮子中，使得每个篮子中的数字个数相同且每个篮子的个数大于等于2，若能恰好分红，则返回篮子个数，否则返回0.

比如 ‘2 2 3 3’，将两个2和两个3，分别放在一个篮子里，返回为2.

比如‘2 2 3 3 3’ 无法平均放入篮子，返回0

比如‘2 3 4 4 2 3 4 4’，返回4.

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 24 19:43:12 2019

@author: janti
"""
        # In[]

def count_blankets(dicta,s,min_count):
    count=0
    flag=1
    while min_count>=2:
        for i in range(len(s)):
            if (dicta[s[i]] % min_count)==0:
                count+=dicta[s[i]]/min_count        
            else:
                flag=0
                count=0
                min_count-=1
                count_blankets(dicta,s,min_count)  
        if flag:
            break
    return count
# In[]

n=9
line='2 3 4 2 3 4 4 4 4'
dicta={}
s=[]
for i in range(n):
    data=int(line.split()[i])
    if data in dicta:
        dicta[data]+=1
    else:
        dicta[data]=1
        s.append(data)
        # In[]
min_count=1000        
for i in range(len(s)):
    if dicta[s[i]]<min_count:
        min_count=dicta[s[i]]
        
if min_count<2:
    res=0
else: 
    res=int(count_blankets(dicta,s,min_count))

print(str(res) + "\n")

通过LeetCode上【70. 爬楼梯】学习（建议）

2. 回溯

2.1 矩阵中的最长递增子序列

找出矩阵中的最长递增路径

import numpy as np          
def  Findlongpath(matrix,i,j,len_vect):
    if len_vect[i][j]:
        return len_vect[i][j]
    cols=len(matrix)
    rows=len(matrix[0])
    maxlen=0
    if i >0 and matrix[i-1][j]>matrix[i][j]:
        maxlen=max(maxlen,Findlongpath(matrix,i-1,j,len_vect))
    if i<cols-1 and matrix[i+1][j] > matrix[i][j]:
        maxlen=max(maxlen,Findlongpath(matrix,i+1,j,len_vect))
    if j>0 and matrix[i][j-1]>matrix[i][j]:
        maxlen=max(maxlen,Findlongpath(matrix,i,j-1,len_vect))
    if j<rows-1 and matrix[i][j+1] > matrix[i][j]:
        maxlen=max(maxlen,Findlongpath(matrix,i,j+1,len_vect))       
    len_vect[i][j] = maxlen+ 1
    return len_vect[i][j]
# In[]
matrix=[[2,3,4],[3,4,5],[6,7,8]]
cols=len(matrix)
rows=len(matrix[0])
max_len_matrix=1
len_vect=np.zeros((cols,rows))
for i in range(cols):
    for j in range(rows):
        len_vect[i][j]=Findlongpath(matrix,i,j,len_vect)
        max_len_matrix=max(max_len_matrix,len_vect[i][j])
print(max_len_matrix)

参考链接：

https://www.cnblogs.com/fanmu/p/9636076.html

利用回溯算法求解 0-1 背包问题

在这里插入图片描述

利用回溯算法求解八皇后问题