题目描述
| f1-记忆化搜索+轮廓线状态压缩 |
基本分析
- 轮廓线状态压缩的场景？在一个二维矩阵上进行动态规划+数据规模不大+可以通过当前位置与其左上方位置+左侧位置计算转移方程
- 为什么存n个状态而不是相关的2个状态？只存2个会丢状态，新的0找不到了；存n个可以递推出
- 具体怎么计算得分？新加人产生的分可分为：填进去的人的分+上侧相邻导致的贡献+左侧相邻导致的贡献；规定贡献的计算方法是下侧和右侧计算，这样可以按照行优先的顺序枚举位置，进行状态转移
- 在dp前进行哪些预处理？
- （1）对每个状态mask，存他对应的0-n-1的每一位值。这里的要求是最高位对应0，最低位对应n-1
- （2）对每个mask，存截断第0位，同时再末尾分别追加0,1,2后的值
- dp时候有哪些细节？
- （1）有可能计算出的pos位置在第一列，这个时候不存在左侧影响，对应的add_l是0
- （2）有可能计算出的pos位置在第一行，这个时候不存在上侧影响，可以假设存在虚拟的第0行，该行状态都是0
- dfs怎么写？
- dfs参数：位置pos，当前轮廓线bl，剩余内向ni，剩余外向nx
- 结束条件：位置达到边界或者人分配完，都可以结束返回0
- 枚举情况：
- （1）pos处不放人，这个时候可以拿到不放对应的best值
- （2）放内向的人，取max（best，内向人得分 + 上侧影响 + 左侧影响 + 后续情况）
- （3) 放外向的人，取max（best，外向人得分 + 上侧影响 + 左侧影响 + 后续情况）
- 返回情况：返回当前状态结果best
代码
class Solution:
def getMaxGridHappiness(self, m: int, n: int, ni: int, ne: int) -> int:
def calc(x, y):
if x==0 or y==0:
return 0
if x==1 and y==1:
return -60
if x==2 and y==2:
return 40
return -10
n3 = 3**n
high = n3//3
# 存数字对应的3进制
mask_span = dict()
# 存数字截断高位，低位+0,1,2后的值
truncate = dict()
for mask in range(n3):
mask_temp = mask
bits = list()
for i in range(n):
bits.append(mask_temp % 3)
mask_temp //= 3
mask_span[mask] = bits[::-1]
truncate[mask] = [mask % high * 3, mask % high * 3+1, mask % high * 3+2]
@lru_cache(None)
def dfs(pos, bl, ni, ne):
if pos == m*n or ni+ne==0:
return 0
x, y = divmod(pos, n)
# 不放
best = dfs(pos+1, truncate[bl][0], ni, ne)
# 放1-内向
if ni > 0:
add_t = calc(1, mask_span[bl][0])
add_l = calc(1, mask_span[bl][n-1]) if y > 0 else 0
best = max(best, 120 + add_t + add_l + dfs(pos+1, truncate[bl][1], ni-1, ne))
# 放2-外向
if ne > 0:
add_t = calc(2, mask_span[bl][0])
add_l = calc(2, mask_span[bl][n-1]) if y > 0 else 0
best = max(best, 40 + add_t + add_l + dfs(pos+1, truncate[bl][2], ni, ne-1))
return best
return dfs(0, 0, ni, ne)
复杂度
时间：
- \(预处理部分计算mask的3进制表示以及mask0, mask1, mask2的复杂度是O(n\cdot 3^n)\)
- \(记忆化搜索部分状态总数是O(m \cdot n \cdot ni\cdot ne \cdot 3^n), 转移需要枚举3=O（1）个状态，转移时间复杂度是O(1)\)
空间： - \(预处理mask的3进制表示是O(n*3^n)\)
- \(预处理mask的截断操作是O(3^n)\)
- \(记忆化搜索的空间为状态总数O(m \cdot n \cdot ni\cdot ne \cdot 3^n)\)
总结
这是第一次碰到轮廓线dp的题。
和之前的相比，（1）选择多了，不再是选和不选，而是有3种可能；（2）用3进制表达相比二进制，没有位运算那么方便了，这里需要预处理mask的3进制每一位的表达；也需要预处理转移后状态的表达；（3）写转移的时候因为是在记忆化搜索里面，所以可以把后面结果当做已知，反而会比较简单。
遇到当前选择会影响之前值的情况，这里是定义了一个规则（由下和右）的位置进行补偿，只要考虑怎么计算这个值。