我记得刚开始进入后端开发时，大家对学历的要求并不那么严格。
那些外包公司，甚至有不少小公司，都更看重的是你的技术能力。只要能写出高质量的代码，问题能解决得干脆利索，学历什么的根本不重要。我的一位大专同学，技术出色，年年升职，根本没受到学历的困扰。
更糟糕的是，一些运维岗位的要求也变得很严格，“统招大专+成人本科都没人要了”这一说法，听得我都有些心虚。照这样发展下去，难道我们这些没有“本”证的程序员，真的就被“学历”挡在门外了吗？
不过，我还是相信一句话：最终决定你职业生涯的，永远是你的能力。如果你技术够硬，根本不怕什么学历限制，继续提升自己的能力，机会总会到来的！
算法题：奇怪的打印机
今天我们来聊聊一道比较有趣的算法题——奇怪的打印机。
题目是这样的：给定一个字符串 s，打印机每次只能打印一个字符，并且打印机能够不断重复打印某个字符，直到用户选择停止。这就有点类似于“重复字符”的问题，但关键在于如何将这个“重复”的过程高效地处理。
这题的目标是找到打印出目标字符串 s 最少需要多少次打印。
举个例子，假设 s = "aaabbb"，我们可以通过三次打印分别打印出：a, b，最后一次是 a、b 连续打印，这样最少的打印次数就是 2 次。
一开始我看到这个题，第一反应是用递归做，结果发现不行。因为递归会把问题拆得太细，导致冗余计算，而且计算量指数级增长，想要优化算法就得好好动动脑筋了。
思路解析
首先要明确一点，这个问题可以看成是一个“区间合并”的问题。为什么这么说呢？我们可以根据相邻字符的重复性来分割问题。比如在 aaabbb 这个例子中，aaa 和 bbb 是两个区间，而我们可以把它们分别处理。
动态规划解法
我的思路是用 动态规划 来解这个问题。为什么呢？因为我们可以从较小的子问题开始逐步求解。
我们设定一个二维数组 dp[i][j]，表示从第 i 个字符到第 j 个字符的最小打印次数。初始化时，单个字符的打印次数就是 1（因为一个字符只需要打印一次）。
接下来，我们需要填充这个 dp 数组。对于每一个区间 [i, j]，我们需要看看怎么从小区间合并成大区间。
具体步骤如下：
对于每个区间 [i, j]，先假设每个字符都独立打印。这样，最坏情况下，打印次数就是dp[i][j] = j - i + 1。然后，我们检查区间内的重复字符。假设区间 s[i] == s[k]，那么区间[i, j]的最小打印次数可以通过将[i, k]和[k+1, j]合并来得到。
代码实现
下面是我写的代码，使用了动态规划的思路：
public class StrangePrinter {
public int strangePrinter(String s) {
int n = s.length();
// dp[i][j]表示从i到j最少的打印次数
int[][] dp = new int[n][n];
// 初始化：单个字符的区间
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 动态规划：计算从i到j的最少打印次数
for (int len = 2; len <= n; len++) { // len是子区间的长度
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = dp[i][j - 1] + 1; // 默认每个字符都独立打印
for (int k = i; k < j; k++) {
// 如果s[k] == s[j]，我们可以合并
if (s[k] == s[j]) {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] - 1);
} else {
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
}
}
}
}
return dp[0][n - 1];
}
public static void main(String[] args) {
StrangePrinter printer = new StrangePrinter();
System.out.println(printer.strangePrinter("aaabbb")); // 输出2
System.out.println(printer.strangePrinter("abcabc")); // 输出3
}
}
这段代码是一个标准的动态规划解法，时间复杂度大约是 O(n^3)，看起来有点高，但对于大多数常见的字符串长度来说，这个时间复杂度应该能接受。
优化
当然，如果我们想要更高效一点，可以通过记忆化搜索来减少一些冗余计算。但从目前的动态规划实现来看，已经算是一个较为合适的解法了。
总结来说，编程不仅仅是完成任务，更是通过不断优化，提升解决问题的效率和质量。就像我们在这道题中不断精细化每一步一样，在工作中，程序员的价值也往往体现在“看似不起眼但却非常高效”的优化中。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
