leecode

限制条件

def ac(n):
    target = [0 for i in range(n+1)]
    target[0]=1
    for i in range(n):
        if i==0 or i==1:
             target[i+1]=i+1
        else:
              j=0
             tmp=0
             while 2**j<=i+1:
                  tmp+=target[i+1-2**j]
                  j+=1
             target[i+1]=tmp
      return target[n]

target[0]=1

ma[i] = max(mi[i-1]*nums[i],nums[i])
mi[i] = min(ma[i-1]*nums[i],nums[i])

假如计划在第 i 天卖出股票，那么最大利润的差值一定是在[0, i-1] 之间选最低点买入；所以遍历数组，依次求每个卖出时机的的最大差值，再从中取最大值。

for i in range(1,len(prices)):
    if prices[i]>prices[i-1]:
        maxprice+=prices[i]-prices[i-1]

主要找波峰波谷位置 

用一个二位数组来记录从l到r的字符串是否为回文串

若s[l,r]是回文串，那么s[l+1,r-1]一定是回文串

状态转移

遍历方式

非动态规划解法

def numSquares(self, n: int) -> int:
    dp=[i for i in range(n+1)]
    dp[0]=0
    for i in range(2,n//2+1):
        for j in range(i*i,n+1):
           dp[j]=min(dp[j],dp[j-i*i]+1)
return dp[n]

o(logn)

left != right

middle= int((left+right)/2)

选优搜索法

放在递归函数的第一行

千万不能放在for或者while循环中

这个参数是随着每次的递归操作而发生改变的

不要破坏当前值

结果一定要有一个全局参数来保存，只用来保存每次递归成功时的结果

如果当前递归过程的处理参数符合要求，则执行相关赋值或其他操作，然后转入下一次递归，如果下一次递归不能找到出口，就把之前相关赋值或其他操作重置为初始状态

check(int k,int j)

能使得递归进行的约束条件

主函数

递归函数

条件判断函数

主函数

递归函数

主函数

递归函数

类型

 def hanota(self, A: List[int], B: List[int], C: List[int]) -> None:
    n= len(A)
    self.move(n,A,B,C)

def move(self,n,A,B,C):
    if n == 1:
        C.append(A[-1])
        A.pop()
        return
    else:
        self.move(n-1,A,C,B)
        C.append(A[-1])
        A.pop()
        self.move(n-1,B,A,C)

n = len(alist)

外层循环

每次选择一个元素并且将整个数组以那个元素分为两部分

每部分分别进行快排

在原数组上直接进行操作

选择元素

分区

最好

最坏

不稳定

出口

分区

调用本递归函数（两部分都快排）

alist l r

1. 选择传入数组中的第一个数

2. 设置两个变量

3. 循环比较

4. 调整指定值的位置

5. 返回下标j

归并排序中间劈一刀，数组分两半，两边排好序，最后把左右两个合并。就是先局部有序，再整体有序。

在原数组上操作

把两个排序好了的列表结合在一起组合成一个单以的有序新列表

合并函数

稳定

出口

取mid 

调用本递归函数（两部分都做归并排序）

alist

o(nlogn)

参数设置

循环遍历alist中相应位置

稳定

for i in range(1,len(alist))

待比较的值

遍历所有已排好的项

一个字典记录出现过的字符

一个头指针0

最大长度max初始化为0

选一个最短的开始作为外层循环

分别判断每个字符串中的前缀是否相同

进位问题需要记录下来

可以转为用一个数字每位✖另一个数字（需要记录进位）

findIp(s, f + i, idx + 1, ip + to_string(num) + ".", res)

深度搜索每一个值为1的点，然后找到面积最大的一个，记得要把每一个已经搜索过的点置零，避免重复搜索以减少计算量

递归里面判断下标限制和是否为1，符合条件就返回num，不符合返回0

nums[mid] < nums[0]

target 和nums[0]

维护一个元素个数为k的最大堆, 将所有数字放入到最大堆中, 全部放完之后, 最大堆中最小的那个元素就是第k个最大的元素

再双层嵌套遍历

以1开头的有(n-1)!个，和k比较

设置一个额外的字典记录每个人所属类别，每次先查找该类别所有人，再把她们的类别改成一样的

然后用一个RES记录最终结果，用最后一个区间的end与下一个的start和end比较

最后返回+从头遍历加载+两个链表遍历

re = ListNode(0)
r = re
carry = 0

空间复杂度o(n)

sortlist(head)

get_mid(head)

伪头节点

prev cur双指针

使用cur遍历 

以n的距离走

快慢指针速度2倍走看是否相遇

一个表示位置的数组+一个队列

双层循环

额外数组

一个用来增加计数，一个用来减少计数，看最后是否为0

可以先用计数器表计算 ss，然后用 tt 减少计数器表中的每个字母的计数器。如果在任何时候计数器低于零，我们知道 tt 包含一个不在 ss 中的额外字母，并立即返回 FALSE。

时间复杂度o(nlogn) 空间复杂度取决于排序算法

或者直接比较len(list(set(alist)))

遍历另一个数组用来比较

o(mlogm+nlogn) o(1)

左右数组的乘积

在push和pop时注意检查是否是最小的那个数

出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。

小顶堆

得到一个递增序列

创新判断条件为比较i与i+1位置

def searchInsert(self, nums: List[int], target: int) -> int:
    left = 0
    right = len(nums)-1
    while left<=right:
        mid = (left+right)//2
        if nums[mid]>=target:
            right = mid-1
        else:
             left = mid+1

return left

用出现次数最少的字符分割字符串，递归调用，当该字符出现次数多于k返回len

用一个变量保存maxlen

因为如果旋转的单位是长度的整数倍相当于没有旋转

我自己没有想到k可以比len大

寻找不重复的数

一个用来遍历所有，另一个用i-1表示就好啦

i=1
count = 1
while i<len(nums):
    if nums[i] == nums[i-1]:
        count+=1
    if count>2:
         nums.pop(i)
         i-=1
   else:
         count=1
    i+=1

分组使用哈希表时要确定好key是什么

if not root:
    return 0
lheight=self.maxDepth(root.left)
rheight=self.maxDepth(root.right)
return max(lheight,rheight)+1

def maxPathSum(self, root: TreeNode) -> int:
    max_sum = [float('-inf')]
    self.max_gain(root,max_sum)
    return max_sum[0]

def max_gain(self,node,max_sum):
    if not node:
        return 0
    left_gain=max(self.max_gain(node.left,max_sum),0)
    right_gain=max(self.max_gain(node.right,max_sum),0)
    price_newpath=node.val+left_gain+right_gain
    max_sum[0]=max(max_sum[0],price_newpath)
    return node.val+max(left_gain,right_gain)

def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
     res=[]
     ans=[]
     self.recr(root,res,ans,sum)
     return ans

def recr(self,root,res,ans,total):
    if root:
        total-=root.val
        res.append(root.val)
        if total==0 and not root.left and not root.right:
            ans.append(res.copy())
        self.recr(root.left,res,ans,total)
        self.recr(root.right,res,ans,total)
        res.pop()

退出条件是root值介于两个待找点之间

while root

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if not root or root==p or root==q:
        return root
    left=self.lowestCommonAncestor(root.left,p,q)
    right=self.lowestCommonAncestor(root.right,p,q)
    if not left:
        return right
    elif not right:
        return left
    else:
        return root

def diameterOfBinaryTree(self, root: TreeNode) -> int:
    maxlen=[0]
    self.height(root,maxlen)
    return maxlen[0]

def height(self,root,maxlen):
    if not root:
        return 0
    lheight=self.height(root.left,maxlen)
    rheight=self.height(root.right,maxlen)
    maxlen[0]=max(maxlen[0],lheight+rheight)
    return max(lheight,rheight)+1

层次遍历，每次把该层最右节点加入结果集合中

按照根节点-右节点-左节点顺序遍历，并且记录该层深度，只有大于深度的节点能加入结果中

def sumOfLeftLeaves(self, root: TreeNode) -> int:
    if not root:
        return 0
    res = [0]
    self.recr(root,res,0)
    return res[0]
def recr(self,root,res,direct):
    if not root.left and not root.right:
        if direct:
            res[0]+=root.val
        return
    if root.left:
        self.recr(root.left,res,1)
    if root.right:
        self.recr(root.right,res,0)
    return

如果是左叶子节点则加上去；如果是左节点进列表；如果是右子节点结束；如果是右节点加进去

保证左右部分数量相同

双指针搜索寻找最优值

m=len(grid)
n=len(grid[0])
queue=[]
d=0
dim=[(-1,0),(1,0),(0,1),(0,-1)]
for row in range(m):
    for col in range(n):
        if grid[row][col]==2:
            queue.append((row,col,d))
while queue:
    q = queue.pop(0)
    for di in dim:
        x=q[0]+di[0]
        y=q[1]+di[1]
        d=q[2]
    if x>=0 and y>=0 and x<m and y<n and grid[x][y]==1:
         queue.append((x,y,d+1))
         grid[x][y]=2
for s in grid:
     if 1 in s:
        return -1
return d

倒转一半

当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。

 if x<0 or (x%10==0 and x!=0):
return False
revernum=0
while revernum<x:
revernum=revernum*10+x%10
x=x//10
return x==revernum or x==revernum//10

def canThreePartsEqualSum(self, A: List[int]) -> bool:
    s=sum(A)
    if s%3:
        return False
    s1=0
    for i in range(len(A)):
        s1+=A[i]
        if s1==s/3:
            for j in range(i+1,len(A)-1):
                 s1+=A[j]
                 if s1==s*2/3:
                     return True
             return False
     return False

def canJump(self, nums: List[int]) -> bool:
right=0
for i in range(len(nums)):
    if i<=right:
        right=max(right,i+nums[i])
if right>=len(nums)-1:
    return True
else:
    return False

def jump(self, nums: List[int]) -> int:
    n = len(nums)
    maxPos, end, step = 0, 0, 0
    for i in range(n - 1):
        if maxPos >= i:
            maxPos = max(maxPos, i + nums[i])
        if i == end:
            end = maxPos
            step += 1
     return step

pre[i]=pre[i−1]+(nums[i]&1)

def reversePairs(self, nums: List[int]) -> int:
    left=0
    right=len(nums)-1
    res=[0]
    self.merge_sort(left,right,nums,res)
    return res[0]
def merge_sort(self,left,right,nums,res):
    if left>=right:
        return
    mid=(left+right)//2
    self.merge_sort(left,mid,nums,res)
    self.merge_sort(mid+1,right,nums,res)
    if nums[mid]>nums[mid+1]:
        self._merge(left,mid,right,nums,res)
def _merge(self,left,mid,right,nums,res):
    blist=nums[left:right+1]
    cur=left
    l=0
    r=mid+1-left
    while l<=mid-left or r<=right-left:
        if l>mid-left:
            nums[cur]=blist[r]
            r+=1
        elif r>right-left:
            nums[cur]=blist[l]
            l+=1
        elif blist[l]<=blist[r]:
            nums[cur]=blist[l]
            l+=1
        else:
            nums[cur]=blist[r]
            res[0]=res[0]+mid-left-l+1
            r+=1
    cur+=1

res=0
for i in range(0,len(row),2):
    if row[i+1]==row[i]^1:
       continue
    res+=1
    for j in range(i+2,len(row)):
        if row[j]==row[i]^1:
            row[i+1],row[j]=row[j],row[i+1]
            break

ret=0
a=0
b=0
for n in nums:
    ret^=n
h=1
while(h & ret ==0):
    h<<=1
for n in nums:
    if n&h==0:
        a^=n
    else:
        b^=n
return [a,b]

def isUnique(self, astr: str) -> bool:
mark = 0
for char in astr:
    move_bit = ord(char) - ord('a')
    if (mark & (1 << move_bit)) != 0:
        return False
    else:
        mark |= (1 << move_bit)
return True

1>>2把1右移2位

deque双端队列接口，最常用的实现类是linkedlist

deque可以实现java中栈和队列

代码

右边第一个比它大的数，维护单调递减的栈，从头到尾遍历

求右边第一个比他小的数，维护单调递增的栈，从头到尾遍历

求左边第一个比它大的数，维护单调递减栈，从尾到头遍历

可以把前n-1补到后面，或者采用遍历2n-1次然后对下标取余数

class Solution {
public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans,-1);
    Deque<Integer> stk = new LinkedList<Integer>();
    for(int i=0;i<2*n-1;i++){
        while(!stk.isEmpty() && nums[stk.peek()] < nums[i%n]){
             ans[stk.pop()]=nums[i%n];
        }
    stk.push(i%n);
    }
    return ans;
}
}

class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
    n = len(nums)
    ret = [-1] * n
    stk = list()

    for i in range(n * 2 - 1):
        while stk and nums[stk[-1]] < nums[i % n]:
             ret[stk.pop()] = nums[i % n]
        stk.append(i % n)
return ret

class Solution {
public String removeDuplicates(String S) {
    StringBuffer stk = new StringBuffer();
    int top=-1;
    for(int i = 0;i < S.length();i++){
        if(top>=0 && S.charAt(i)==stk.charAt(top)){
            stk.deleteCharAt(top);
            top--;
        }else{
            stk.append(S.charAt(i));
            top++;
         }
    }
    return stk.toString();
}
}

class Solution:
def removeDuplicates(self, S: str) -> str:
    stack = []
    n = len(S)
    i = 0
    while i < n:
       if stack and S[i] == stack[-1]:
           stack.pop()
       else:
           stack.append(S[i])
           i+=1

       res = ''.join(stack)
    return res

class Solution:
def evalRPN(self, tokens: List[str]) -> int:
    stack = []
    f1 = lambda a,b : a+b
    f2 = lambda a,b : a-b
    f3 = lambda a,b : a * b
    f4 = lambda a,b : int(a / b) ##取整不能用 a//b
    op = {'+':f1, '-':f2, '*':f3,'/':f4}
    for i in tokens:
        if i in op:
           b = stack.pop()
           a = stack.pop()
           stack.append(op[i](a,b))
        else:
           stack.append(int(i))
    return stack[0]

只有加减和括号

注意要初始化push一个1

class Solution {
public int calculate(String s) {
    int ret = 0;
    int sign = 1;
    int i = 0;
    int n = s.length();
    Deque<Integer> ops = new LinkedList<Integer>();
    ops.push(1);
    while(i<n){
        if(s.charAt(i)==' '){
           i++;
        }else if(s.charAt(i)=='+'){
           sign = ops.peek();
           i++;
        }else if(s.charAt(i)=='-'){
           sign = -ops.peek();
           i++;
        }else if(s.charAt(i)=='('){
           ops.push(sign);
            i++;
        }else if(s.charAt(i)==')'){
            ops.pop();
            i++;
        }else{
            long num = 0;
            while(i<n && Character.isDigit(s.charAt(i))){
                num = num*10 + s.charAt(i)-'0';
                i++;
             }
           ret+=num*sign;
        }
     }
     return ret;
}
}

入栈：数字，没有符号

技巧：另设一个ops，每次当前是符号，就用上一次的符号乘数字结果入栈

class Solution {
public int calculate(String s) {
    char ops = '+';
    int num = 0;
    Deque<Integer> stk = new LinkedList<Integer>();
    for(int i=0;i<s.length();i++){
        if(Character.isDigit(s.charAt(i))){
            num = num * 10 + s.charAt(i) - '0';
        }
        if(!Character.isDigit(s.charAt(i)) && s.charAt(i)!=' ' || i==s.length()-1){
            switch(ops){
                case '+':
                    stk.push(num);
                    break;
                case '-':
                    stk.push(-num);
                    break;
                case '*':
                     stk.push(stk.pop()*num);
                     break;
                default:
                     stk.push(stk.pop()/num);
            }
            num = 0;
            ops = s.charAt(i);
       }
    }
     int ret = 0;
     while(!stk.isEmpty()){
         ret += stk.pop();
     }
     return ret;
}
}

class Solution:
def calculate(self, s: str) -> int:
    ops='+'
    stack = []
    num = 0
    for i,c in enumerate(s):
        if c.isnumeric(): 
            num = num*10 + int(c)
        if c in '+-*/' or i==len(s)-1:
            if ops=="+":
                  stack.append(num)
            if ops=="-":
                  stack.append(-num)
            if ops=="*":
                   stack.append(stack.pop()*num)
            if ops=="/":
                   stack.append(stack.pop()/num)
        num = 0
        ops = c
return sum(stack)

因为队列和维护最大值的栈出队顺序是相反的

所以最好也用一个队列去维护最大值

记录每一个位置的前缀和，一维或者二维

代码

超级零

关键怎么设置状态转移

初始值一定要inf

对于矩阵中的任意一个 1 以及一个 0，我们如何从这个 1 到达 0 并且距离最短呢？根据上面的做法，我们可以从 1 开始，先在水平方向移动，只要与 0 在同一列。随后再在竖直方向上移动，直到到达 0 的位置。这样以来，从一个固定的 1 走到任意一个 0，在距离最短的前提下可能有四种方法，故有4个状态转移函数

我想到了这种方法，但是不知道怎么处理上下左右四个位置，就想要用两个dp存取最小，但是边界难处理，这道题直接用一个数组，每次比较上下左右和自己，很巧妙的动态规划

def digitsum(self,n):
    ans=0
    while n:
        ans=ans+n%10
        n//=10
    return ans

def movingCount(self, m: int, n: int, k: int) -> int:
    vim=set([(0,0)])
    for i in range(m):
        for j in range(n):
            if ((i-1,j) in vim or (i,j-1) in vim) and self.digitsum(i)+self.digitsum(j)<=k:
            vim.add((i,j))
    return len(vim)

class MyHashSet {
    private static final int BASE=769;
    private LinkedList[] data;

    public MyHashSet() {
        data = new LinkedList[BASE];
        for(int i=0;i<BASE;i++){
             data[i] = new LinkedList<Integer>();
        }
    }

    public void add(int key) {
        int h = hash(key);
        Iterator<Integer> it = data[h].iterator();
        while(it.hasNext()){
            Integer ele = it.next();
            if(ele==key){
                 return;
            }
        }
        data[h].offerLast(key);
    }

    public void remove(int key) {
        int h = hash(key);
        Iterator<Integer> it = data[h].iterator();
        while(it.hasNext()){
            Integer ele = it.next();
            if(ele==key){
                 data[h].remove(ele);
                 return;
            }
         }
    }

    public boolean contains(int key) {
         int h = hash(key);
         Iterator<Integer> it = data[h].iterator();
         while(it.hasNext()){
              Integer ele = it.next();
              if(ele==key){
                   return true;
              }
          }
          return false;
    }

    private static int hash(int key){
        return key%BASE;
    }
}

class MyHashMap {
    private class Pair {
    private int key;
    private int value;

    public Pair(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
return key;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}
}

private static final int BASE = 769;
private LinkedList[] data;

/** Initialize your data structure here. */
public MyHashMap() {
data = new LinkedList[BASE];
for (int i = 0; i < BASE; ++i) {
data[i] = new LinkedList<Pair>();
}
}

/** value will always be non-negative. */
public void put(int key, int value) {
int h = hash(key);
Iterator<Pair> iterator = data[h].iterator();
while (iterator.hasNext()) {
Pair pair = iterator.next();
if (pair.getKey() == key) {
pair.setValue(value);
return;
}
}
data[h].offerLast(new Pair(key, value));
}

/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
public int get(int key) {
int h = hash(key);
Iterator<Pair> iterator = data[h].iterator();
while (iterator.hasNext()) {
Pair pair = iterator.next();
if (pair.getKey() == key) {
return pair.value;
}
}
return -1;
}

/** Removes the mapping of the specified value key if this map contains a mapping for the key */
public void remove(int key) {
int h = hash(key);
Iterator<Pair> iterator = data[h].iterator();
while (iterator.hasNext()) {
Pair pair = iterator.next();
if (pair.key == key) {
data[h].remove(pair);
return;
}
}
}

private static int hash(int key) {
return key % BASE;
}
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/design-hashmap/solution/she-ji-ha-xi-ying-she-by-leetcode-soluti-klu9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。题

class ParkingSystem {
    int big,medium,small;

    public ParkingSystem(int big, int medium, int small) {
         this.big = big;
         this.medium = medium;
         this.small = small;
    }

    public boolean addCar(int carType) {
         if(carType==1){
            if(this.big>0){
                this.big--;
                return true;
            }
         } else if(carType==2){
             if(this.medium>0){
                 this.medium--;
                 return true;
             }
         }else if(carType==3){
              if(this.small>0){
                  this.small--;
                  return true;
              }
        }
        return false;
    }
}

    求出所有和为 target 的组合，并且每个数只能使用一次，因此我们可以使用递归 + 回溯的方法来解决这个问题：
我们用 dfs(pos,rest) 表示递归的函数，其中 pos 表示我们当前递归到了数组 candidates 中的第 pos 个数，而 rest 表示我们还需要选择和为rest 的数放入列表作为一个组合；
     对于当前的第 pos 个数，我们有两种方法：选或者不选。如果我们选了这个数，那么我们调用dfs(pos+1,rest−candidates[pos]) 进行递归，注意这里必须满足 rest≥candidates[pos]。如果我们不选这个数，那么我们调用dfs(pos+1,rest) 进行递归；
     在某次递归开始前，如果rest 的值为 0，说明我们找到了一个和为 target 的组合，将其放入答案中。每次调用递归函数前，如果我们选了那个数，就需要将其放入列表的末尾，该列表中存储了我们选的所有数。在回溯时，如果我们选了那个数，就要将其从列表的末尾删除。
上述算法就是一个标准的递归 + 回溯算法，适用于集合没有重复数字的数组

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        combine = []
        idx = 0
        res = []
        self.dfs(candidates,target,combine,idx,res)
        return res

    def dfs(self,candidates,target,combine,idx,res):
        if target<=0 or idx>=len(candidates):
            if target==0:
                res.append(combine)
                return

        self.dfs(candidates,target-candidates[idx],combine+[candidates[idx]],idx,res)
        self.dfs(candidates,target,combine,idx+1,res)
        return

转换为不重复数组，用一个字典记录

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
         res=[]
         temp=[]
         start=0
         freq = sorted(collections.Counter(candidates).items())
         self.back(start,freq,target,res,temp)
         return res

    def back(self,start,freq,target,res,temp):
         if start>=len(freq) or target<=0:
             if target==0:
                 res.append(temp.copy())
                 return

         self.back(start+1,freq,target,res,temp)
         most = min(target//freq[start][0],freq[start][1])

         for i in range(1,most+1):
             temp.append(freq[start][0])
             self.back(start+1,freq,target-i*freq[start][0],res,temp)

         for i in range(most):
              temp.pop()

class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
    alist=[i for i in range(1,10)]
    res=[]
    temp=[]
    idx=0
    self.back(alist,k,n,idx,res,temp)
    return res

def back(self,alist,k,target,idx,res,temp):
    if idx>=len(alist) or len(temp)>=k:
        if len(temp)==k and target==0 and sorted(temp) not in res:
            res.append(sorted(temp))
        return

    temp.append(alist[idx])
    self.back(alist,k,target-alist[idx],idx+1,res,temp)
    temp.pop()
    self.back(alist,k,target,idx+1,res,temp)

确定好回溯函数需要的参数

回溯法

def permutation(self, S: str) -> List[str]:
    if len(S)<=1:
        return [S]
    tmp=[S[0]]
    res=[tmp]
    for i in range(1,len(S)):
        n = len(res)
        for j in range(n):
            base = res.pop(0)
            tmp = base.copy()
            for k in range(len(tmp)+1):
                 tmp.insert(k,S[i])
                 res.append(tmp)
                 tmp =base.copy()
     ans=[]
    for r in res:
       ans.append(''.join(r))
return ans

完全背包，可重复使用元素

def combinationSum4(self, nums: List[int], target: int) -> int:
    dp = [0]*(target+1)
    dp[0]=1
    for i in range(1,target+1):
         for n in nums:
              if i-n>=0:
              dp[i]+=dp[i-n]

    return dp[-1]

def change(self, amount: int, coins: List[int]) -> int:
    dp = [0]*(amount+1)
    dp[0] = 1
    for c in coins:
        for j in range(c,amount+1):
             dp[j] += dp[j-c]
     return dp[-1]

策略为：

从基本情况没有开始，一一添加。
对于每个添加的***，我们从金额 0 到 amount 递归的计算组合数量。
算法：

以基本情况没有***开始组合数量。dp[0] = 1，然后其余等于 0。
遍历所有***面值：
对于每个***，我们将从金额 0 遍历到 amount：
对于每个 x，计算组合数：dp[x] += dp[x - coin]。
返回 dp[amount]

dp[x]表示构成金额x的硬币最少数量

n个物品m大小

把第二大给第3大，第1大给第2大，第一大赋给新的值

分别保留奇数格子和偶数格子中出现次数最多的两个数

然后再减去交叉算重复的点

x表示标记个数-1，y表示周长的整数倍

先求左右分别的积 

再求x ans=x-1

外层遍历指定每一个要抢劫的银行

结束cnt==0

集合

属性

集合划分