状压DP

数据结构与算法

发布日期: 2020-12-07

看到题目有什么特点可以用状压？

提示1


集合类状压
可以用比较少(小于30)的集合表示当前某些数/物品 用(多少)/没用 的状态

提示2


连通类状压
棋盘/树(长或宽小于30)中按某种规则放置固定长度的 物品

集合类状态压缩动态规划

枚举子集模板


for(int subset=set;subset!=0;subset=(subset-1)&set)
{
    f[set] = f[subset] + 转移规则
}
subset = set
while(subset):
    f[set] = f[subset] + 转移规则 
    subset = (subset-1)&set

acwing91 最短Hamilton路径-旅行商问题

1 注意+-的优先级大于位运算
2 if(i-(1<<j)>>k & 1)//从状态i中去掉点j后 的集合(i-(1<<j))中包含点k(i-(1<<j)>>k & 1) 
则能从点k走到点j从而从状态f[i-(1<<j)][k]+w[k][j]到达状态f[i][j]
f[state][j] = f[state_k][k]+weight[k][j] , state_k = state集合除掉j之后的子集 state_k包含点k

state怎么表示一个集合？ ->二进制 位置上1代表包含0代表不包含
0,1,4
state = 10011

state表示哪些点被用过 
j代表当前停在哪个点上->state除掉j 
走过点的集合i中去除掉点j表示：i - (1 << j)，
比方说i是{0,1,4}，j是1，那么i = 10011，(1 << j) = 10，i - (1 << j) = 10001

在函数里定义的变量 存放在栈里->C++默认的栈的大小4MB 所以大数组开在外面比较安全
定义为static变量 存放在堆里

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 20,M=1<<20;
int n;
int f[M][N],weight[N][N];

int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> weight[i][j];
        }
    }
    
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;//最开始的时候 我们这个人在0号点 状态集合里只包含0这1个点 所以状态表示就是1 在0没走过任何路程 所以初始0
    for(int i=0;i<1 << n;i++)//枚举所有状态
    {
        for(int j=0;j<n;j++)//对于第j位不用   i - (1<<j) 比方j=3 那么i-(1 << j)表示不用第j位  
        {
            if((i >> j) & 1)//首先判断状态i是否合法 即该集合里是否包含j 判断i的第j位是否是1 把第j位移到个位和0001比
            for(int k=0;k<n;k++)//f[i][j] = f[i_k][j]+weight[k][j]
            {//i_k = i-(1<<j)的第k位是否是1
                if(i-(1 << j) >> k & 1)
                    f[i][j] = min(f[i][j],f[i-(1 << j)][k]+weight[k][j]);
            }
        }
    }
    cout << f[(1 << n) -1][n-1] << endl;//1<<n表示所有点都遍历过了 并且停在了n-1点上
    return 0;
}

leetcode 351 安卓系统手势解锁

我们都知道安卓有个手势解锁的界面，是一个 3 x 3 的点所绘制出来的网格。用户可以设置一个 “解锁模式” ，通过连接特定序列中的点，形成一系列彼此连接的线段，每个线段的端点都是序列中两个连续的点。如果满足以下两个条件，则 k 点序列是有效的解锁模式：

以下是一些有效和无效解锁模式的示例：

无效手势：[4,1,3,6] ，连接点 1 和点3 时经过了未被连接过的2 号点。
无效手势：[4,1,9,2] ，连接点 1 和点 9 时经过了未被连接过的 5号点。
有效手势：[2,4,1,3,6] ，连接点 1 和点3 是有效的，因为虽然它经过了点2 ，但是点 2 在该手势中之前已经被连过了。
有效手势：[6,5,4,1,9,2] ，连接点 1 和点9 是有效的，因为虽然它经过了按键 5 ，但是点5 在该手势中之前已经被连过了。
给你两个整数，分别为 m 和 n ，那么请你统计一下有多少种不同且有效的解锁模式，是至少需要经过 m 个点，但是不超过 n 个点的。

两个解锁模式不同需满足：经过的点不同或者经过点的顺序不同。

解锁模式中的所有点互不相同。
假如模式中两个连续点的线段需要经过其他点，那么要经过的点必须事先出现在序列中（已经经过），不能跨过任何还未被经过的点。

$f[i][j][state]$ 代表$state$状态下最后落点$j$ 总共划了$i+1$个点的可能性总数
初始化 $f[0][k][00k00]=1$
状态转移条件:
$j->k$

1.$k->j$不需要中间节点(k和j相邻时) $cond[j][k]==0$
2.当前状态$state$中有$k->j$的中间节点$cond[j][k]$

class Solution:
    def numberOfPatterns(self, m: int, n: int) -> int:
        f = [[[0]*(1<<9) for _ in range(9)] for _ in range(n)]
        for k in range(9):
            f[0][k][1<<k]=1
        cond = [[0]*9 for _ in range(9)]
        # 三条横的中间点要到
        cond[0][2] = cond[2][0]=(1<<1)
        cond[3][5] = cond[5][3]=(1<<4)
        cond[6][8] = cond[8][6]=(1<<7)
        # 三条纵的中间点要到
        cond[0][6] = cond[6][0]=(1<<3)
        cond[1][7] = cond[7][1]=(1<<4)
        cond[2][8] = cond[8][2]=(1<<5)
        # 两条对角的中间点要到
        cond[0][8] = cond[8][0]=(1<<4)
        cond[2][6] = cond[6][2]=(1<<4)
        for i in range(1,n):
            for j in range(9):
                for k in range(9):
                    for state in range(1<<9):
                        if f[i-1][k][state]==0 or (state&(1<<j))!=0:
                            continue
                        #1 k->j不需要中间节点(当两点相邻时) 2 当前状态state中有k->j的中间节点
                        if k!=j and (cond[k][j]==0 or state&cond[k][j]!=0):
                            f[i][j][state | (1<<j)] += f[i-1][k][state] 
        res = 0
         
        for i in range(m-1,n):#为啥是m-1->n-1 因为m-1代表m个点
            for j in range(9):
                for state in range(1<<9):
                    res += f[i][j][state]
        return res

leetcode464 我能赢吗-博弈状压

在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定一个整数maxChoosableInteger（整数池中可选择的最大数）和另一个整数desiredTotal（累计和），判断先出手的玩家是否能稳赢（假设两位玩家游戏时都表现最佳）？

你可以假设maxChoosableInteger不会大于 20，desiredTotal不会大于 300。

博弈状压dp

maxChoosableInteger不会大于 20
不可重复用一个数，则可以用二进制state的第i位是1代表当前和用了i
$f[state]$代表对当前操作的人而言当前状态能赢还是必输:
遍历$[1,maxChoosableInteger]$中每个当前状态$state$还未选的$i$,则当前能赢的两个条件

1.当前操作$+$的数$i>=$剩余目标和$resid$
2.当前操作$+i$后,留给对手的状态使得对手必输

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        # 如果可选的最大>目标和 先手直接赢
        if maxChoosableInteger>=desiredTotal:return True
        # 如果两个人把所有数都用完了依然<目标和 先手后手都输
        if maxChoosableInteger*(maxChoosableInteger+1)//2<desiredTotal:return False
        f = [0]*(1<<maxChoosableInteger)
        # 当前操作时剩余目标和,当前状态
        def dfs(resid,state):
            if f[state]!=0:
                return f[state]
            # 遍历每个候选可用位
            for i in range(1,maxChoosableInteger+1):
                tmp = 1<<(i-1)
                # 该位还没被用过
                if tmp & state ==0:
                    # 如果剩下的目标和<当前做加操作的人选的+的i or 对手选了i但输了
                    if resid<=i or not dfs(resid-i,tmp|state):
                        f[state] = True
                        return True
            f[state] = False
            return False
        return dfs(desiredTotal,0)

leetcode 526 优美的排列

假设有从 1 到 N 的N个整数，如果从这N个数字中成功构造出一个数组，使得数组的第 i位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一个优美的排列。条件：

第i位的数字能被i整除
i 能被第 i 位上的数字整除
现在给定一个整数 N，请问可以构造多少个优美的排列？

示例:

输入: 2
输出: 2
解释: 

第 1 个优美的排列是 [1, 2]:
  第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
  第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除

第 2 个优美的排列是 [2, 1]:
  第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
  第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除

数据范围

1.N 是一个正整数，并且不会超过15。

状态表示
$f[state][i]$代表当前已经排好的集合$state$,以及当前序列最后一个数是$i$
状态转移
$通过cnt1(state)$计算一个二进制数中1的个数得到当前序列长度,则新加入序列的$ne$在序列中的就是第$cnt1(state)+1$个
同时需要满足优美排列
$ne\%(cnt1(state)+1)==0或(cnt1(state)+1)\%ne==0$时
$f[state|ne][ne] +=f[state][cur]$

答案

以任意一个数作为序列结尾,序列中包含所有1~N中的数的方案数之和$\sum_{i=1}^{N}f[(1<<N)-1][i]$

class Solution:
    def countArrangement(self, N: int) -> int:
        f = [[0]*N for _ in range(1<<N)]
        def cnt1(x):
            res = 0
            while x:
                x -= x&-x
                res+=1
            return res
        for i in range(N):
            f[1<<i][i]=1
        
        for state in range(1<<N):
            for cur in range(N):
                if (state>>cur)&1:
                    for ne in range(N):
                        if cur==ne or (state>>ne)&1:continue
                        idx = cnt1(state)+1
                        if (ne+1)%idx==0 or idx%(ne+1)==0:
                            f[state|(1<<ne)][ne]+=f[state][cur] #状态state最后一个是第i个      
        res = 0
        for i in range(N):
            res+=f[(1<<N)-1][i] 
        return res

leetcode 638 大礼包-7进制状压

在LeetCode商店中，有许多在售的物品。

然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。

每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。

任意大礼包可无限次购买。

示例

输入: [2,5], [[3,0,5],[1,2,10]], [3,2]
输出: 14
解释: 
有A和B两种物品，价格分别为¥2和¥5。
大礼包1，你可以以¥5的价格购买3A和0B。
大礼包2， 你可以以¥10的价格购买1A和2B。
你需要购买3个A和2个B， 所以你付了¥10购买了1A和2B（大礼包2），以及¥4购买2A。

数据范围

1.最多6种物品， 100种大礼包。
2.每种物品，你最多只需要购买6个。
3.你不可以购买超出待购清单的物品，即使更便宜。

思路

由条件1,2可知最终答案的每个礼包的个数最多只需用7位7进制数来描述

状态表示
$f[state]$:$7$进制集合状态$state$下的最小

状态转移
遍历每个礼包
$ne = cur|(speacial[i])_{7进制}$

转移条件:$ne_{7进制}$中的每一位不能超过$needs_{7进制}$中的每一位

$f[ne] = min(f[ne],f[cur]+sum(speacial[i])_{10进制}) $

class Solution:
    def shoppingOffers(self, price: List[int], special: List[List[int]], needs: List[int]) -> int:
        dec = [1,7,49,343,2401,16807,117649]
        #把集合S数组转换为7进制的10进制表示的集合状态
        def get7state(s,n):
            res = 0
            for i in range(n):
                res+=s[i]*dec[i]
            return res
        #检查是否可以再买一个礼包S--条件3:你不可以购买超出待购清单的物品，即使更便宜。
        def check(s,n,pack):
            for i in range(n):#7进制第i位就是第i个物品的数量，加上当前大礼包后和needs的第i位a物品数量进行比较
                if (pack%7)+s[i]>needs[i]:
                    return False
                pack //=7#相当于向右移一位，那么前一位的物品就没了，下一次循环时pack%7 = 第i+1位的物品数。
            return True
        #把单件物品也封装成一个7进制礼包方便后面进行完全背包
        # 在示例1中相当于[1,0,2] [0,1,5]
        for i in range(len(price)):
            tmp = [0]*(len(price)+1)
            tmp[len(price)]=price[i]
            tmp[i]=1
            special.append(tmp)
        #[[3,0,5],[1,2,10],[1,0,2],[0,1,5]]
        box = len(special)#礼包种类数 4
        goods = len(price)#物品种类数 2
        # 7进制下的物品数集合状态 [3,2] 3*1+2*7
        tot = get7state(needs,goods)
        f = [float('inf')]*(tot+1)#17
        f[0]=0
        # 背包问题
        # 遍历第i个礼包
        for i in range(box):
            # 遍历体积
            for cur in range(tot+1):
                # 第i个大礼包能否再买一个
                if not check(special[i],goods,cur):continue
                # 如果可以,则可以到达 下一个状态state = 当前7进制状态+第i个大礼包的7进制状态
                ne = cur+get7state(special[i],goods)
                # 状态state最小花费为min(f[state],状态j最小花费+第i个大礼包的价格)
                f[ne] = min(f[ne],f[cur]+special[i][goods])
        return f[tot]

leetcode 691 贴纸拼词

我们给出了 N 种不同类型的贴纸。每个贴纸上都有一个小写的英文单词。

你希望从自己的贴纸集合中裁剪单个字母并重新排列它们，从而拼写出给定的目标字符串 target。

如果你愿意的话，你可以不止一次地使用每一张贴纸，而且每一张贴纸的数量都是无限的。

拼出目标target 所需的最小贴纸数量是多少？如果任务不可能，则返回 -1。

示例

输入：["with", "example", "science"], "thehat"
输出：3
解释：
我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
此外，这是形成目标字符串所需的最小贴纸数量。

数据范围

stickers 长度范围是[1, 50]。
stickers 由小写英文单词组成（不带撇号）。
target 的长度在[1, 15]范围内，由小写字母组成。
在所有的测试案例中，所有的单词都是从 1000
个最常见的美国英语单词中随机选取的，目标是两个随机单词的串联。
时间限制可能比平时更具挑战性。预计 50 个贴纸的测试案例平均可在35ms内解决。

思路

将$target$的每一位是否填充作为状态,通过填充$stickers$中包含$target$中字符串的$sticker$转移状态

状态表示
$f[state]$表示$target$填充状态为$state$时的最小取用贴纸次数

状态转移
遍历每个能到达的状态$cur$
从$cur$出发遍历$stickers[k]$
遍历$cur$中位数为$0$的位$j$,其对应字符$target[j]$在$stickers[k]$中个数够用就把$cur[j]$填1
$ne = cur + \sum(j<<1) 如果stickers[k]中target[j]够用$

$f[ne] = f[cur]+1$

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n,m = len(stickers),len(target)
        f = [float('inf')]*(1<<m)
        cnt = [[0]*26 for _ in range(n)]
        can = [[] for _ in range(26)]#包含字母ch的sticker的序列
        for i in range(n):
            for ch in stickers[i]:
                idx = ord(ch)-ord('a')
                cnt[i][idx]+=1
                if can[idx]==[] or can[idx][-1]!=i:
                    can[idx].append(i)

        f[0] = 0
        for cur in range(1<<m):
            if f[cur]==float('inf'):continue
            # 对于状态i中还是0的位 我们遍历一遍stickers[k]只要能填target[i]字符串 就填上 作为i能到达的一种ne状态
            # 找第一个当前状态是0的字符串 target[d]对应的那些包含target[d]的stiker的下标数组can[d]---从而确保状态10 -> 11 和 01 -> 11的重复情况不出现
            d = 0
            for j in range(m):
                if not cur&(1<<j):
                    d = j
                    break
            d = ord(target[d])-ord('a')
            
            for k in can[d]:
                ne = cur
                tmp = cnt[k][:]#创建一个临时统计量
                # 遍历target每一位j
                for j in range(m):
                    # 已经填好了的位不用管
                    if ne&(1<<j):continue
                    # 如果stickers[k]还有字符串target[j]可填
                    if tmp[ord(target[j])-ord('a')]>0:
                        ne|=(1<<j)
                        tmp[ord(target[j])-ord('a')]-=1
                f[ne] = min(f[ne],f[cur]+1)
        return f[(1<<m)-1] if f[(1<<m)-1]!=float('inf') else -1

未优化重复情况$TLE$

class Solution:
    def minStickers(self, stickers: List[str], target: str) -> int:
        n,m = len(stickers),len(target)
        f = [float('inf')]*(1<<m)
        cnt = [[0]*26 for _ in range(n)]
        for i in range(n):
            for ch in stickers[i]:
                cnt[i][ord(ch)-ord('a')]+=1
        
        f[0] = 0
        for cur in range(1<<m):
            if f[cur]==float('inf'):continue
            # 对于状态i中还是0的位 我们遍历一遍stickers[k]只要能填target[i]字符串 就填上 作为i能到达的一种ne状态
            for k in range(n):
                ne = cur
                tmp = cnt[k][:]
                # 遍历target每一位j
                for j in range(m):
                    # 已经填好了的位不用管
                    if ne&(1<<j):continue
                    # 如果stickers[k]还有字符串target[j]可填
                    if tmp[ord(target[j])-ord('a')]>0:
                        ne|=(1<<j)
                        tmp[ord(target[j])-ord('a')]-=1
                f[ne] = min(f[ne],f[cur]+1)
        return f[(1<<m)-1] if f[(1<<m)-1]!=float('inf') else -1

leetcode 698划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出： True
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

数据范围

1 <= k <= len(nums) <= 16
0 < nums[i] < 10000

状压dp

状态表示
$f[state]$用$state$中位数为$1$的数的集合满足状态转移约束
$tot[state]$用$state$中位数为$1$的数的集合的数的总和
状态转移
遍历每个能用的$num$
当前状态能转移到下一个状态的合法条件:
除去已经合法的分组的数，能不能和当前加进来的$num$组成一个新的组
即当前和余$target$下的数$resid$+$num$<$target$:
即:当满足条件 $tot[state] =k*target + resid \\\\ resid = tot[state]\quad mod\quad target \\\\ 如果num+resid <=target => num<=target-resid\\\\$ 时，有
$f[state|idx[num]] = True $

答案

$f[(1<class Solution: def canPartitionKSubsets(self, nums: List[int], k: int) -> bool: nums.sort() target,resid = sum(nums)//k,sum(nums)%k if resid or nums[-1]>target:return False f = [False]*(1<<len(nums)) f[0] = True tot = [0]*(1<<len(nums)) for state in range(1<<len(nums)): if not f[state]:continue for i,num in enumerate(nums): # 下一个状态ne ne = state|(1<<i) if state!=ne and not f[ne]: # 当前状态tot[state]=k*target + resid # resid = tot[state]%target # 如果num+resid<=target => num<=target-resid 则我们可以把num加入当前集合 if (num<=target-(tot[state]%target)): f[ne]=True tot[ne] = tot[state]+num else: break # f[1<<len(nums)-1] = 用掉所有数之后且在状态转移过程中一直满足我们的约束 return f[-1]

leetcode 847 访问所有节点的最短路径

给出graph为有 N 个节点（编号为0, 1, 2, ..., N-1）的无向连通图。

graph.length = N，且只有节点 i和 j连通时，j != i在列表graph[i]中恰好出现一次。

返回能够访问所有节点的最短路径的长度。你可以在任一节点开始和停止，也可以多次重访节点，并且可以重用边。

示例

输入：[[1,2,3],[0],[0],[0]]
输出：4
解释：一个可能的路径为 [1,0,2,0,3]

数据范围

1 <= graph.length <= 12
0 <= graph[i].length < graph.length

最短路二进制状态表示

class Solution(object):
    def shortestPathLength(self, graph):
        n = len(graph)
        queue = collections.deque((1 << x, x) for x in range(n))
        dist = [[float('inf')]*n for _ in range(1<<n)]
        for i in range(n):dist[1<<i][i] = 0

        while queue:
            state, cur = queue.popleft()
            d = dist[state][cur]
            if state == (1<<n) - 1: return d
            for ne in graph[cur]:
                state_ne = state | (1 << ne)
                if d + 1 < dist[state_ne][ne]:
                    dist[state_ne][ne] = d + 1
                    queue.append((state_ne,ne))

状压dp

状态表示
$f[state][i]$遍历过的节点集合$state$,落在点$i$上时最短路径长度
状态转移
松弛$f[state|ne][ne] = f[state][cur]+1 \quad if \quad f[state][cur]+1 <f[state|ne][ne]$

假如说$state==state_{ne}$ 则说明$ne$在访问节点集合(已经被松弛更新过的点才会在$state$中)中,
且通过$ne$使得状态$state$有更短路,则需要重新对$state$所有点更新一遍确保更新ne后遍历顺序在ne前的点没有漏更新

比如example1的[1,0,2,0,3]，1,0,2,0和1,0,2对应状态一样都是7(111)，但是1,0,2,0是由1,0,2转移过来的，它们状态都是7，即$dp[7][0]$其实等于$dp[7][2]+1$。如果你只求一遍（即while(repeat)循环），就可能会导致你用$dp[7][2]$更新完$dp[7][0]$，你又有了新的$dp[7][0]$值，但是用$dp[7][0]$扩展路径的那一步循环已经过去了，你没有对$dp[7][0]$进行扩展，可能会漏掉一些路径。

class Solution:
    def shortestPathLength(self, graph: List[List[int]]) -> int:
        n = len(graph)
        dist = [[float('inf')]*n for i in range(1<<n)]
        # 从点i出发且只经过i的路径长度初始化为0
        for i in range(n):
            dist[1<<i][i]=0
        
        for state in range(1<<n):
            repeat = True
            while repeat:
                repeat = False
                for cur,d in enumerate(dist[state]):
                    for ne in graph[cur]:
                        state_ne = state | (1<<ne)
                        if d+1<dist[state_ne][ne]:
                            dist[state_ne][ne] = d+1
                            if state == state_ne:
                                repeat = True
        # 答案 从点i作为终点且经过所有点的路径长度最小值
        return min(dist[(1<<n)-1])

leetcode 935 骑士拨号器-滚动数组状压

骑士可以按$ne$所示进行移动：
$ne = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]$
这一次，我们将“骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳N-1 步。每一步必须是从一个数字键跳到另一个数字键。

每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下N 位数字。

你能用这种方式拨出多少个不同的号码？

因为答案可能很大，所以输出答案模10^9 + 7。

示例

输入：1
输出：10

数据范围

1 <= N <= 5000

思路

因为每个位置$i$除第一次放置外只能由去确定的$ne[i]$的位置

状态表示
$f[i]$ 第$i$次跳完后跳到位置$i$的方案数
状态转移
$f[ne[i]] += f[i]$

答案

跳$n$次后落在$0~9$中每个数的方案数之和
$\sum_{i=0}^{9}f[i]$

class Solution:
    def knightDialer(self, n: int) -> int:
        ne = [[4,6],[6,8],[7,9],[4,8],[3,9,0],[],[1,7,0],[2,6],[1,3],[2,4]]
        f1 = [1]*10
        mod = 1e9+7
        for ep in range(n-1):#我们已经放了一次在初始位置了 所以只需要循环n-1次
            f2 = [0]*10
            for idx,pre in enumerate(f1):
                for nei in ne[idx]:
                    f2[nei]+=pre
                    f2[nei]%=mod
            f1 = f2
        return int(sum(f1)%mod)

leetcode 943 最短超级串

给定一个字符串数组 A，找到以 A 中每个字符串作为子字符串的最短字符串。

我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。

示例:

输入：["alex","loves","leetcode"]
输出："alexlovesleetcode"
解释："alex"，"loves"，"leetcode" 的所有排列都会被接受。

数据范围

1.1 <= A.length <= 12
2.1 <= A[i].length <= 20

状压dp

最终拼接的结果一定是累计重叠长度最长的情况
因此我们可以对A中每对第i、第j个字符串计算重叠长度overlaps[i][j]

状态表示
$f[state][cur]$:当前接到总串尾巴上的是$A[cur]$,当前A数组总共用的状态为$state$的最大累计重叠长度
状态转移
$f[state^pre][pre] = f[state][cur] + overlaps[pre][cur] \quad if 更新后>更新前$
同时维护一个$pre[state][cur]$作为当前用掉的字符串下标的集合$state$,最后一个接上的字符串下标$cur$时累计最大的前继下标

答案

则我们需要取用掉$n$个字符串后累计重叠长度最长时最后用到的字符串$idx\quad of \quad max(f[(1<<n)-1])$,通过$idx_{maxsums}$倒序向前推得有更新$sums_overlaps$的节点并加入拼接顺序列表$order$,同时考虑到有一部分字符串之间是没有重叠的,那么就得再用一个状态数组$st$记录加入$order$的字符串,对于没有加入的(与其他字符串无重叠的)字符串可以任意拼接至尾部

对$order$中的字符串进行拼接,因为我们有$overlaps[i-1][i]$,所以$order[i] = order[i][overlaps[i-1][i]:]$

class Solution:
    def shortestSuperstring(self, A: List[str]) -> str:
        n = len(A)

        overlaps = [[0]*n for _ in range(n)]
        for i,x in enumerate(A):
            for j,y in enumerate(A):
                if i==j:continue
                for ans in range(min(len(x),len(y)),-1,-1):
                    if x.endswith(y[:ans]):
                        overlaps[i][j] = ans
                        break

        f = [[0]*n for _ in range(1<<n)]
        pre = [[None]*n for _ in range(1<<n)]
        for state in range(1,1<<n):
            for i in range(n):
                if (state>>i)&1:
                    state_pre = state^(1<<i)
                    if state_pre==0:continue
                    for j in range(n):
                        if (state_pre>>j)&1:
                            # 累计重叠长度越大越好
                            val = f[state_pre][j]+overlaps[j][i]
                            # 选累计重叠长度最大的j作为前缀
                            if val>f[state][i]:
                                f[state][i] = val
                                pre[state][i] = j

        # 根据最大累计重叠长度的前缀得到拼接顺序
        order = []
        state = (1<<n)-1
        i = f[-1].index(max(f[-1]))#i = max(xrange(N), key = dp[-1].__getitem__)
        while i is not None:#为什么是not None 而不能while i:?因为i如果是0时 是有可能有pre[state][0]的 这种情况就会导致while循环提前停止
            order.append(i)
            state,i = state^(1<<i),pre[state][i]

        order = order[::-1]
        st = [False]*n

        for i in order:
            st[i]=True
        # order.extend([i for i in xrange(N) if not seen[i]])
        for i in range(n):
            if not st[i]:
                order.append(i) 
        res = [A[order[0]]]
        for i in range(1,len(order)):
            overlap = overlaps[order[i-1]][order[i]]
            res.append(A[order[i]][overlap:])
        return "".join(res)

leetcode 980不同路径Ⅲ

在二维网格 grid 上，有 4 种类型的方格：

1 表示起始方格。且只有一个起始方格。
2 表示结束方格，且只有一个结束方格。
0 表示我们可以走过的空方格。
-1 表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。

每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。

示例:

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

数据范围

1 <= grid.length * grid[0].length <= 20

分析

首先对所有合法坐标(grid[i][j]!=-1)映射为0~cnt

状态表示

$f[j][state]$表示当前落在第$j$个点上状态为$state$(经历过$state$中位数为$1$的点)的方案数

状态转移
$f[j_{next}][state | j_{next}] += f[j][state] ,其中j_{next}代表点j能到的邻居点$

需要考虑当前落点$j$状态能继续往$j_{next}$走的条件:

$j$被$state$包含
有方案数到$f[j][state]$

最终答案

经历过的点==所有点,落点为end的方案数$f[end][(1<<tot)-1]$

class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        dirs = [[1,0],[-1,0],[0,1],[0,-1]]
        m,n = len(grid),len(grid[0])
        idx = [[0]*m*n for _ in range(m*n)]
        f = [[0]*(1<<m*n) for _ in range(m*n)]
        pairs = []
        m,n = len(grid),len(grid[0])
        start,end,tot=0,0,0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==-1:continue
                idx[i][j] = tot
                pairs.append([i,j])
                if grid[i][j]==1:start = idx[i][j]
                if grid[i][j]==2:end = idx[i][j]
                tot+=1
        f[start][1<<start]=1
        # f[j][state] 落在j点上 状态state
        # 遍历每个状态
        for state in range(1<<tot):
            # 遍历每个候选 出发点j
            for j in range(tot):
                # 不合法:如果当前状态没有点j 则j不能作为当前落点 or 当前状态state 落点j没有方案数
                if not (state>>j) & 1 or f[j][state]==0:continue
                for dx,dy in dirs:
                    nx,ny = pairs[j][0]+dx,pairs[j][1]+dy
                    if nx<0 or nx>=m or ny<0 or ny>=n or grid[nx][ny]==-1 or ((state >> idx[nx][ny])&1):continue
                    f[idx[nx][ny]][state|(1<<idx[nx][ny])]+=f[j][state]
        return f[end][(1<<tot)-1]

leetcode 1125 最小的必要团队

作为项目经理，你规划了一份需求的技能清单req_skills，并打算从备选人员名单people中选出些人组成一个「必要团队」（编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表）。

所谓「必要团队」，就是在这个团队中，对于所需求的技能列表req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。

我们可以用每个人的编号来表示团队中的成员：例如，团队team = [0, 1, 3]表示掌握技能分别为people[0]，people[1]，和people[3]的备选人员。

请你返回任一规模最小的必要团队，团队成员用人员编号表示。你可以按任意顺序返回答案，本题保证答案存在。

示例

输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
输出：[0,2]

数据范围

1 <= req_skills.length <= 16
1 <= people.length <= 60
1 <= people[i].length, req_skills[i].length, people[i][j].length<= 16
req_skills和people[i]中的元素分别各不相同
req_skills[i][j], people[i][j][k]都由小写英文字母组成
本题保证「必要团队」一定存在

思路

状态表示
$f[state]$为技能满足状态为$state$时需要的最少人数数组
状态转移
遍历$people$中的每个人

遍历$0~(1<<n)-1$每个状态$cur$,则$cur$加上$people[i]$能到的下一个状态为$ne=cur|skill(people[i])$

$f[ne] = f[state] + [i] (满足条件时转移:如果ne现在最少人数>cur最少人数+1)$

答案

所有技能都被满足时的最少人数数组
$f[(1<<n)-1]$

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n = len(req_skills)
        f = [list(range(len(people))) for _ in range(1<<n)]
        f[0]=[]
        # 把技能映射为 状态
        state = {}
        for i in range(n):
            state[req_skills[i]]=1<<i
        
        for i in range(len(people)):
            skill = 0
            for s in people[i]:
                skill|=state[s]
            for cur,cur_ls in enumerate(f):
                ne = cur|skill
                if ne!=cur and len(f[ne])>len(f[cur])+1:
                    f[ne]=cur_ls+[i]
        return f[(1<<n)-1]

leetcode 1178 猜字谜

外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。

字谜的迷面puzzle 按字符串形式给出，如果一个单词word符合下面两个条件，那么它就可以算作谜底：

单词word中包含谜面puzzle的第一个字母。
单词word中的每一个字母都可以在谜面puzzle中找到。
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及"based"（其中的 "s" 没有出现在谜面中）。
返回一个答案数组answer，数组中的每个元素answer[i]是在给出的单词列表 words 中可以作为字谜迷面puzzles[i]所对应的谜底的单词数目。

示例

输入：
words = ["aaaa","asas","able","ability","actt","actor","access"], 
puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]
输出：[1,1,3,2,4,0]
解释：
1 个单词可以作为 "aboveyz" 的谜底 : "aaaa" 
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"
没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。

数据范围

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j]都是小写英文字母。
每个puzzles[i]所包含的字符都不重复。

思路

状态表示

将字谜puzzle及单词word按包含a~z中字母集合转化为$26$位$2$进制数
状态转移
用字典word_dic记录words中不同状态数的个数
枚举puzzles中的每个puzzle
构建puzzle包含puzzle[0]的状态子集subset
遍历$subset$中的每个状态$state$,有$res+=word\underline{~} dic[state] 如果state \in word\underline{~} dic$
$(说明puzzle的子集状态state在words中有word\underline{~} dic[state]个对应的word可作为谜底) $

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        res = []
        n = len(words)
        word_state = [0]*n
        for i in range(n):
            for j in words[i]:
                word_state[i] |= 1<<(ord(j)-ord('a'))
        # 统计包含字符种类状态为state的字符串有多少个
        # state["pleas"]=state["please"] = 1<<p+1<<l+1<<e+1<<a+1<<s
        word_dic = {}
        for state in word_state:
            word_dic[state] = word_dic.get(state,0)+1
        # 遍历所有谜面
        for puzzle in puzzles:
            # 将谜面puzzle的包含puzzle[0]所有子状态加入subset中
            subset = set()
            # 状压常规写法:搜所有包含puzzle[0]的状态子集
            state_p = 0
            for ch in puzzle:
                state_p|=1<<(ord(ch)-ord('a'))
            tmp = state_p
            while tmp:
                if (tmp&(1<<(ord(puzzle[0])-ord('a')))):
                    subset.add(tmp)
                tmp = (tmp-1)&state_p
            sums = 0
            # 遍历所有包含puzzle[0]的子集中字符种类状态在words中的个数
            for state in subset:
                # 如果dic中有word的
                if state in word_dic:
                    sums+=word_dic[state]
            res.append(sums)
        return res

leetcode 1255 得分最高的单词集合

你将会得到一份单词表words，一个字母表letters（可能会有重复字母），以及每个字母对应的得分情况表score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由letters里的字母拼写出的任意属于 words单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

玩家需要用字母表letters 里的字母来拼写单词表words中的单词。
可以只使用字母表letters 中的部分字母，但是每个字母最多被使用一次。
单词表 words中每个单词只能计分（使用）一次。
根据字母得分情况表score，字母 'a','b','c', ... ,'z' 对应的得分分别为 score[0], score[1],...,score[25]。
本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

示例

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

数据范围

1 <= words.length <= 14
1 <= words[i].length <= 15
1 <= letters.length <= 100
letters[i].length == 1
score.length ==26
0 <= score[i] <= 10
words[i]和letters[i]只包含小写的英文字母。

思路

状态表示
$state$:用了$words$中各个单词的状态
遍历$1 \sim (1<<n)$每个状态$cur$计算不同字母个数及状态对应的分数$score(cur)$
合法状态需要满足$cur$中每个字母$\leq$给定的字母表$letters$中每个字母的个数

答案

$max(score(state)) 对所有合法状态state$

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        n = len(words)
        wordscore = [0]*n
        wordchar = [[0]*26 for _ in range(n)]
        letterchar = [0]*26
        for ch in letters:
            letterchar[ord(ch)-ord('a')]+=1
        for i in range(n):
            word = words[i]
            for ch in word:
                wordscore[i]+=score[ord(ch)-ord('a')]
                wordchar[i][ord(ch)-ord('a')]+=1
        res = 0
        # 遍历每个状态
        for cur in range(1<<n):
            tot = [0]*26
            curscore = 0
            # 遍历cur中位为1的用到的word[j] 累加wordscore[j] 计算cur的分数
            # 并统计以及状态cur中26个字母各自的个数tot[]
            j=0
            while cur>0:
                if cur&1:
                    for k in range(26):
                        tot[k]+=wordchar[j][k]
                    curscore+=wordscore[j]
                cur>>=1
                j+=1
            # 遍历cur的每个字母个数tot[i] 需要tot[i]<=letterchar[i] 我们能用的字母集合letters中每个字母的个数
            flag = True
            for i in range(26):
                if tot[i]>letterchar[i]:
                    flag = False
                    break
            if flag:
                res = max(res,curscore)
        return res

leetcode 1434 每个人戴不同帽子的方案数

总共有 n个人和 40 种不同的帽子，帽子编号从 1 到 40 。

给你一个整数列表的列表hats，其中hats[i]是第 `i个人所有喜欢帽子的列表。

请你给每个人安排一顶他喜欢的帽子，确保每个人戴的帽子跟别人都不一样，并返回方案数。

由于答案可能很大，请返回它对10^9 + 7取余后的结果。

示例

输入：hats = [[3,4],[4,5],[5]]
输出：1
解释：给定条件下只有一种方法选择帽子。
第一个人选择帽子 3，第二个人选择帽子 4，最后一个人选择帽子 5。

数据范围

n == hats.length
1 <= n <= 10
1 <= hats[i].length <= 40
1 <= hats[i][j] <= 40
hats[i] 包含一个数字互不相同的整数列表。

思路

状态表示
$f[i][state]$:处理到第$i$顶帽子时,n个人选美选好帽子的状态为$state$的方案数

状态转移
子集:
从第$1$顶帽子遍历到第$max(hats)$顶帽子
第i顶帽子是 |1 由当前的状态中的人选 |2 不由当前状态中的人选
$f[i][state] = f[i-1][state] + \sum_{j}f[i-1][state-(1<<j)] (如果第j个人能选第i顶帽子)$

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        maxhat = max(max(hats[i]) for i in range(len(hats)))
        mod = 1e9+7
        n =  len(hats)
        f = [[0]*(1<<n) for _ in range(maxhat+1)]
        hat2person = collections.defaultdict(list)
        for i in range(n):
            for h in hats[i]:
                # hat2person[h] = hat2person.get(h,[])
                hat2person[h].append(i)
        # 处理0个帽子,没有人用帽子的方案数=1
        f[0][0]=1
        # 逐个遍历帽子 则到第i个帽子的时候前面的人都没用过第i顶帽子
        for i in range(1,maxhat+1):
            for state in range(1<<n):
                # 如果不用第i个帽子,方案数=处理了前i-1个帽子的方案数
                f[i][state] = f[i-1][state]
                for j in hat2person[i]:#遍历对第i顶帽子能用的人j
                    if (state >> j)&1:#如果当前状态有第j个人 则当前状态能从集合中去掉j 不选第i个帽子时的状态转移过来
                        f[i][state] += f[i-1][state-(1<<j)]
                f[i][state]%=mod        
        return int(f[maxhat][(1<<n)-1])

leetcode1542 找出最长的超赞子字符串

给你一个字符串 s 。请返回 s 中最长的超赞子字符串的长度。

「超赞子字符串」需满足满足下述两个条件：

该字符串是 s 的一个非空子字符串
进行任意次数的字符交换后，该字符串可以变成一个回文字符串

示例

输入：s = "3242415"
输出：5
解释："24241" 是最长的超赞子字符串，交换其中的字符后，可以得到回文 "24142"

数据范围

1 <= s.length <= 10^5
s 仅由数字组成

思路

回文子串中各个数字中最多只有一个是奇数,因此我们可以用子串$s[i:j]$的奇偶性状态判断是否回文,等价于$state[s[:i]]$和$state[s[:j]]$在位数上最多只有一位不同

状态表示
维护状态映射到下标的前缀奇偶性字典$prefix$
$prefix[state]=j$为$s[:j]$中$0\sim 9$各个数字个数的奇偶性状态为state
状态转移

$state$初始化为0000000000

遍历$s$中的每个字符,当前遍历到了第$j$个字符$num$,则$s[:j]$中数$num$的个数$+1$,奇偶性与$state$中$1<<num$位相反,所以通过异或将当前状态更新为$state \bigoplus (1<<num)$

如果是第$1$次碰到奇偶性状态$state$,则$f[state]=j$
1. 找全偶子串:如果是第$\geq 2$次碰到奇偶性状态$state$,则$state[s[:j]]-state[s[:prefix[state]]]=0$ 即子串$s[prefix[state]:j]$的奇偶性为全偶数,那么可以用子串$s[prefix[state]:j]$的长度更新$res=max(res,j-prefix[state])$
2. 找只有1个奇数的子串:依次更改$state$中的每个位置的奇偶,$state_{ne}=state^(1<<k) for k in [0,9]当state_{ne}在字典中(下标小于j的时候出现过)$,则$state[s[:j]]-state_{ne}[s[:prefix[state_{ne}]]]=1$ 即子串$s[prefix[state_{ne}]:j]$的奇偶性为只有一个奇数,那么可以用子串$s[prefix[state_{ne}]:j]$的长度更新$res=max(res,j-prefix[state_{ne}])$

class Solution:
    def longestAwesome(self, s: str) -> int:
        n = len(s)
        prefix = {0:-1}
        res,state = 0,0
        for j in range(n):
            num = ord(s[j])-ord("0")
            state ^= (1<<num)
            if state in prefix:#如果有这个状态 则s[prefix[state]:j]奇偶性为全偶 所以更新答案
                res = max(res,j-prefix[state])
            else:#如果第一次出现这个状态
                prefix[state] = j
            # 当前状态更改一位数的奇偶性的状态state_ne
            for k in range(10):
                state_ne = state ^ (1<<k)
                if state_ne in prefix:#如果state_ne在之前有更小的下标碰到过,则子串s[prefix[state_ne]:j]是只有一位数个数是奇数的子串
                    res = max(res,j-prefix[state_ne])
        return res

leetcode 1681 最小不兼容性

给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中，使得同一个子集里面没有两个相同的元素。

一个子集的不兼容性是该子集里面最大值和最小值的差。

请你返回将数组分成 k 个子集后，各子集不兼容性的和的最小值，如果无法分成分成 k 个子集，返回 -1 。

子集的定义是数组中一些数字的集合，对数字顺序没有要求。

示例

输入：nums = [1,2,1,4], k = 2
输出：4
解释：最优的分配是 [1,2] 和 [1,4] 。
不兼容性和为 (2-1) + (4-1) = 4 。
注意到 [1,1] 和 [2,4] 可以得到更小的和，但是第一个集合有 2 个相同的元素，所以不可行。

数据范围

1 <= k <= nums.length <= 16
nums.length 能被 k 整除。
1 <= nums[i] <= nums.length

思路

dfs+剪枝

dfs枚举每种合法的组合并计算兼容性
状压dp

状态表示

$f[state]$ 已经凑好了若干组且已经用的数为1的二进制集合状态为state的所有方案中的最小值
状态转移

闫式dp分析

子集$j$为$state$这种情况下最后一组加入的组为子集$j$,

则$j$加入前的所有方案的最小值$=f[state-j]$,

加入$j$则需要加上子集$j$的兼容性$g[j]$,

那么加入$j$前$state$转移到加入$j$后的$state$:

$f[state] = f[state-j] + g[j]$

方法一 DFS剪枝TLE

class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        if k==len(nums):
            return 0
        cnt = collections.Counter(nums)
        maxi = max(cnt[x] for x in cnt)
        if maxi>k:
            return -1
        n = len(nums)
        nums.sort()
        self.res = float('inf')
        tmp = collections.defaultdict(list)
        lens = n//k
        for i in range(k):
            tmp[k]=[]
        vis = set()
        def check(path):
            sums = 0
            for x in path:
                if path[x]:
                    sums+=max(path[x])-min(path[x])
            return sums>self.res
        def dfs(path,resi,cntk):
            if resi==0:
                self.res = min(self.res,sum(max(path[i])-min(path[i]) for i in range(k)))
                return
            if check(path):
                return
            for i in range(n):
                if i not in vis and nums[i] not in path[cntk]:
                    path[cntk].append(nums[i])
                    vis.add(i)
                    dfs(path,resi-1,cntk+1) if len(path[cntk])==lens else dfs(path,resi-1,cntk)
                    path[cntk].pop()
                    vis.remove(i)
        dfs(tmp,n,0)
        return self.res

方法二状压dp

class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if k==n:
            return 0
        if k==1:
            cnt = collections.Counter(nums)
            return max(nums)-min(nums) if all(cnt[x]==1 for x in cnt) else -1
        g = [-1]*(1<<n)#状态i的兼容性数组
        f = [float('inf')]*(1<<n)#状态i的最小兼容性和
        f[0]=0
        def cnt1(x):
            res = 0
            while x:
                x=x&(x-1)
                res+=1
            return res
        for i in range(1,1<<n):
            if cnt1(i)!=n//k:
                continue
            d = []
            for j in range(n):
                if (i>>j) & 1:
                    d.append(nums[j])
            flag = False
            d.sort()
            for j in range(len(d)-1):
                if d[j]==d[j+1]:
                    flag = True
                    break
            if flag:#如果状态i下 子集d中有相同的两个数
                continue
            g[i] = d[-1]-d[0]#状态i下 兼容性g[i]
        for i in range(1,1<<n):#枚举i的所有子集j O(3^n)
            if cnt1(i)%(n//k):continue
            j = i
            while j>0:
                if g[j]!=-1:
                    f[i] = min(f[i],f[i-j]+g[j])
                j = (j-1)&i
        res = f[(1<<n)-1]
        return res if res!=float('inf') else -1

leetcode 1655 分配重复整数

leetcode 1723 完成所有工作的最短时间

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的工作时间是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化。

返回分配方案中尽可能最小的最大工作时间。

示例：

输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。

数据范围

1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 107

思路

首先创建$sum[state]$数组表示每种状态下的用时之和

状态表示

$f[k][state] =$ 给第$k+1$组分配时分配状态为$state$的所有组用时中最大值的最小值
状态转移

给第$k+1$组分配时,对其所有子集进行遍历,
$f[k][state] = min(max(f[k-1][state-substate],sum[substate]))\ for\ all\ substate$

class Solution {
public:
    int f[13][1<<13];
    int sum[1<<13];
    int last_zero(int x)
    {
        int last1 = x-(x&(x-1));
        int res = 0;
        while(last1)
        {
            last1>>=1;
            res++;
        }
        return res-1;
    }
    int minimumTimeRequired(vector<int>& jobs, int k) {
        memset(f,0,sizeof f);
        memset(sum,0,sizeof sum);
        int n = jobs.size();
        for(int i=1;i<(1<<n);i++)
        {
            int x = last_zero(i);//__builtin_ctz(i);
            int y = i - (1<<x);
            sum[i] = sum[y] + jobs[x];
        }
        // 初始化第一组的工作时间
        for(int i=0;i<(1<<n);i++)
        {
            f[0][i] = sum[i];
        }
        // 从第二组到第k组的工作时间
        for(int i = 1;i < k; i++)
            for(int cur = 0;cur < (1<<n); cur++)
            {
                int mini = INT_MAX;
                for(int subset = cur;subset;subset = cur&(subset-1))
                {
                    mini = min(mini,max(f[i-1][cur - subset],sum[subset]));
                }
                f[i][cur] = mini;
            }
        return f[k-1][(1<<n)-1];
    }
};

LCP 13 寻宝

我们得到了一副藏宝图，藏宝图显示，在一个迷宫中存在着未被世人发现的宝藏。

迷宫是一个二维矩阵，用一个字符串数组表示。它标识了唯一的入口（用 'S' 表示），和唯一的宝藏地点（用 'T' 表示）。但是，宝藏被一些隐蔽的机关保护了起来。在地图上有若干个机关点（用 'M' 表示），只有所有机关均被触发，才可以拿到宝藏。

要保持机关的触发，需要把一个重石放在上面。迷宫中有若干个石堆（用 'O' 表示），每个石堆都有无限个足够触发机关的重石。但是由于石头太重，我们一次只能搬一个石头到指定地点。

迷宫中同样有一些墙壁（用 '#' 表示），我们不能走入墙壁。剩余的都是可随意通行的点（用 '.' 表示）。石堆、机关、起点和终点（无论是否能拿到宝藏）也是可以通行的。

我们每步可以选择向上/向下/向左/向右移动一格，并且不能移出迷宫。搬起石头和放下石头不算步数。那么，从起点开始，我们最少需要多少步才能最后拿到宝藏呢？如果无法拿到宝藏，返回 -1 。

示例：

输入： ["S#O", "M..", "M.T"]

输出：16

解释：最优路线为： S->O, cost = 4, 去搬石头 O->第二行的M, cost = 3, M机关触发 第二行的M->O, cost = 3, 我们需要继续回去 O 搬石头。 O->第三行的M, cost = 4, 此时所有机关均触发 第三行的M->T, cost = 2，去T点拿宝藏。 总步数为16。

限制：

1 <= maze.length <= 100
1 <= maze[i].length <= 100
maze[i].length == maze[j].length
S 和 T 有且只有一个
0 <= M的数量 <= 16
0 <= O的数量 <= 40，题目保证当迷宫中存在 M 时，一定存在至少一个 O 。

思路

$maze$中，每个位置到地图上任意的其他位置的距离是不会变化的，因此使用BFS算法计算并保存（题解中实际上只计算了起点到任意点的距离以及每个机关i到任意点的距离）
使用$dist$数组，记录机关i到机关$j$的最短距离，从机关i到机关j需要经过一次石头，因此每计算一个$dist[i][j]$都需要遍历所有的石头
状态压缩的$dp$，利用二进制的$mask$来保存当前的状态，$dp[mask][j]$表示当前处于第$j$个机关，总的触发状态为$mask$所需要的最短路径。由于有$n_b$个机关，每个机关都有访问和未访问两种状态，共有$2^{nb}$个状态，因此需要$(1<<nb)*nb$的空间开销
最后，所有状态都被访问以后，还应当从最后一个状态$j$出发，前往终点，最终比较得到最短的距离

class Solution:
    def minimalSteps(self, maze: List[str]) -> int:
        dirs = [(-1,0),(1,0),(0,-1),(0,1)]
        m,n = len(maze),len(maze[0])
        keys,locks = [],[]
        for i in range(m):
            for j in range(n):
                if maze[i][j]=='M':#机关
                    locks.append([i,j])
                if maze[i][j]=='O':#石堆
                    keys.append([i,j])
                if maze[i][j]=='S':
                    si = i
                    sj = j
                if maze[i][j]=='T':
                    ti = i
                    tj = j
        locks = [[si,sj]] + locks#把起点也作为锁 错因:start不是0 0而是si,sj
        # print(locks)
        # print(keys)
        nk,nl = len(keys),len(locks)
        tdist = [[float('inf')] * n for _ in range(m)]#终点和各点距离
        kdist = [[[float('inf')] * n for _ in range(m)] for _ in range(nk)]#石堆和各点距离
        # print(kdist)
        def bfs(i,j,dist):
            q = collections.deque([])
            visit = [[False] * n for _ in range(m)]
            q.append((i,j))
            dist[i][j] = 0
            visit[i][j] = True
            while q:
                x,y = q.popleft()
                for dx,dy in dirs:
                    nx,ny = x+dx,y+dy
                    if nx<0 or nx>=m or ny<0 or ny>=n or visit[nx][ny] or maze[nx][ny]=='#':
                        continue
                    dist[nx][ny] = dist[x][y]+1
                    visit[nx][ny] = True
                    q.append((nx,ny))
        for i in range(nk):
            bfs(keys[i][0],keys[i][1],kdist[i])
        bfs(ti,tj,tdist)

        print(kdist)
        ldist = [[float('inf')] * nl for _ in range(nl)]
        for i in range(nl):
            i1,j1 = locks[i][0],locks[i][1]#第i把锁的坐标
            for j in range(nl):
                if i==j: continue
                i2,j2 = locks[j][0],locks[j][1]#第j把锁的坐标
                for k in range(nk):#遍历k把钥匙与第i把及与第j把锁的距离的和的最小值
                    ldist[i][j] = min(ldist[i][j],kdist[k][i1][j1] + kdist[k][i2][j2])
        dp = [[float('inf')] *(1 << nl) for _ in range(nl)]#nl个锁开与没开的状态
        dp[0][1] = 0#第0把锁也就是起点打开时 初始化为0
        for state in range(1,1<<nl):#对2^nl种 nl个锁开与不开的状态进行遍历
            for cur in range(nl):#对nl个锁进行遍历
                if dp[cur][state]==float('inf'): continue#如果当前锁 
                #下一步要打开的锁
                for i in range(1,nl):
                    # 目标锁已经被打开 所以我们继续看下一把锁
                    if state & (1 << i): continue
                    # 目标锁未被打开 则把目标锁打开 
                    ne = state+(1 << i)#则下一个状态是把目标锁打开
                    #ldist[cur][i]存的是从当前锁 去最近的key拿钥匙再去i开锁的距离
                    dp[i][ne] = min(dp[i][ne],dp[cur][state] + ldist[cur][i])
        # 出发去终点前的状态，应当是处于某一机关处，同时所有机关均已打开。
        # 遍历所有机关的位置，得到最终的结果。
        ans = float('inf')
        for i in range(nl):
            ans = min(ans,dp[i][(1<<nl)-1]+tdist[locks[i][0]][locks[i][1]])
        return ans if ans!=float('inf') else -1

连通类状态压缩动态规划

leetcode 1349 参加考试的最大学生数

给你一个m*n的矩阵 seats表示教室中的座位分布。如果座位是坏的（不可用），就用'#'表示；否则，用'.'表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的一起参加考试且无法作弊的最大学生人数。

学生必须坐在状况良好的座位上。

示例:

输入：seats = [["#",".","#","#",".","#"],
              [".","#","#","#","#","."],
              ["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。

数据范围

seats只包含字符'.'和'#'
m ==seats.length
n ==seats[i].length
1 <= m <= 8
1 <= n <= 8

连通性状压dp

状态表示
$f[i][state]$ 第$i$行学生座位排布集合为$state$

状态转移
$f[i-1][ne]=max(f[i-1][ne],f[i][cur]+cnt1(ne))$

从最后一排往前排座位

遍历前一排的所有合法状态$ne$ 合法条件:$ne$没有相邻两个1 同时有1的位置与’#’不冲突

遍历当前排的所有合法状态$cur$ 合法条件:$cur$的1的相邻位上$ne$没有1

class Solution:
    def maxStudents(self, seats: List[List[str]]) -> int:
        m,n = len(seats),len(seats[0])
        f = [[0]*(1<<n) for _ in range(m+1)]
        a = [0]*m
        def cnt1(state):
            res = 0
            while state:
                state-=state&-state
                res+=1
            return res
        for i in range(m):
            for j in range(n):
                if seats[i][j]=='#':
                    a[i]|=1<<j
        for i in range(m,0,-1):
            # 下一行状态ne
            for ne in range(1<<n):
                if not ne&(ne<<1) and not ne&(ne>>1) and not ne&a[i-1]:
                    # 当前行状态cur
                    for cur in range(1<<n):
                        if not ne&(cur<<1) and not ne&(cur>>1):
                            f[i-1][ne] = max(f[i-1][ne],f[i][cur]+cnt1(ne))
        return max(f[0])

Leopold

https://leopoldacc.github.io/Blogs/Blogs/2020/12/07/%E7%8A%B6%E5%8E%8BDP/

本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Leopold !

动态规划状态压缩

网络流

2020-12-08 数据结构与算法

网络流

贪心

2020-12-07 数据结构与算法

贪心

状压DP

集合类状态压缩动态规划

acwing91 最短Hamilton路径-旅行商问题

leetcode 351 安卓系统手势解锁

leetcode464 我能赢吗-博弈状压

博弈状压dp

leetcode 526 优美的排列

示例:

数据范围

状压dp

答案

leetcode 638 大礼包-7进制状压

示例

数据范围

思路

leetcode 691 贴纸拼词

示例

数据范围

思路

leetcode 698划分为k个相等的子集

示例：

数据范围

状压dp

答案

leetcode 847 访问所有节点的最短路径

示例

数据范围

最短路 二进制状态表示

状压dp

leetcode 935 骑士拨号器-滚动数组状压

示例

数据范围

思路

答案

leetcode 943 最短超级串

示例:

数据范围

状压dp

答案

leetcode 980不同路径Ⅲ

示例:

数据范围

分析

最终答案

leetcode 1125 最小的必要团队

示例

数据范围

思路

答案

leetcode 1178 猜字谜

示例

数据范围

思路

leetcode 1255 得分最高的单词集合

示例

数据范围

思路

答案

leetcode 1434 每个人戴不同帽子的方案数

示例

数据范围

思路

leetcode1542 找出最长的超赞子字符串

示例

数据范围

思路

leetcode 1681 最小不兼容性

示例

数据范围

思路

leetcode 1655 分配重复整数

leetcode 1723 完成所有工作的最短时间

示例：

数据范围

思路

LCP 13 寻宝

示例：

限制：

思路

连通类状态压缩动态规划

最短路二进制状态表示