状压dp|dfs|dijk

lc2816

优雅递归😋

class Solution {
public:
int t=0;
ListNode* doubleIt(ListNode* head)
{
auto dfs=[&](this auto&& dfs,ListNode* node)->ListNode*
{
if(!node) return nullptr;
dfs(node->next);

//先递归到结尾
//handle
int v=node->val;
node->val=v*2%10+t;
t=v*2/10;
return node;
};
dfs(head);
if(t)
return new ListNode(1,head);
return head;
}
};

lc2486

暴力dfs

DFS找从起点到终点的最小掉血路径

记下来最少掉多少血

若这个数比初始健康值小且能走到终点，就返回true

必然 充分的地推验证过程 实现剪枝

class Solution {
public:
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

bool findSafeWalk(vector<vector<int>>& g, int h) {
int m=g.size(),n=g[0].size();
vector<vector<int>> mem(m, vector<int>(n, INT_MAX));

auto dfs = [&](this auto&& dfs, int x, int y, int c){
if(x<0||x>=m||y<0||y>=n||c>=mem[x][y]) return;
mem[x][y] = c;
if(x==m-1&&y==n-1) return;
for(int k=0;k<4;k++){
int a=x+dx[k],b=y+dy[k];
dfs(a,b,c + (a>=0&&a<m&&b>=0&&b<n?g[a][b]:0));
}
};

dfs(0,0,g[0][0]);
return mem[m-1][n-1] < h && mem[m-1][n-1] != INT_MAX;
}
};

dijk优化

对于"大的同时小一点"

大的加给小的，返回当前大的

lc1723

预处理 抽象出jobs子集枚举 状态 +状压dp

二进制表示任务组合，先算所有组合的总耗时，再用动态规划分k个工人：

每个工人分配部分任务，取“当前工人任务耗时”和“之前工人最大耗时”的较大值

最终找k个工人干完所有任务的最小最大耗时

class Solution {

public:
int minimumTimeRequired(vector<int>& jobs, int k)

{
int n = jobs.size();
vector<int> tot(1 << n, 0);
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) == 0) continue;
int left = (i - (1 << j));
tot[i] = tot[left] + jobs[j];
break;
}
}

vector<vector<int>> dp(k, vector<int>(1 << n, -1));
for (int i = 0; i < (1 << n); i++)
dp[0][i] = tot[i];

for (int j = 1; j < k; j++) {
for (int i = 0; i < (1 << n); i++) {
int minv = INT_MAX;
for (int s = i; s; s = (s - 1) & i)

{

// 枚举 i 的全部子集
int left = i - s;
int val = max(dp[j-1][left], tot[s]);
minv = min(minv, val);
}
dp[j][i] = minv;
}
}
returndp[k-1][(1<<n)-1];
}
};