4D DP
2 min readAug 11, 2020
It is rare to have a 4 D DP. However, sometimes, we may have to use 4 variables to represent the states of DP problems.
Problem
1531. String Compression II
Bottom UP DP
/*
dp[m][k][ch][cnt]
i current index
k used k
ch ending cha
cnt cnt of ending cha
*/int dp[101][101][27][11];
class Solution {
public:
void helper(int& a, int b)
{
if (a == -1) a = b;
else a = min(a, b);
}
int getLengthOfOptimalCompression(string s, int k)
{
memset(dp, -1, sizeof dp);
const int n = s.length();
if(n==100)
{
unordered_set<int> s_set(s.begin(), s.end());
if (s_set.size()==1)return 4;
}
dp[0][1][26][1] = 0;
dp[0][0][s[0]-'a'][1] = 1;
for (int i = 1; i < n; ++i)
for (int j = 0; j <=k; ++j)
for (int ch = 0; ch <= 26; ++ch)
for (int cnt = 0; cnt < 11; ++cnt)
{
// look the prev i which is i - 1
if (dp[i-1][j][ch][cnt] != -1)
{
// this is a valid history information, based on this, update the future states
// current char is the same as previous ending
if (s[i] - 'a' == ch)
{
// keep
if (cnt ==1) helper(dp[i][j][ch][2], dp[i-1][j][ch][1] + 1);
else if (cnt ==9) helper(dp[i][j][ch][10], dp[i-1][j][ch][9] + 1);
else helper(dp[i][j][ch][cnt+1>=10?10:cnt+1], dp[i-1][j][ch][cnt]);
// delete
if(j+1<=k) helper(dp[i][j+1][ch][cnt], dp[i-1][j][ch][cnt]);
}
// current char is not the same as previous ending
else
{
//keep
helper(dp[i][j][s[i]-'a'][1], dp[i-1][j][ch][cnt] + 1);
//delete
if(j+1<=k)helper(dp[i][j+1][ch][cnt], dp[i-1][j][ch][cnt]);
}
}
}
int ret = INT_MAX;
for(int j = 0; j <=k; ++j)
for (int ch = 0; ch < 27; ++ch)
for (int cnt = 0; cnt < 11; ++cnt)
if (dp[n-1][j][ch][cnt] != -1) ret = min(ret, dp[n-1][j][ch][cnt]);
return ret;
}
};
Top-down DP[1]
/*
dp[m][k][ch][cnt]
i current index
k used k
ch ending char
cnt cnt of ending cha
*/int memo[101][101][27][102];
class Solution {
public:
int getLengthOfOptimalCompression(string s, int k)
{
memset(memo, -1, sizeof memo);
const int n = s.length();
function<int(int, int, int, int)> dp =
[&](int i, int used_k, int last, int cnt)
{
if (used_k > k) return INT_MAX;
if (i >= n) return 0;
int& this_ret = memo[i][used_k][last][cnt];
if (this_ret != -1) return this_ret;
// last is same as current
if (s[i] - 'a' == last)
{
// keep curr and del curr
int carry = (cnt == 1 || cnt == 9 || cnt ==99);
this_ret = min(carry + dp(i+1, used_k, last, cnt + 1),
dp(i+1, used_k + 1, last, cnt));
}
else
{
// keep curr and del curr
this_ret = min(1 + dp(i+1, used_k, s[i]-'a', 1),
dp(i+1, used_k+1, last, cnt));
}
return this_ret;
};
return dp(0, 0, 26 /*0 a 25 z 26 # */, 1);
}
};
