状压 DP：从记忆化搜索到递推【力扣周赛 397】
-花月本无常-:
这场风评应该又会争议比较大。第四题如果直接按照题目公式进行状压DP，需要first，last和mask这些状态，总复杂度达到2^n * n^3，但可以发现一个排列任意平移分数都不会变，因此第一位一定能填0，first是个多余状态，总复杂度就是2^n * n^2。这个题很可能考的就是这点，而有意把没发现这点的做法卡掉。美国站通过率看难度分确实是踩线2600。
【回复】回复 @喵依米 :2^n * n^3而且常数不大（因为肯定有很多垃圾状态），对于n=14是应该通过的，但实际上是过不了的，一般出现这种情况，评价就会很负面。但这个题考的就是怎么去掉一个状态，这需要细心观察与思考，所以这么做也可理解。
【回复】只要题意清楚，没误导人，就不能说有争议吧。
清風逐尘乀:
我觉得T4没讲清楚为什么第一位一定可以填0。因为题目给的nums数组是固定的，我没法理解up主说的旋转是什么意思。
【回复】这里说的是 perm 的旋转（循环移位）不改变相邻元素，原来是相邻的，循环移位后还是相邻的，所以计算的分数是不变的。具体可以看我题解中的分析。
【回复】【0,1,2,3】 【1,2,3,0】 【2,3,0,1】 【3,0,1,2】 这四个排列的分数肯定一样，你可以带入公式看看[滑稽] n取其他值，其他形式的排列也可以这样类推。
【回复】我理解他答案返回的数组取得是原下标，只要顺序一样，得出的答案都是一致的
堝媆戜:
灵神好，就是状压dp的dp方程可以定义f【i】【j】为当前走过所有点的集合i,当前在的点为j吗，这样是不是将if(!(i>>j&1)改成 if(i>>j&1)
【回复】回复 @灵茶山艾府 : 好的谢谢灵神
【回复】回复 @堝媆戜 :也可以这样定义，具体可以做做我的 DP 题单中的状压 DP 题目。
噬神s:
请问T4为什么记忆化搜索的时间为O(n*2^n),如果是这样，leetcode题里的https://leetcode.cn/problems/number-of-squareful-arrays/，为什么按照您的写法会把我卡住时间复杂度
class Solution {
public:
int ans=0;
int numSquarefulPerms(vector<int>& nums) {
int n = nums.size();
dfs(0, -1, nums);
unordered_map<int, int> map;
for(auto& i:nums)
{
map【i】++;
}
for(auto& item:map)
{
for(int i=1;i<=item.second;i++)
{
ans /= i;
}
}
return ans;
}
void dfs(int mask,int j,vector<int>& nums)
{
if (mask == (1 << nums.size())-1)
{
ans++;
return;
}
for(int i=0;i<nums.size();i++)
{
if (mask>>i&1) continue;
if(j==-1 || check(nums【i】 + nums【j】))
{
dfs(mask | (1 << i), i, nums);
}
}
}
static bool check(int number)
{
int s = static_cast<int>(sqrt(number));
return s*s==number;
}
};
dadadalizia:
T4暴力混过了，但是我知道考点肯定不是这个，做之前觉得一定超时[笑哭]。
【回复】数据假了，经典赛后补数据，你现在再交一发试试
【回复】....经典赛后卡数据，前两天洗碗的dfs今天又过不去了，不知道其他语言行不行
我的意思是超级跳投:
那假如我纯彩笔，以后的dp是不是都可以用记忆化搜索写，就不推导什么转移方程了[笑哭]
【回复】回复 @灵茶山艾府 :懂了，那我先用记忆化搜索转向dp训练一下思维方式[笑哭]
【回复】回复 @我的意思是超级跳投 :记忆化搜索可以解决大部分 DP 题目。更难一些的需要用到数据结构优化的只能写递推。
饭碗碗的皮皮然:
好消息，卡掉了n^3 * 2^n次的做法，坏消息，没卡掉带分数减枝回溯暴力(甚至不需要发现左移不变的性质，直接暴搜带减枝都是乱过)
【回复】回复 @喵依米 :不否认你的说法，看这题的提示官方出题应该是希望状压的解法 不然不会给到7分
【回复】好的剪枝为什么要卡掉，不也是优秀的解法
努力自省:
灵神，这里一直没想通，求解答[打call][打call][打call]。为什么判断 dfs(memo, a, s | 1 << k, k, n) + abs(j - a【k】) == final_res呢，我理解的是递归末尾为k的状态时，已经把 abs(j - a【k】)算入了呀，这样不是重复计算么
【回复】回复 @努力自省 :abs 是加在 dfs(s,j) 中的，并不在 dfs(s|1<<k,k) 中
大大逐月:
第三题接雨水了[藏狐]，是没，我是新开一个数组用来存它左上的最小值，然后用当前值去减，测了四下，第一行和第一列没有单独考虑[笑哭]
realLei-:
想问下T3循环内部：
mn = min(f【i + 1】【j】, f【i】【j + 1】)
ans = max(ans, x - mn)
f【i + 1】【j + 1】 = min(mn, x)
不是很懂，这用到了二维前缀和 f【i + 1】【j】 + f【i】【j+1】 - f【i】【j】 + a【i】【j】 吗？看起来没有求和....
mn = min(f【i + 1】【j】, f【i】【j + 1】) 只是获得最小值
【回复】Hi，这里思路和二维前缀和是类似的，那么转移方程也是类似的。
