状态机dp

lc351

memo+回溯,状态标记+对称性优化

统计手机九宫格手势密码中长度在 [m,n] 范围内的有效模式总数

class Solution {
public:
bool st[9];
int cnt;
int ans;
int c_num;
int n1[16] = {0, 0, 0, 1, 2, 2, 2, 3, 5, 6, 6, 6, 7, 8, 8, 8};
int n2[16] = {2, 8, 6, 7, 0, 6, 8, 5, 3, 0, 8, 2, 1, 2, 0, 6};
int n3[16] = {1, 4, 3, 4, 1, 4, 5, 4, 4, 3, 7, 4, 4, 5, 4, 7};
bool check(int u, int i) {

if (st[i]) return false;
for (int j = 0; j < 16; j ++) {
if (u == n1[j] && i == n2[j] && !st[n3[j]]) return false;
}
return true;
}

void dfs(int u, int m, int n) {
st[u] = true;
if (c_num >= m && c_num <= n) ans ++;
for (int i = 0; i < 9; i ++) {
if (check(u, i)) {
c_num += 1;
dfs(i, m, n);
c_num -= 1;
}
}
st[u] = false;
}

int numberOfPatterns(int m, int n) {
memset(st, false, sizeof st);
if (n == 0) return 0;
if (n == 1) return 9;
cnt = 1;
c_num = 1;
int res = 0;
dfs(0, m, n);
res += ans * 4;
ans = 0;
dfs(1, m, n);
res += ans * 4;
ans = 0;
dfs(4, m, n);
res += ans;
return res;
}
};

lc1852

hash滑窗

vector<int> distinctNumbers(vector<int>& nums, int k)
{
int n=nums.size();
unordered_map<int,int> hash;
for(int i=0;i<k;i++)
{
hash[nums[i]]++;
}
vector<int> ret(n-k+1);
ret[0]=hash.size();
for(int i=1;i<n-k+1;i++)
{
int l=nums[i-1];
int r=nums[i+k-1];
if(--hash[l]==0)
hash.erase(l);
++hash[r];
ret[i]=hash.size();
}
return ret;
}
};

lc3573

用三个二维数组记录每天、至多k+1笔交易下的多仓、做空仓、空仓利润

遍历价格更新状态后取最终k+1笔交易空仓的最大利润

class Solution {

typedef long long ll;

public:

long long maximumProfit(vector<int>& prices, int k)

{

int n = prices.size();

const ll INF = LLONG_MIN / 2;

// f[i][j]: 第i天，j次交易后 多仓（买入持有）的最大利润

// g[i][j]: 第i天，j次交易后 做空仓（卖出待买回）的最大利润

// h[i][j]: 第i天，j次交易后 空仓的最大利润

vector<vector<long long>> f(n + 1, vector<ll>(k + 2, INF));

auto g=f;

auto h=f;

// 初始化：第0天，空仓利润为0

for (int j = 1; j <= k + 1; j++)

h[0][j] = 0;

for (int i = 0; i < n; i++) {

int p = prices[i];

for (int j = 1; j <= k + 1; j++) {

// 空仓状态更新：延续空仓 / 多仓平仓 / 做空仓平仓

h[i + 1][j] = max({h[i][j], f[i][j] + p, g[i][j] - p});

// 多仓状态更新：延续多仓 / 前一次空仓开多

f[i + 1][j] = max(f[i][j], h[i][j - 1] - p);

// 做空仓状态更新：延续做空仓 / 前一次空仓开空

g[i + 1][j] = max(g[i][j], h[i][j - 1] + p);

}

}

return h[n][k + 1];

}

};

lc188

三维 状态机dp

“买/卖状态数组”记录每天最多k次交易后的持仓/空仓利润，先优化k的上限，再遍历价格更新状态，最后取空仓的最大利润

＆看题解学到了斜率优化dpദ്ദി˶˃ ᵕ ˂ )✧！

class Solution {
public:
int maxProfit(int k, vector<int>& prices)
{
int n=prices.size();
//题目 给的 k 可能过大
k=min(k,n/2); //处理一下，优化空间

vector<vector<int>> f(n,vector<int>(k+1,-0x3f3f3f3f));
auto g=f;//卖出

g[0][0]=0;//sale
f[0][0]=-prices[0];//buy

for(int i=1;i<n;i++)
{
for(int j=0;j<=k;j++)
{
f[i][j]=max(f[i-1][j],g[i-1][j]-prices[i]);
g[i][j]=g[i-1][j];
if(j-1>=0)
g[i][j]=max(g[i-1][j],f[i-1][j-1]+prices[i]);
}
}
int ret=0;
for(int j=0;j<=k;j++)
{
ret=max(ret,g[n-1][j]);
}
return ret;
}
};