1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
struct Solution;
impl Solution {
pub fn get_length_of_optimal_compression(s: String, k: i32) -> i32 {
#[inline]
fn len_of_chars(n: i32) -> i32 {
match n {
1 => 1,
2..=9 => 2,
10..=99 => 3,
_ => 4,
}
}
fn dfs(v: &[u8], dp: &mut [[i32; 101]; 101], left: i32, k_s: i32) -> i32 {
let mut k = k_s;
if v.len() as i32 - left <= k {
return 0;
}
if dp[left as usize][k as usize] >= 0 {
return dp[left as usize][k as usize];
}
let mut ans = if k > 0 {
dfs(v, dp, left + 1, k - 1)
} else {
std::i32::MAX
};
let mut c = 1;
for i in left + 1..=v.len() as i32 {
ans = ans.min(dfs(v, dp, i, k) + len_of_chars(c));
if i == v.len() as i32 {
break;
}
if v[i as usize] == v[left as usize] {
c += 1;
} else {
k -= 1;
if k < 0 {
break;
}
}
}
dp[left as usize][k_s as usize] = ans;
ans
}
let mut dp = [[-1; 101]; 101];
let v = s.as_bytes();
dfs(v, &mut dp, 0, k)
}
}
fn main() {
let s = String::from("aaabcccd");
print!("{}", Solution::get_length_of_optimal_compression(s, 2));
}
|