- 动态：求解过程应该是从问题最初开始进行
动态推导的，而不是直接求解出问题的答案 - 规划：每一步该如何做，才能使得这个问题能够动态的求解出答案
当我写斐波那契数列时，我在想些什么
斐波那契数列是一个典型的递归问题，同样也可以转化为一个树形结构
对于这个递归树，可以看出我们进行了许多重复的计算 (例如 3，2)
那对于这些重复的计算我们有没有办法只计算一次？
解决思路：利用一个全局数组memory，memory[ i ]就记下了第 i 个斐波那契数列的值，所以总共需要 i+1个空间[0…i]，于是可以优化成如下：
private int fib(int n){if(n==0) return 0;if(n==1) return 1;//如果当前斐波那契数列对应数值不存在于记忆数组中，则计算出其值，并存入//否则直接返回记忆的值//于是对每个n而言，只会计算一次相应的斐波那契值if(memory[n] == -1){memory[n] = fib(n-1)+fib(n-2);}return memory[n];}
将重复计算的值用数组记下来，下次再遇到时就不再使用递归又计算一次，而是直接返回记录下的值。这种方式又叫做记忆化搜索
递归其实就是自上而下的解决问题，同样，我们也能自下而上的解决斐波那契数列的问题，自下而上的方式就称之为动态规划
斐波那契数列的动态规划代码如下：
//动态规划-自下而上
private int fib2(int n){
memory[0] = 0;
memory[1] = 1;
for(int i=2; i<=n; i++){
memory[n] = memory[i-1]+memory[i-2];
}
return memory[n];
}
我们该什么时候谈动态规划
动态规划的精髓：
- 将原问题拆解成若干子问题，同时保留子问题的答案，使得每个子问题只求解一次，最终获得原问题的答案
大多数的动态规划问题其本质都是一个递归问题，但在递归过程会产生重叠子问题 (如在斐波那契数列的递归解法中重复求解的元素)，对于重叠子问题可以采用如下方式解决：
- 记忆化搜索 (自顶向下的解决问题)
- 动态规划 (自底向上的解决问题)
大部分情况下的动态规划问题并不仅仅具有重叠子问题这一特性，同时也具有最优子结构的特性，对于什么是最优子结构，下面会有说明
同时，动态规划最重要的一个特性是无后效性
- 在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的
- 某阶段状态一旦确定，就不受之后阶段的决策影响
当我开始做态规划题目时，我首先想到的是递归
70. 爬楼梯
对于这个问题，有如下的树形
即 calcWays[n] = calcWay[n-1] + calcWays[n-2] 的问题
递归写法如下：
int calcWays(int n){
if(n == 1) return 1;
if(n == 2) return 2;
return calcWays(n-1)+calcWays(n-2);
}
不难看出，如果使用递归调用的话，则会产生很多重复计算的过程，因此可以使用记忆化搜索/动态规划来解决这一问题
动态规划解法：
private int calcWays(int n){
if(n==1) return 1;
if(n==2) return 2;
memory[1] = 1;
memory[2] = 2;
for(int i=3; i<=n; i++){
memory[i] = memory[i-1]+memory[i-2];
}
return memory[n];
}
记忆化搜索解法：
private int calcWays(int n){
if(n==1) return 1;
if(n==2) return 2;
if(memory[n]==-1)
memory[n] = calcWays(n-1)+calcWays(n-2);
return memory[n];
}
343. 整数拆分
对于该树形问题而言，分割3获得的最大乘积再乘以3就是一个备选答案，2和3同理；最后选出三者中最大的那个
于是可以得出分割3的所有可能
于是可以画为如下情况
从树形中可以看出，有重叠子问题 ，同时由于我们求的是乘积最大化的结果，因此这又是一个最优子结构的问题
最优子结构 ：对于原问题而言我们需要求的是一个最优化的问题，而我们可以通过求子问题的最优解，进而获得原问题的最优解，这样的性质称为最优子结构
递归解决：
class Solution {
public int integerBreak(int n) {
return breakInteger(n);
}
//递归解决
//将n进行分割，至少分割为两个部分，以求得最大乘积
private int breakInteger(int n){
//1无法进行分割
if(n==1) return 1;
int res = -1;
//遍历[1..n-1]所有的可分割数字
for(int i=1; i<=n-1; i++){
//将n分为 i, (n-i) 两个数字
//(1*(n-1)); (2*(n-2))...，然后找到其中分割出来的乘积结果的最大值
res = Math.max(i*breakInteger(n-i), res);
//尝试比较本身分割出来的结果的乘积和上面的结果哪个更大
res = Math.max(res, i*(n-i));
}
return res;
}
}
记忆化搜索：
class Solution {
int[] memo;
public int integerBreak(int n) {
if(n==0) return 0;
memo = new int[n+1];
for (int i = 0; i <= n; i++) {
memo[i] = -1;
}
return breakInteger(n);
}
//记忆化搜索
//将n进行分割，至少分割为两个部分，以求得最大乘积
private int breakInteger(int n){
//1无法进行分割
if(n==1) return 1;
//如果不为-1，说明已经记录过，直接返回
if(memo[n]!=-1){
return memo[n];
}
int res = -1;
//遍历[1..n-1]所有的可分割数字
for(int i=1; i<=n-1; i++){
//将n分为 i, (n-i) 两个数字
//(1*(n-1)); (2*(n-2))...，然后找到其中分割出来的乘积结果的最大值
res = Math.max(i*breakInteger(n-i), res);
//尝试比较本身分割出来的结果的乘积和上面的结果哪个更大
res = Math.max(res, i*(n-i));
}
//记录下当前数字分割后的最大乘积
memo[n] = res;
return res;
}
}
动态规划：
//动态规划
private int breakIntegerDp(int n){
//dp[i]表示将数字i分割后(至少两部分)得到的最大乘积
int[] dp = new int[n+1];
//对底进行设置
dp[1] = 1;
for(int i=2; i<=n; i++){
//将i进行分割
for(int j=1; j<=i-1; j++){
//每次尝试将i分割为j和i-j
//分为两种情况：j*(i-j)直接分割相乘 和 j*(继续分割(i-j))，
//继续分割的值即是前面求出来的并存入dp的最大值
//j*dp[i-j]即根据最优子结构求出当前最优解
dp[i] = Math.max(j*dp[i-j], Math.max(j*(i-j), dp[i]));
}
}
return dp[n];
}
198. 打家劫舍
可以有如下递归树，对于偷取n号房子而言，有如下的方案 (因为不能偷取相邻房子，因此偷取n-1后不再考虑n)
当考虑偷取 i 后，下一次考虑偷取的房子就从 i+2 开始
因此，继续深入递归树
可以发现有许多的重叠子问题，对于子问题而言，其最优化解配合当前决策(偷哪家)，就是父问题的最优解
因此这个问题拥有最优子结构和重叠子问题 这两个性质
解题思路：
对编号为n的房子进行偷取
- 定义状态：考虑偷取 [x…n-1] 范围内的房子
根据状态定义：决定状态的转移
- f(0) = max {v(0) + f(2)，v(1)+f(3)…，v(n-2) + f(n)，v(n-1)} 状态转移方程
- v( i )代表第 i 号房子代表的收益，f( i )表示考虑偷取 [ i…n-1 ] 范围里的房子所能获得的最大收益
- 因此可以抽象出：f( i ) = max{ v( i ) + f( i+2 ) } f(i+2)应该偷取的下一家房屋的可得最大收益
我们也可以从第一家开始考虑偷取，则可以抽象出状态方程为：f( i ) = max { v( i ) + f( i-2 ) } (感觉这种比较好理解)
动态规划代码如下：
从前往后考虑
class Solution { public int rob(int[] nums) { if(nums.length == 0) return 0; if(nums.length == 1) return nums[0]; int[] dp = new int[nums.length]; dp[nums.length-1] = nums[nums.length-1]; dp[nums.length-2] = Math.max(nums[nums.length-2], nums[nums.length-1]); for(int i=nums.length - 3; i>=0; i--){ //nums[i]+dp[i+2]：当前房屋收益+下次应该偷取的房屋的收益 dp[i] = Math.max(dp[i+1], nums[i]+dp[i+2]); } return dp[0]; } }
- 从后往前考虑
class Solution { public int rob(int[] nums) { if(nums.length == 0) return 0; if(nums.length == 1) return nums[0]; int[] dp = new int[nums.length]; //dp[i]表示第i号房可得的最大金额 dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); for(int i=2; i<nums.length-1; i--){ //dp[i] 到第i号房为止可拿的最大金额 //nums[i]+dp[i-2] : 状态方程，第i号房的可偷窃金额 //dp[i-1]第i-1号房可以拿的钱 dp[i] = Math.max(dp[i-1], nums[i]+dp[i-2]); } return dp[nums.length-1]; } }
- 记忆化搜索
class Solution { int[] memo; public int rob(int[] nums) { if(nums.length <= 0) return 0; if(nums.length == 1) return nums[1]; memo = new int[nums.length+1]; return maxAmount(nums,0); } private int maxAmount(int[] nums,int start)//这个函数考虑抢劫[start...nums.size())范围内房子返回的钱数 { if(start>=nums.length) return 0; if(memo[start]!=0) return memo[start]; int res = 0; for(int i=start;i<nums.length;i++) { res = Math.max(res,nums[i]+maxAmount(nums,i+2)); } memo[start] = res; return res; } }
0-1背包？多少钱
对于动态规划的状态而言，状态应该满足题目的约束条件，对于01背包问题而言，有两个约束条件。如下：
F(n, C) 考虑将 n 个物品 放进 容量为 C 的背包，使得价值最大
因此可以考虑出如下两种策略：
F( i, c ) 表示选取第 i 个物品时背包的总价值和容量
F( i, c ) = F( i-1, c ) 第一种策略
F( i, c ) = v( i ) + F( i-1, c-w(i) ) 第二种策略
对于第一种策略而言，我们对第 i 个物品不进行加入，因此 F( i, c ) 中 c 没有变化；对第二种策略而言，尝试加入第 i 个物品，并将状态更新
因此，对这两种策略的选择，其实就是选取二者中可以使得F( i, c )较大的那个策略作为结果
因此状态转移方程如下：
- F( i, c ) = max( F( i-1, c ), v( i ) + F( i-1, c-w( i ) ) )
递归解法如下：
//递归解法
//用[0...index]的物品，填充容量为C的背包，使得价值最大
private int maxValue(int[] weight, int[] value, int index, int C){
if(C<=0 || index<0){
return 0;
}
//第一种策略，不管当前物品，用前index-1个物品填充C
int max = maxValue(weight, value, index-1, C);
//如果当前背包的剩余容量能够容纳下第index个物品
if(C >= weight[index]){
//第二种策略
//选用第index个物品放入背包
max = Math.max(max, value[index] + maxValue(weight, value, index-1, C-weight[index]));
}
return max;
}
在使用记忆化搜索之前，先注意，对于这个问题而言，有两个约束条件：n 和 c，可以代表在尝试选取第 n 个物品时容量为 c 下背包的价值，因此我们需要使用二维数组来对这个”键值对”下背包的价值进行记忆
因此记忆化搜索如下：
int[][] memo;
//关联index和C，表示放入第 index 个物品，容量为 c 时，背包价值是多少
//在第index行时只考虑第[0...index]个物品, 对考虑第index个物品而言，是基于[0...index-1]个物品得到的答案
memo = new int[weight.length][C+1];
... //省略初始化数组为-1的操作
//记忆化搜索
//用[0...index]的物品，填充容量为C的背包，使得价值最大
private int maxValueMemo(int[] weight, int[] value, int index, int C){
if(C<=0 || index<0){
return 0;
}
//如果当前约束条件下已经有过记录，直接返回
if(memo[index][C] != -1){
return memo[index][C];
}
//第一种策略，不管当前物品，用前index-1个物品填充C
int max = maxValueMemo(weight, value, index-1, C);
//如果当前背包的剩余容量能够容纳下第index个物品
if(C >= weight[index]){
//第二种策略
//选用第index个物品放入背包
max = Math.max(max, value[index] + maxValueMemo(weight, value, index-1, C-weight[index]));
}
//记录当前约束条件下的背包价值
memo[index][C] = max;
return max;
}
在尝试使用动态规划时，我们尝试推出如下表格
其中三行的每一行为对应物品，每一列为对应容量，所以每一格表示对当前物品在现在的容量下进行两种策略选择后的最大值
因此，动态规划解法如下：
public int bag01(int[] weight, int[] value, int C){
//动态规划解法
int n = weight.length;
int[][] dp = new int[weight.length][C+1];
//自底向上, 只考虑0号物品
for(int i=0; i<=C; i++){
//容量i是否存的下第0个物品，如果存的下，dp[0][i]就存第i个物品
dp[0][i] = (weight[0] <= i ? value[0] : 0);
}
//求解其它行
for(int i=1; i<n; i++){
for(int j=0; j<=C; j++){
//dp[i][j]表示第i个物品且容量为j时可以获得的最大价值
//策略1：不使添加第i个物品
dp[i][j] = dp[i-1][j];
//策略2：添加第i个物品，并与策略1比较
if(j >= weight[i]){
dp[i][j] = Math.max(dp[i][j], value[i]+dp[i-1][j-weight[i]]);
}
}
}
return dp[n-1][C];
}
对于这个版本的代码而言，空间复杂度为O(nC)，时间复杂度也为O(nC)，在空间复杂度上，可以继续进行优化
我的背包还能更轻？
从基础解法中可以发现，第 i 行元素只依赖于第 i-1 行元素。因此理论上我们只需要保持两行元素即可，空间复杂度下降为了 O( 2*C ) = O( C )
第一步：基于第0行求解第1行
第二步：我们求解第二行2只需要基于第1行即可，因此覆盖掉”0”行
同理：
……
可以发现，占用掉第一行的总是 i 为偶数，占用第二行的总是 i 为奇数。因此在计算某一行时，只需要知道 这一行的奇偶即可
因此优化很简单，如下：
//01背包优化
public int betterBag01(int[] weight, int[] value, int C){
//动态规划解法
int n = weight.length;
//只需要两行
int[][] dp = new int[2][C+1];
//自底向上, 只考虑0号物品
for(int i=0; i<=C; i++){
//容量i是否存的下第0个物品，如果存的下，dp[0][i]就存第0个物品
dp[0][i] = (weight[0] <= i ? value[0] : 0);
}
//求解其它行
for(int i=1; i<n; i++){
for(int j=0; j<=C; j++){
//dp[i][j]表示第i个物品且容量为j时可以获得的最大价值
//策略1：不使添加第i个物品
dp[i%2][j] = dp[(i-1)%2][j]; //第i行依然根据第i-1行来，但我们只需要两行的物理空间即可，当i为偶数行时，就根据上一行即奇数行来计算
//策略2：添加第i个物品，并与策略1比较
if(j >= weight[i]){
dp[i%2][j] = Math.max(dp[i%2][j], value[i]+dp[(i-1)%2][j-weight[i]]);
}
}
}
return dp[(n-1)%2][C];
}
在这个优化版本中，虽然大O表示法下只有O(C)的空间复杂度，但空间复杂度其实是2*C，那有没有可能使得空间复杂度真正的为O(C) ？
在推导二维数组的过程中，不难发现我们永远只会比较当前单元格的上面单元格和其左边单元格，而永远不会去使用上面单元格的右边单元格
因此，在考虑使用一行时，可以从右向左的刷新这一行的内容
假设：目前我们在考虑 i=1 这一行，那首先考虑背包容量为 5 的时候，相应的格子应该变为什么。由于编号 i=1 的物品重量为2，因此5-2=3，我们考虑加入weight=3的物品即编号 i=2 的物品。其中容量为5的对应格子就代表了没有更新前容量为5时背包的最大价值。由于 i=1 时value(1)为10，因此可以发现C为5时，可以容纳的最大价值就变成了10+6=16，因此更新 C( 5 )
接着，尝试更新背包容量为 4，由于 i 仍然为 2，因此尝试的是和背包容量为2时，与当前的value( i )进行相加的值，和原来的值进行比较，取二者较大的那一个
不难计算，value(1) =10, 10+F( V( C(2) ), C(2) ), 即 10+6=16，所以，更新容量为4时的格子
以此类推：
当容量C小于weight( i )时，不再考虑更新其值，因为根本没办法放进新的物品，更新也无从谈起
再次优化后的01背包代码如下
//01背包再次优化
public int betterBag01(int[] weight, int[] value, int C){
//动态规划解法
int n = weight.length;
int[] dp = new int[C+1];
//自底向上, 只考虑0号物品
for(int i=0; i<=C; i++){
//容量i是否存的下第0个物品，如果存的下，dp[i]就存第0个物品
dp[i] = (weight[0] <= i ? value[0] : 0);
}
for(int i=1; i<n; i++){
//从右往左更新，容量j装不下第i个物品
for(int j=C; j>=weight[i]; j--){
//dp[j]表示选取当前容量j下背包的最大价值，每一次更新尝试将value(i)加入，进行对比
dp[j] = Math.max(dp[j], value[i]+dp[j-weight[i]]);
}
}
return dp[C];
}
为什么我的背包还能变异！
- 完全背包问题
在01背包问题中，每个物品只能被选用一次；而在完全背包问题中，每个物品可以被无限次选用
在这里只提一下思路：虽然每个物品可以被无限次的选用，但背包的容量是有限的，因此每个物品的可选用次数是有限次的，这样就可以转化为选用有限物品的问题，只是在这些物品中有重复的
多重背包问题
每个物品不止1个，有 num( i )个；这种变种问题与完全背包问题类似多维费用背包问题
同时考虑物品的体积和重量两个维度
01背包问题也可以有更加复杂的变种：如加入物品之间的排斥，依赖等约束
背包问题应用
416. 分割等和子集
典型的背包问题应用，在n个数字中选出一些数字，填满 sum/2 的背包
因此，参考背包问题的状态，可以得出这道题的状态： F( n , C ) 考虑将 n 个物品填满容量为C的背包
如果[0…i-1]的物品能把背包填满，或者[0…i]的物品也能把背包填满，则返回true，因此状态转移方程为：
- F( i , c ) = F( i-1, c ) || F( i-1, c-w(i) )
因此，递归解法如下：
class Solution{
public boolean canPartition(int[] nums) {
//由于需要找出nums中的数字组合能够满足等于一半的nums总和，因此先计算出nums总和sum
int sum=0;
for (int num : nums) {
sum+=num;
}
//如果nums里面的数字和不能被平分的话，那无论在nums中如何选取，都无法选出一部分让其等于另外一部分
if(sum%2!=0){
return false;
}
return tryPar(nums, nums.length-1, sum/2);
}
//尝试从[0...index]是否可以完全填充c，即sum/2
private boolean tryPar(int[] nums, int index, int c){
//如果背包没有空间了
if(c==0){
return true;
}
if(index<0 || c<0){
return false;
}
//策略1：不使用第index个物品，看是否能填充 //策略2：使用第index个物品，看是否能填充
return tryPar(nums, index-1, c) || tryPar(nums, index-1, c-nums[index]);
}
}
记忆化搜索解法如下：
class Solution {
//memo[i][c] 表示使用索引为[0...i]的这些元素，是否能够填充容量为 c 的背包
//-1表示未计算，0表示计算过，但不可填充，1表示可填充
private int[][] memo;
public boolean canPartition(int[] nums) {
//由于需要找出nums中的数字组合能够满足等于一半的nums总和，因此先计算出nums总和sum
int sum=0;
for (int num : nums) {
sum+=num;
}
//如果nums里面的数字和不能被平分的话，那无论在nums中如何选取，都无法选出一部分让其等于另外一部分
if(sum%2!=0){
return false;
}
//sum/2+1列
memo = new int[nums.length+1][sum/2+1];
for (int i = 0; i < memo.length; i++) {
Arrays.fill(memo[i], -1);
}
return tryParMemo(nums, nums.length-1, sum/2);
}
//记忆化搜索
private boolean tryParMemo(int[] nums, int index, int c){
//如果背包没有空间了
if(c==0){
return true;
}
if(index<0 || c<0){
return false;
}
//已经记录过当前容量下能否填充，则直接返回
if(memo[index][c] == 0){
return false;
}
memo[index][c] = (tryParMemo(nums, index - 1, c) ||
tryParMemo(nums, index - 1, c - nums[index])) == true ? 1 : 0;
return memo[index][c] == 1;
}
}
动态规划解法如下：
class Solution {
public boolean canPartition(int[] nums) {
if(nums.length==0) return false;
//由于需要找出nums中的数字组合能够满足等于一半的nums总和，因此先计算出nums总和sum
int sum=0;
for (int num : nums) {
sum+=num;
}
//如果nums里面的数字和不能被平分的话，那无论在nums中如何选取，都无法选出一部分让其等于另外一部分
if(sum%2!=0){
return false;
}
//动态规划解法
int C = sum/2;
int n = nums.length;
//dp[i]表示容量为i时能否完全填充
boolean[] dp = new boolean[C+1];
//尝试初始化dp[i], 如果nums[0]等于容量i的话就直接完全填充了
for (int i = 0; i <= C; i++) {
dp[i] = (nums[0] == i);
}
for(int i=1; i<n; i++){
//从右往左刷新，当j<nums[i]时，就装不下了
for(int j=C; j>=nums[i]; j--){
//看之前是否已经被填满/加上当前这个数字后可以被填满，则表示当前的dp[i]可以被完全填充
dp[j] = dp[j] || dp[j-nums[i]];
}
}
return dp[C];
}
}
LIS问题
300. 最长上升子序列
注意：什么是子序列？什么是上升？
子序列即序列的子集，对于子序列而言，不要求是连续的；
对于上升而言，要求后一个数比前一个数要大，这里的上升并不是严格上升，当二者相等时，不算上升
一个序列可能有多个最长上升子序列，但这个最长的长度只有1个
从暴力解法方面来看，求出所有的子序列后返回其中最长的子序列的长度即可，时间复杂度为O(2 * n)，2为子序列数目，n为判断该序列是否为上升子序列的过程
对于动态规划问题而言，首先找到其状态和状态转移方程
状态可以表示为：
Lis( i ) 表示以第 i 个数字为结尾的最长上升子序列的长度
Lis( i ) 表示[ 0…i ]的范围内，选择数字nums[ i ]可以获得的最长上升子序列的长度
抽象定义为：Lis( i ) = max(1+Lis( j ) if nums[i] > nums[j] ) ( i > j )
对于 j 后面的位置 i 来说，如果存在一个数字nums[ i ]比nums[ j ]大，则说明又找到一个上升的数，对Lis( i )进行更新，更新为Lis( j )+1
一开始，每个Lis( i ) 都是1，因为每个数的最长上升子序列就是它自己
而后，每个数与自己前面的数进行比较，如果比前面的数字要大，则成为一个上升序列，更新Lis( i )
当nums[6]与nums[3]对比后, 比nums[3]大，所以Lis( 6 )即101更新为Lis( 3 )+1=3，再与Lis( 4 )+1对比，发现大小相同，因此不更新
最后，与nums[5]比较，发现比它大，更新为Lis(6) = Lis(5)+1 = 4
因此，结果为：
对于Lis( i )来说，并不是一直上升的，如：
因此，得出解：
class Solution {
public int lengthOfLIS(int[] nums) {
if(nums.length == 0) return 0;
if(nums.length == 1) return 1;
if(nums.length == 2) return (nums[0]>nums[1] ? 1: 2);
//dp[i]表示以nums[i]为结尾的上升子序列长度
int[] dp = new int[nums.length+1];
//初始化每个数字其最长上升子序列为其自己，即1
Arrays.fill(dp, 1);
for(int i=0; i<nums.length; i++){
//尝试nums[i]之间的所有元素
for(int j=0; j<i; j++){
if(nums[j] < nums[i]){
//更新dp[i]
dp[i] = Math.max(dp[i], 1+dp[j]);
}
}
}
//最长子序列的长度可能存在于dp数组中的任意位置
Arrays.sort(dp);
return dp[nums.length];
}
}
对于尝试优化成时间复杂度为O(nlog)的算法而言，我们可以尝试使用二分查找的方式
LCS问题
1143. 最长公共子序列
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
对于LCS问题的状态设置如下：
LCS( m , n ) 为 text1[0…m] 和 text2[0…n] 的最长公共子序列的长度
于是，问题就是比较text1和text2了
从后往前的状态转移方程如下：
当从后往前推时，需要基于`下一个元素`进行增加
text1[ i ] == text2[ j ]：
LCS ( i , j ) = 1+LCS( i+1, j+1 )如果不相等，则往前寻找较大的那个公共子序列
text1[ i ] != text2[j]：
LCS( i , j ) = max( LCS( i+1, j ), LCS( i, j+1 ) )
从前往后的状态转移方程如下：
从前往后推，需要基于`上一个元素`进行增加
对于LCS(0, 0)来说，必然为0，因此需要从1开始，基于0进行求解，到末尾处截止，因此最后结果存于LCS( text1.size, text2.size ) 处
text1[i-1] == text2[i-1]:
LCS ( i , j ) = 1+LCS( i+1, j+1 )text1[i-1] != text2[j-1]
LCS( i , j ) = max( LCS( i+1, j ), LCS( i, j+1 ) )
EG：ABCD 和 AEBD
第一步：先找到了D 和 D相等，因此记录下来最大公共子序列长度变为1
第二步：发现 C 和 B 不等，因此讨论text1和text2各缩1步的情况 
第三步：`先走左边`，从左边的AB | AEB来看，B相等了，于是，再将这一步记录下来长度为1
第四步：继续发现A | AE 的 A和E不等，因此，再次讨论各缩一步的情况，于是，再记录下一个1，最后text1和text2都变成了空，左边的寻找结束，因此`从左边查找得到的最大公共子序列为 3`
接着，来讨论右子树的情况
第五步：ABC | AE，C和E不等，因此又各自缩小一步
后面的步骤同理，一旦遇到不等字符，就各缩一步，再进行比较
从后往前推的代码如下：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int[][] LCS = new int[text1.length()+1][text2.length()+1];
for(int i=text1.length()-1; i>=0; i--){
for(int j=text2.length()-1; j>=0; j--){
if(text1.charAt(i) == text2.charAt(j)){
LCS[i][j] = 1+LCS[i+1][j+1];
}else{
//分别缩小一步，如果是有相等字符的话，
LCS[i][j] = Math.max(LCS[i+1][j], LCS[i][j+1]);
}
}
}
return LCS[0][0];
}
}
从前往后推的代码如下：
class Solution {
public int longestCommonSubsequence(String text1, String text2){
int[][] LCS = new int[text1.length()+1][text2.length()+1];
for(int i=1; i<=text1.length(); i++){
for(int j=1; j<=text2.length(); j++){
if(text1.charAt(i-1) == text2.charAt(j-1)){
LCS[i][j] = 1+LCS[i-1][j-1];
}else{
//分别"缩小"一步，查看上一位是否有相等字符，
LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
}
}
}
return LCS[text1.length()][text2.length()];
}
}
浅谈：Dijkstra背后的影子
Dijkstra背后其实有着动态规划的影子
对于Dijkstra的状态而言，可以这样定义：
状态：shortestPath( i ) : 为从 start 到 i 的最短路径长度
状态转移方程：
对于 x 结点的最短路径值而言，是在每一个可以到达 x 结点的 a 结点中，计算出到达 a 结点的最短路径值+ a->x 的路径值的开销中，选取最小的那一个
shortestPath( x ) = min( shortestPath(a) + w( a->x ))
其实，在知乎上关于Dijkstra背后的算法思想到底是贪心还是dp有个很有意思的争论
关于具体解
在上述动态规划问题中，我们并没有给出一个具体的解，而是找出其总和，差值等大致解
那能不能求出其具体解呢？例如，在背包问题中，我们只知道其最大价值是多少，却不知道是哪些物品构成了最大价值；在LIS问题中，我们只知道最大长度，而不知道是哪些数字构成了最大长度
其实获得具体解的过程其实就是一个逆推的过程 (值得注意的是，在背包问题中我们优化空间复杂度至O(C)的情况下，会使得没有足够的信息来进行逆推)
若有收获，就点个赞吧
0 人点赞
