企业官网建设流程全解析

动态规划（DP）是算法中最重要也最难掌握的思想。这篇从两个经典问题入手，讲清楚 DP 的核心套路。

一、DP 的核心思想

DP = 最优子结构 + 重叠子问题 1. 把大问题拆成小问题（状态定义） 2. 找到小问题之间的关系（状态转移方程） 3. 从小问题开始算到大问题（递推）

DP 与分治的区别：分治的子问题互不重叠（如归并排序），DP 的子问题会重复出现（如斐波那契）。

二、斐波那契数列（入门）

// 递归（O(2^n)，大量重复计算）intfib(intn){if(n<=1)returnn;returnfib(n-1)+fib(n-2);}// DP（O(n)）intfib(intn){if(n<=1)returnn;int[]dp=newint[n+1];dp[0]=0;dp[1]=1;for(inti=2;i<=n;i++)dp[i]=dp[i-1]+dp[i-2];returndp[n];}

三、0-1 背包

publicintknapsack(int[]weights,int[]values,intcapacity){intn=weights.length;int[][]dp=newint[n+1][capacity+1];for(inti=1;i<=n;i++){for(intw=1;w<=capacity;w++){if(weights[i-1]>w){dp[i][w]=dp[i-1][w];// 装不下}else{dp[i][w]=Math.max(dp[i-1][w],// 不装dp[i-1][w-weights[i-1]]+values[i-1]// 装);}}}returndp[n][capacity];}

四、最长公共子序列

publicintlongestCommonSubsequence(Stringtext1,Stringtext2){intm=text1.length(),n=text2.length();int[][]dp=newint[m+1][n+1];for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(text1.charAt(i-1)==text2.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}returndp[m][n];}

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！