solve_leetcode/problems/
0651-4-keys-keyboard.rs

1/// f(n) = max(
2///     // A
3///     f(n - 1) + 1,
4///     // Ctrl-V
5///     g(n, 1),
6/// )
7///
8/// f(1) = 1
9/// f(2) = 2
10///
11/// g(i, j) means the last j steps are Ctrl-V (j <= i - 3)
12///
13/// g(i, j) = max(
14///     // Either the previous step is also Ctrl-V
15///     g(i, j + 1),
16///     // or the previous two steps are Ctrl-A + Ctrl-C
17///     f(i - j - 2) * (j + 1)
18/// ) }
19
20pub mod recursion {
21    use std::cmp::max;
22
23    pub fn f(n: usize) -> usize {
24        if n <= 2 {
25            return n;
26        }
27
28        max(f(n - 1) + 1, g(n, 1))
29    }
30
31    fn g(n: usize, j: usize) -> usize {
32        if j > n - 3 {
33            return n - j;
34        }
35
36        max(g(n, j + 1), f(n - j - 2) * (j + 1))
37    }
38
39    pub use f as solve;
40}
41
42pub mod dp {
43    use std::cmp::max;
44
45    pub fn solve(n: usize) -> usize {
46        let mut dpt = vec![0; n + 1];
47
48        if n >= 1 {
49            dpt[1] = 1;
50        }
51        if n >= 2 {
52            dpt[2] = 2;
53        }
54        if n >= 3 {
55            dpt[3] = 3;
56        }
57
58        if n >= 4 {
59            for i in 4..=n {
60                let v1 = dpt[i - 1] + 1;
61
62                let v2 = {
63                    let mut prev = 2usize; // j = i - 2
64                    for j in (1..=(i - 3)).rev() {
65                        // println!("prev = {}, j = {}, dpt = {:?}", prev, j, dpt);
66                        prev = max(prev, dpt[i - j - 2] * (j + 1));
67                    }
68
69                    prev
70                };
71
72                // println!("i = {}, v1 = {}, v2 = {}, dpt = {:?}", i, v1, v2, dpt);
73
74                dpt[i] = max(v1, v2);
75            }
76        }
77
78        dpt[n]
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    #[test]
85    fn problem_0651() {
86        for solve in [
87            //
88            super::recursion::solve,
89            super::dp::solve,
90        ] {
91            assert_eq!(solve(0), 0);
92            assert_eq!(solve(1), 1);
93            assert_eq!(solve(2), 2);
94            assert_eq!(solve(3), 3);
95            assert_eq!(solve(4), 4);
96            assert_eq!(solve(5), 5);
97            assert_eq!(solve(6), 6);
98            assert_eq!(solve(7), 9);
99            assert_eq!(solve(8), 12);
100            assert_eq!(solve(9), 16);
101            assert_eq!(solve(10), 20);
102            assert_eq!(solve(11), 27);
103            assert_eq!(solve(12), 36);
104            assert_eq!(solve(13), 48);
105            assert_eq!(solve(14), 64);
106            assert_eq!(solve(15), 81);
107            assert_eq!(solve(16), 108);
108            assert_eq!(solve(17), 144);
109            assert_eq!(solve(18), 192);
110            assert_eq!(solve(19), 256);
111            assert_eq!(solve(20), 324);
112            assert_eq!(solve(21), 432);
113            assert_eq!(solve(22), 576);
114            assert_eq!(solve(23), 768);
115            assert_eq!(solve(24), 1024);
116            assert_eq!(solve(25), 1296);
117            assert_eq!(solve(26), 1728);
118            assert_eq!(solve(27), 2304);
119            assert_eq!(solve(28), 3072);
120            assert_eq!(solve(29), 4096);
121            assert_eq!(solve(30), 5184);
122        }
123    }
124}
solve_leetcode/problems/0651-4-keys-keyboard.rs

solve_leetcode/problems/
0651-4-keys-keyboard.rs
