老程序员回炉补基础（五）：经典算法——背包、LCS、N皇后、汉诺塔与更多
这一章是我的"算法练兵场"。从递归入门的汉诺塔和阶乘，到动态规划的背包和LCS，再到回溯的N皇后，每一种算法思想都让我对"如何把现实问题抽象为数学模型"有了更深的理解。
一、递归入门：阶乘与汉诺塔
阶乘
学习时间：2023年9月27日
publicclassfactorial{publiclongcfactorial(longn){if(n==0){return1;}returnn*cfactorial(n-1);}}最简单的递归。n! = n × (n-1)!，边界条件是 0! = 1。
递归三要素：
- 递归体：
n * cfactorial(n - 1) - 终止条件：
n == 0 - 返回值：每次递归向终止条件逼近（n 不断减小）
汉诺塔
学习时间：2023年9月26日
publicclasshtower{publicvoidf(intn,Stringfrom,Stringmid,Stringto){if(n==1){System.out.println(n+":"+from+"->"+to);}else{f(n-1,from,to,mid);// 上面n-1个盘子从A移到BSystem.out.println(n+":"+from+"->"+to);// 最大的盘子从A移到Cf(n-1,mid,from,to);// n-1个盘子从B移到C}}}汉诺塔是理解递归最好的例子。3个盘子：
f(3, A, B, C): f(2, A, C, B) → 把上面2个从A移到B（借C） 移动盘子3: A→C → 把最大的从A移到C f(2, B, A, C) → 把2个从B移到C（借A）关键洞察：不管有多少个盘子，问题都可以分解为三步——把上面的移走、移最底下的、把上面的移回来。这就是分治的思想。
二、动态规划：0-1背包问题
学习时间：2023年10月7日
物品定义
publicclassStuff{privatedoubleweigth;// 重量privatedoublevalue;// 价值privateintnumber;// 编号publicStuff(intnumber,doubleweigth,doublevalue){this.number=number;this.value=value;this.weigth=weigth;}}核心算法
publicclassKnapsack{/** * 0-1 背包问题 * @param list 物品列表 * @param weigth 背包容量 * @return 动态规划表 c[i][w] 表示前i个物品、容量为w时的最大价值 */publicint[][]f(List<Stuff>list,intweigth){intc[][]=newint[list.size()+1][weigth+1];for(inti=1;i<=list.size();i++){c[i][0]=0;for(intw=1;w<=weigth;w++){Stuffobj=list.get(i-1);if(obj.getWeigth()<=w){if(obj.getValue()+c[i-1][(int)(w-obj.getWeigth())]>c[i-1][w]){c[i][w]=(int)(obj.getValue()+c[i-1][(int)(w-obj.getWeigth())]);}else{c[i][w]=c[i-1][w];}}else{c[i][w]=c[i-1][w];}}}returnc;}}状态转移方程
c[i][w] = max( c[i-1][w], // 不选第i个物品 value[i] + c[i-1][w - weight[i]] // 选第i个物品 )测试用例
物品：[{编号:1, 重量:3, 价值:4}, {编号:5, 重量:9, 价值:13}, {编号:2, 重量:4, 价值:5}, {编号:3, 重量:7, 价值:10}, {编号:4, 重量:8, 价值:11}] 背包容量：17我的理解
动态规划的核心是找到状态转移方程。背包问题的状态是"考虑前i个物品、容量为w时的最大价值"，每个状态只依赖上一行的状态。
动态规划表（DP Table）是理解算法的关键：
w=0 w=1 w=2 w=3 w=4 ... w=17 i=0 0 0 0 0 0 ... 0 i=1 0 0 0 4 4 ... 4 i=2 0 0 0 4 4 ... 13 ...从最后一行最后一列就能读出最优解。
架构师视角
背包问题的思想在工程中广泛应用：
- 服务器资源分配：有限的CPU/内存，如何分配给多个服务使总收益最大？
- 任务调度：有限时间内，选择哪些任务执行使产出最大？
- 缓存策略：有限的缓存空间，缓存哪些数据使命中率最高？
三、动态规划：最长公共子序列（LCS）
学习时间：2023年9月27日
publicclassLCS{publicvoidf(char[]X,char[]Y,intl[][]){for(inti=1;i<=X.length;i++){for(intj=1;j<=Y.length;j++){if(X[i-1]==Y[j-1]){l[i][j]=l[i-1][j-1]+1;}else{intm=0,n=0;m=l[i-1][j];n=l[i][j-1];if(m<n){l[i][j]=m;// BUG：应该是 n}else{l[i][j]=n;// BUG：应该是 m}}}}}}状态转移方程
if X[i] == Y[j]: l[i][j] = l[i-1][j-1] + 1 else: l[i][j] = max(l[i-1][j], l[i][j-1])一个真实的 Bug
我在这段代码中犯了一个错误：当m < n时，应该取较大值n，但我写成了l[i][j] = m。这意味着当两个字符不匹配时，我取的是较小值而不是较大值。
这个 Bug 不是抄代码会犯的错误——抄代码至少会抄对逻辑。它是理解不够深入时手写代码的典型问题：我记住了要比较，但搞反了取值的方向。
修正后的代码：
if(m<n){l[i][j]=n;// 取较大值}else{l[i][j]=m;// 取较大值}测试
X = {'A','B','C','B','D','A','B'} Y = {'B','D','C','A','B','A'} LCS 长度 = 4（"BCBA" 或 "BDAB"）架构师视角
LCS 的应用场景：
- Git diff：比较两个版本的代码差异，本质是 LCS 问题
- DNA 序列比对：生物信息学中比对基因序列的相似性
- 拼写检查：找到最相似的单词
四、回溯：N皇后问题
学习时间：2023年10月13日
N皇后问题：在 N×N 的棋盘上放置 N 个皇后，使它们互不攻击（不在同一行、同一列、同一对角线上）。
递归解法
privateintn=8;privateintp[];publicvoidNqueue(intk){if(k==n){// 所有皇后都放好了，输出一种解法System.out.println(Arrays.toString(p));return;}for(inti=0;i<n;i++){intj=0;for(;j<k;j++){// 检查是否和已放置的皇后冲突if(p[j]==i||Math.abs(p[j]-i)==Math.abs(k-j)){break;}}if(j==k){// 没有冲突p[k]=i;Nqueue(k+1);// 放下一行的皇后}}}我的理解
这是一个经典的回溯算法。p[k] = i表示第 k 行的皇后放在第 i 列。
冲突检测只需两个条件：
p[j] == i：同一列Math.abs(p[j] - i) == Math.abs(k - j)：同一对角线（行差等于列差）
回溯的思想是：走一步看一步，走不通就退回来换一条路。for循环尝试当前行的每一列，如果某一列不冲突就放下去，递归处理下一行；如果所有列都冲突，递归自然返回，上一行就会尝试下一个位置。
迭代解法
我还写了一个非递归版本wNqueue()，用while循环手动模拟递归的回溯过程：
publicvoidwNqueue(){inti,j,count=1;intpos1[]=newint[n+1];for(i=1;i<=n;i++)pos1[i]=0;j=1;while(j>=1){pos1[j]=pos1[j]+1;while(pos1[j]<=n&&!isplace(pos1,j)){pos1[j]=pos1[j]+1;}if(pos1[j]<=n&&j==n){// 找到一组解System.out.print("第 "+(count++)+":");for(i=1;i<=n;i++)System.out.print(pos1[i]);System.out.println();}if(pos1[j]<=n&&j<n){j=j+1;// 放下一行}else{pos1[j]=0;j=j-1;// 回溯到上一行}}}非递归版本的核心：j是当前行号，pos1[j]是当前尝试的列号。当本行所有列都试过了还不行（pos1[j] > n），就重置当前行并回退到上一行。
8皇后的解
8皇后共有92种不同的放置方案。
五、更多算法练习
最大子段和
Sum.java中包含了最大子段和问题的两种解法：
分治法（O(n log n)）：
intmaxSum(intarray[],intleft,intright){if(left>=right){returnarray[left]>0?array[left]:0;}intmid=(left+right)/2;intleftMax=maxSum(array,left,mid);intrightMax=maxSum(array,mid+1,right);// 跨中点的最大子段和ints0=0,s1=0,lefts=0,rights=0;for(inti=mid;i>left;i--){lefts+=array[i];if(lefts>s0)s0=lefts;}for(inti=mid+1;i<right;i++){rights+=array[i];if(rights>s1)s1=rights;}returnmax(leftMax,rightMax,s0+s1);}Kadane 算法（O(n)，最优解）：
intmaxSum(int[]array){intmax=0,temp=0;for(inti=0;i<array.length;i++){temp+=array[i];if(temp>max)max=temp;if(temp<0)temp=0;// 前缀和为负就丢弃}returnmax;}Kadane 算法是一个经典的贪心/DP混合思路：如果一段子数组的和已经是负数了，那它不可能成为最大子段和的一部分，直接丢弃从头开始。
最大公约数（欧几里得算法）
intgcd(inta,intb){intrem=0;while(b>0){rem=a%b;a=b;b=rem;}returna;}辗转相除法，公元前 300 年欧几里得发明的算法，至今仍在使用。
快速幂
publicdoublepower(doublei,longn){if(n==3)returni*i*i;elseif(n==2)returni*i;elseif(n==1)returni;if(n%2==0){returnpower(i*i,n/2);}else{returnpower(i*i,n/2)*i;}}快速幂将 O(n) 的乘法降到 O(log n)：x^n = (x²)^(n/2)。
页码统计
voidpageNumber(){intpages=99;intnumber[]=newint[10];for(inti=1;i<=pages;i++){intnum=i;do{intrem=num%10;number[rem]++;num=num/10;}while(num>0);}}统计一本书从第1页到第99页，每个数字（0-9）出现了多少次。这是一个简单的数学问题，但对理解数位操作有帮助。
五种算法思想总结
| 算法思想 | 代表问题 | 核心思路 |
|---|---|---|
| 递归 | 汉诺塔、阶乘 | 大问题拆成同类小问题 |
| 分治 | 最大子段和、归并排序 | 分成子问题分别求解再合并 |
| 动态规划 | 0-1背包、LCS | 记录子问题的解避免重复计算 |
| 回溯 | N皇后 | 试探+撤销，走不通就回头 |
| 贪心 | Kadane算法、快速幂 | 每一步选局部最优 |
写在最后：五个月的学习总结
从2023年8月到2024年1月，我用5个月时间补完了这些基础：
| 月份 | 学习内容 |
|---|---|
| 2023.8 | 链表、栈、队列 |
| 2023.9 | 排序算法、递归 |
| 2023.10 | 图、树、经典算法 |
| 2023.11 | 堆排序、Java基础 |
| 2023.12 | JVM（类加载、内存） |
| 2024.1 | 快速排序（收官） |
代码中有 Bug（LCS），有未完成的功能（Prim），有拼写错误（BSF/DSF）。但这些"不完美"恰恰证明了：这是真实的学习过程，而不是复制粘贴的成果展示。
作为一个43岁的架构师，我想说的是：永远不要觉得补基础是浪费时间。你写的每一行底层代码，都会在未来的某一天，帮你做出更好的架构决策。
系列完
