文章目录
从背包问题说起
背包问题是一个非常经典的算法问题，它有多种版本，这里我先描述一种简单的：
有一个背包，它能装的最大物品重量是 capacity, 有若干物品 ，重量分别不等（物品无法切分）。
问：背包中能装入的最大重量是多少？
这是一个0-1背包问题，即物品要么选择装入，要么选择不装入，不能装物品的一部分。
暴力求解
因为每种物品有放入、或不放入两种情况，所以列出所有的可能性，然后找到最优解即可。这也就是回溯算法思想
代码如下：
public static int maxW = Integer.MIN_VALUE; //存储背包中物品总重量的最大值
/**
* 背包问题：0-1背包。每个物品要么装入，要么不装入。
* cw表示当前已经装进去的物品的重量和；i表示考察到哪个物品了；
* w背包重量；items表示每个物品的重量；n表示物品个数
* 假设背包可承受重量100，物品个数10，物品重量存储在数组a中，那可以这样调用函数：
* f(0, 0, a, 10, 100)
*
* @param i
* @param cur_w
* @param items
* @param goods 物品总数
* @param capacity 背包容量
*/
public static void bag1(int i, int cur_w, int capacity, int[] goods) {
if (i == goods.length || cur_w == capacity) {//已经全部考察完，或者背包已经满了。
if (cur_w > Max_Value) Max_Value = cur_w;
return;
}
//不选当前物品
bag1(i + 1, cur_w, capacity, goods);
if ((cur_w + goods[i]) < capacity) {//选当前物品
bag1(i + 1, cur_w + goods[i], capacity, goods);
}
}
public static void main(String[]args){
int[] items = new int[]{3, 2, 1 ,5 ,4 };
bag1(0, 0, 10, items);
System.out.println(maxW);
}
回溯算法思想，一般采用递归的编程思想。
上面的递归树如下：后两个参数不变，所以省略。f(i,j) 第一个参数表示考察到第几个物品，第二个参数表示目前背包中已经装入的物品重量。
* f(0,0)
* f(1,3) f(1,0)
*
* f(2,5) f(2,3) f(2,2) f(2,0)
*
* f(3,6) f(3,5) f(3,4) f(3,3) f(3,3) f(3,2) f(3,1) f(3,0)
可以看到f(i,cur_w) 有很多重复的分支，我们实际上只需保留其中的一个进行递归。所以可以利用 备忘录的方式进行优化：引入一个boolean二维数组，记录已经搜索过的分支，防止重复搜索。限于篇幅，可能有部分伪代码。
public static boolean[][]stats = new boolean[goods.length][capacity+1];
public static void bag1(int i, int cur_w, int capacity, int[] goods) {
if (i == goods.length || cur_w == capacity) {//已经全部考察完，或者背包已经满了。
if (cur_w > Max_Value) Max_Value = cur_w;
return;
}
//已经搜索过，就不再重复搜索。
if(stats[i][cur_w])return;
//记录在备忘录：
stats[i][cur_w] = true;
//不选当前物品
bag1(i + 1, cur_w, capacity, goods);
if ((cur_w + goods[i]) < capacity) {//选当前物品
bag1(i + 1, cur_w + goods[i], capacity, goods);
}
}
优化后的效率和动态规划几乎一样。但是某些场景不能用备忘录的方式。下文会讨论到。
动态规划求解
我们先看动态规划的思想如何求解上面的背包问题：
从上面的递归树，可以看到，每次对一个物品决策完，背包中的重量会产生不同的状态，动态规划就是把各个阶段决策后的状态全部推导出来，并且合并重复的状态（类似上面的备忘录），然后求最优解。
上面的物品是【3，2，1，5，4】，背包容量时 10 ,横坐标是背包物品重量，纵坐标是第几个物品（从0开始）
0 1 2 3 4 5 6 7 8 9 10
——————————————————————————————————————————————
0| √ √
1| √ √ √ √
2| √ √ √ √ √ √ √
3| √ √ √ √ √ √ √ √ √ √ √
4| √ √ √ √ √ √ √ √ √ √ √
第一个物品决策完，有两种状态：0 或者 3 。依据第一行推导所有的状态。代码如下：
public static int dybag(int[]goods,int capactity){
//状态二维表
boolean[][]stats = new boolean[goods.length][capacity+1];//重量范围是0 ~ capacity
//1.先处理第一个物品
stats[0][0] = true ;//不选的情况
if(goods[0]<=capacity){//选的情况
stats[0][goods[0]] = true;
}
//2.根据第一行状态推导所有状态
for(int i=1;i<goods.length;++i){
//第i个物品不放入背包的情况
for(int j = 0;j<=capacity;++j){
//和上一行保持一样
if(stats[i-1][j])stats[i][j]=true;
}
//第i个物品放入背包的情况
for(int j=0;j<capacity-goods[i];++j){
if(stats[i-1][j])stats[i][j+goods[i]] = true;
}
}
//3.在最后一行获取最大值
for(int j=capacity;j>=0;--j){
if(stats[goods.length-1][j])return j;
}
return 0;
}
时间复杂度分析：每层状态数不会超过 背包重量，所以时间复杂度就是代码中两层循环的乘积。即：O（nxcapacity) n 是物品个数。 空间复杂度也是是O（nxcapacity)
上面的代码可以优化,利用一维数组：
public static int dybag(int capacity,int[]goods){
boolean[]stats = new boolean[capacity+1];
//1.先处理第一个物品
stats[0] = true;
if(goods[0]<=capacity){
stats[goods[0]]=true;
}
//2.状态推导
for(int i=1;i<goods.length;++i){
for(int j=capacity-goods[i];j>=0;--j){
if(stats[j])stats[j+goods[i]] = true;
}
}
for(int j= capacity;j>=0;--j){
if(stats[j])return j;
}
return 0;
}
问题升级
上面问题是求解放入背包的最大重量，假如每个物品对应一个价值 value, 如何在背包容量固定的情况下，放入的价值最大？
同样，可以先采用回溯的暴力解法：
public static int[] goods = new int[]{2, 2, 4, 6, 3};
public static int[] values = new int[]{4, 3, 8, 9, 6};
public static int capacity = 6;
public static int Max_Value = Integer.MIN_VALUE;
/**
* i表示考察到第几个物品
* cur_w表示目前背包中的重量
* cur_v表示目前背包中物品的价值
* 调用： findMaxValue(0,0,0);
*/
public static void findMaxValue(int i,int cur_w,int cur_v){
if(i==goods.length || cur_w==capacity){//如果已经考察完毕，或者背包重量已满
if(cur_v>Max_Value)Max_Value = cur_v;//更新最大价值
return;
}
//不选择第i物品
findMaxValue(i+1,cur_w,cur_v);
if(cur_w+goods[i]<=capacity){//选择第i个物品
findMaxValue(i+1,cur_w+goods[i],cur_v+values[i]);
}
}
上面问题的递归树如下：
f(0,0,0)
*
* f(1,0,0) f(1,2,4)
*
* f(2,0,0) f(2,2,3) f(2,2,4) f(2,4,7)
*
* f(3,0,0) f(3,4,8) f(3,2,3) f(3,6,11) f(3,2,4) f(3,6,12) f(3,4,7) f(3,8,15)
可以看到有很多重复的f(i,j) ,在相同的重量情况下，我们应该选取价值更大的分支即可， 此时不能用备忘录的方式，比如 f(2,2) 对应的价值可以是3，或者4.如果用
二维数组备忘录，会采取f(2,2,3) 分支，而丢失f(2,2,4）的分支。
动态规划解决：
物品：{2, 2, 4, 6, 3}
价值：{4, 3, 8, 9, 6}
对应的状态表：横坐标表示背包重量，纵坐标表示第几个物品。状态值是价值数。
* 物品：{2, 2, 4, 6, 3}
*
* 价值：{4, 3, 8, 9, 6}
*
* 0 1 2 3 4 5 6
* ————————————————————————————————
* 0 │ 0 4
* 1 │ 0 4 7
* 2 │ 0 4 8 12
* 3 │ 0 4 8 12
* 4 │ 0 4 6 8 10 12
public static int dybag(int capacity,int[]goods,int[]values){
int[][]stats = new int[goods.length][capacity+1];
//1.先处理第一个物品
stats[0][0] = 0;
if(goods[0]<=capacity){
stats[0][goods[0]] = values[0];
}
//2.状态推导
for(int i = 1;i<goods.length;++i){
//不选第i个物品的状态
for(int j=0;j<=capacity;++j){
if(stats[i-1][j]>=0)stats[i][j] = stats[i-1][j];
}
//选第i个物品的状态
for(int j = 0 ;j<=capacity-goods[i];++j){
if(stats[i-1][j]>=0){
int v = stats[i-1][j]+values[i];
if(v>stats[i][j+goods[i]]) {
stats[i][j+goods[i]] = v;
}
}
}
}
//3.找到最值
for(int j = capacity;j>=0;--j){
if(stats[goods.length-1][j]>0)return stats[goods.length-1][j];
}
return 0;
}
用一个数组优化：
public static int dybay(int capacity,int[]goods,int[]values){
int[]stats = new int[capacity+1];
//1.处理第一个物品
stats[0] = 0;
if(goods[0]<=capacity){
stats[goods[0]] = values[0];
}
//2状态推导
for(int i=1;i<goods.length;++i){
for(int j=capacity-goods[i];j>=0;--j){
if(stats[j]>0){
int v = stats[j]+values[i];
if(v>stats[j+goods[i]]){
stats[j+goods[i]] = v;
}
}
}
}
//3.计算最大值
for(int i=capacity;i>=0;--i){
if(stats[i]>0)return stats[i];
}
return 0;
}
问题补充
上面的求解我们都计算出了最优解，但是我们如何能知道最右解对应的决策是什么，也就是我们选了哪几个物品？
比如上面的动态规划解法：我们知道 状态 (i,j)是由 状态 （i-1,j)或者(i-1,j-goods[i])推导而来，如果是从(i-1,j )可以推导过来
说明我们没有选第i个物品，否则我们选择第i个物品。如果两个都可以推导出（i,j) 说明有多种选择可以达到最优解，我们可以只选择一种即可。
代码如下：
public static int dybag(int capacity,int[]goods,int[]values){
int[][]stats = new int[goods.length][capacity+1];
//1.先处理第一个物品
stats[0][0] = 0;
if(goods[0]<=capacity){
stats[0][goods[0]] = values[0];
}
//2.状态推导
for(int i = 1;i<goods.length;++i){
//不选第i个物品的状态
for(int j=0;j<=capacity;++j){
if(stats[i-1][j]>=0)stats[i][j] = stats[i-1][j];
}
//选第i个物品的状态
for(int j = 0 ;j<=capacity-goods[i];++j){
if(stats[i-1][j]>=0){
int v = stats[i-1][j]+values[i];
if(v>stats[i][j+goods[i]]) {
stats[i][j+goods[i]] = v;
}
}
}
}
//3.找到最值
int max_values = 0;
int j;
for(j = capacity;j>=0;--j){
if(stats[goods.length-1][j]>0){
max_values = stats[goods.length-1][j];
break;
}
}
//打印选择的物品
for(int i=goods.length-1;i>=1;--i){
int v = stats[i-1][j-goods[i]];
if(v>0 && stats[i][j]-values[i] == v){
System.out.println("第"+i+"个物品："+goods[i]+" ");
j = j-goods[i];
}
}
if(j!=0) System.out.println("第"+0+"个物品："+goods[0]);
return max_values;
}
动态规划解题思路
动态规划是解决多阶段决策最优解的一种算法思想。
基本特征
- 多阶段决策：问题的求解涉及到多个阶段的决策，每一步决策都会产生不同的结果。
- 最优子结构：即我们可以根据一个决策推导出其他决策的结果。即状态表的推导过程。
- 重复子问题：递归树中重复的状态，利用动态规划就是为了消除重复，避免回溯的时间复杂度
- 无后效性：某个状态一旦确定，就不会受后续决策的影响。
求解思路
- 可以先尝试用回溯的暴力解法求解：熟练后，可以直接寻找最优子结构，即状态推导方程
- 画出递归树：看重复的状态
- 写出状态推导的方程
- 代码翻译：可以根据方程写递归代码，或者推导出状态表，然后求解。
算法练习目录
杨辉三角
-
题目描述：
假设你站在第一层，往下移动，我们把移动到最底层所经过的所有数字之和，定义为路径的长度。
请你编程求出从最高层移动到最底层的最短路径长度
-
思路：
每一步选择，都可以选择左侧的路径，或者右侧的路径。决策的次数刚好和层数相同。
假设有N层，我们构建一个NXN的二维状态表：（i，j）i表示行（层），j表示列(该层第几个元素)
第一层的选择只有一个所以（0，0）处的状态值是5，从第二层开始，如果某个节点A在这一层的最左（i,0)，那么A只能是从它的右上方走过来，如果A是
在该层最右侧（i,N) N表示第几层，则是从左上方走来。其他的节点，则是有两种可能，我们取其中状态值小的路径。所以状态推导如下：
先推导一直走左，或一直走右的状态
所以我们可以据此画出状态树 * i/j│ 0 1 2 3 4 * ———————————————————————————— * 0 │ 5 * 1 │ 12 14 * 2 │ 14 18 * 3 │ 18 19 * 4 │ 26 20推导其他状态：
上面首先画出一直选左节点或者右节点的状态。 * 空余部分的状态，我们可知，每个节点(i,j) 是从节点(i-1,j-1) 或者(i-1,j)推导而来。我们只需要选择 * Min((i-1,j-1),(i-1,j)) 较小的一个值加上当前节点的值就是该节点的状态。据此补全状态表： * i/j│ 0 1 2 3 4 * ———————————————————————————— * 0 │ 5 * 1 │ 12 14 * 2 │ 14 15 18 * 3 │ 18 23 21 19 * 4 │ 26 25 23 20 20 * * 最后只需要在最后一行找到最小值。 -
求解(翻译代码)：
static int[][]matrix = new int[][]{{5},{7,9},{2,3,4},{4,9,6,1},{8,7,2,1,1}}; public static int yanghui(){ int[][]stats = new int[matrix.length][matrix.length]; //1.处理第一列 int sum = 0; for(int i=0;i<matrix.length;++i){ sum+=matrix[i][0]; stats[i][0]= sum; } //2.处理对角线 sum = matrix[0][0]; for(int i=1;i<matrix.length;++i){ sum+=matrix[i][i]; stats[i][i] = sum; } //3.推导其他状态 for(int i=2;i<matrix.length;++i){ for(int j = 1;j<i;++j){ stats[i][j] = Math.min(stats[i-1][j-1],stats[i-1][j]) + matrix[i][j]; } } //4.获取最小值 int min = Integer.MAX_VALUE; for(int i=0;i<matrix.length;++i){ if(stats[matrix.length-1][i]<min)min = stats[matrix.length-1][i]; } return min; }
硬币找零
-
题目描述：
有若干面值的硬币v1,v2,…vn ,要找零w 。求需要的最小硬币个数。
-
思路：
每个硬币，有选或者不选两种情况，可以利用回溯解法，列出所有可能。这里前提是硬币面值为正，并且最小面值是1元。
/**
* 例如有硬币：【1,3,5】 target = 9
* 如果用回溯法：
* void f(int i,int cur_v,int[]coins){
* if(cur_v=target)更新最值
*
* //选择其中一个硬币
* for(){
*
* }
* }
*
* 递归树：(去重后)
* f(0,0)
* f(1,1) f(1,3) f(1,5)
* f(2,2) f(2,4) f(2,6) f(2,8) f(2,10)
* f(3,3) f(3,5) f(3,7) f(3,5) f(3,7) f(3,9)
*
* 推导状态表:纵坐标表示决策次数，因为目标是9元，而面值最小是一元，所以最多决策9次，否则不能找零，返回0.
* 第一次决策完，有1,3,5 三种状态，在这个基础上，第二次决策同样有三种选择，所以第二次决策完有2,4,6,8几种状态。依次推导当
* 发现目标target，即可以返回决策次数，即最小硬币数。
* 1 2 3 4 5 6 7 8 9
* 0 √ √ √
* 1 √ √ √ √
* 2 √ √ √ √
* 3
* 4
* 5
* 6
* 7
* 8
* 9
* @param target
* @param coins
* @return
*/
public static int coin(int target,int[]coins){
boolean[][]stats = new boolean[target][target+1];
//1.第一次决策
for(int i=0;i<coins.length;++i){
if(coins[i]<=target){
if(coins[i]==target){//如果一个硬币就满足
return 1;
}
stats[0][coins[i]] = true;
}
}
System.out.println("状态推导：：：");
//2.状态推导
for(int i = 1;i<target;++i){//从第二行开始推导
for(int j=1;j<target;++j){
if(stats[i-1][j]){//对上一个决策考虑加上每一个硬币后的状态
for(int m=0;m<coins.length;++m){
if(j+coins[m]<=target) {
if(j+coins[m]==target){
return i+1;
}
stats[i][j + coins[m]] = true;
}
}
}
}
}
return 0;
}
八皇后问题
-
题目描述
我们有一个 8x8 的棋盘，希望往里放 8 个棋子（皇后），每个棋子所在的行、列、对角线都不能有另一个棋子。
-
思路
我们一行一行放棋子，需要放置8次，每次我们放置的时候有8个选择，利用回溯的思想，我们可以穷举所有的放法，找到符合要求的放置位置。
在放置每个棋子时，要判断这个棋子是否满足要求，可以考察它所在的列、它的左上方对角线，右上方对角线分别是否有已经放置的棋子。
-
实现：
回溯方法：
public static int[]result = new int[8]; public static void eightQueens(int row){ if(row==8){//已经做完所有行的决策 printQueen(result); return; } for(int column=0;i<8;++column){ if(isOk(row,column)){ result[row] = column; eightQueens(row+1);//考察下一行 } } } //判断当前放置的位置是否符合要求 public static boolean isOk(int row ,int column){ int leftUp = column -1; int rightUp = column+1; int i = row-1; while(i>=0){ //考察同一列 if(result[i]==column){ return false; } //考察左上方对角线 if(leftUp>=0 && result[i]==leftUp){ return false; } //考察右上方对角线 if(rightUp<=8 && result[i]==rightUp){ return false; } --i; --leftUp; ++rightUp; } return true; } //打印结果 public static void printQueen(int[]result){ for(int row = 0;row8;++row){ for(int column=0;column<8;++column){ if(result[row][column]>0){ System.out.print("Q "); }else{ System.out.print("* ") } } System.out.println(); } }动态规划：
这里一个棋子确定，下一个的位置无法唯一确定，所以没有最优子结构，无法用动态规划的思路解。
棋盘走位
-
问题描述：
假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢
* 1 3 5 9 * 2 1 3 4 * 5 2 1 7 * 6 8 4 3 -
思路：
每次移动，可以选择向右或者向下，直到行或者列达到目标点（x,y)
点（i,j) 可以由 （i-1,j) 或者 （i,j-1) 推导而来，两者只需要选择较小的一个路径即可。所以可以写出一个递推公式：
f(x,y) = Min(f(x-1,y),f(x,y-1)) + w(x,y)有了递推公式，可以翻译成代码，调用：f(3,3)
public static int[][]matrix = { {1,3,5,9}, {2,1,3,4}, {5,2,1,7}, {6,8,4,3}, }; public static int minDist(int row,int column){ if(row==0 && column==0){ return matrix[0][0]; } if(row==0){ return minDist(row,column-1)+matrix[row][column]; } if(column==0){ return minDist(row-1,column)+matrix[row][column]; } return Math.min(minDist(row,column-1)+matrix[row][column],minDist(row-1,column)+matrix[row][column]); }利用状态表：
public static int[][]matrix = { {1,3,5,9}, {2,1,3,4}, {5,2,1,7}, {6,8,4,3}, }; //状态表 横向坐标和纵向坐标分别表示向右和向左走的步数。初始时，(0,0)处的状态值是1，即一步未走，路径和是1. * 0 1 2 3 * ———————————————————————————————— * 0 │ 1 * 1 │ * 2 │ * 3 │ //我们可以先推导出一直向下走和向右走，走过的数字之和。 * 0 1 2 3 * ———————————————————————————————— * 0 │ 1 4 9 18 * 1 │ 3 * 2 │ 8 * 3 │ 14 //其他位置(i,j)的状态值,是由(i-1,j) 或(i,j-1)中较小的值推导而来，有了上面的状态，可以推导出其他状态。 * 0 1 2 3 * ———————————————————————————————— * 0 │ 1 4 9 18 * 1 │ 3 4 7 11 * 2 │ 8 6 7 14 * 3 │ 14 14 11 14 //所以目标值就是 (3,3)处的状态值。翻译代码：
public static int[][]matrix = { {1,3,5,9}, {2,1,3,4}, {5,2,1,7}, {6,8,4,3}, }; //n是矩阵行数 public static int dpDist(int n){ int[][]stats = new int[n][n]; //1.先推导第一行状态 int sum = 0; for(int i = 0;i<n;++i){ sum+=matrix[0][i]; stats[0][i] = sum; } //2.推导第一列状态 sum=0; for(int j = 0;j<n;++j){ sum+=matrix[j][0]; stats[j][0]=sum; } //3.推导其他状态 for(int i=1;i<n;++i){ for(int j=1;j<n;++j){ stats[i][j] = Math.min(stats[i-1][j],stats[i][j-1]) + matrix[i][j]; } } //4.获取最值 return stats[n-1][n-1]; }
最长子序列
-
问题描述
我们有一个数字序列包含 n 个不同的数字，如何求出这个序列中的最长递增子序列长度？
- 比如 2, 9, 3, 6, 5, 1, 7 这样一组数字序列，它的最长递增子序列就是 2, 3, 5, 7，
- 所以最长递增子序列的长度是 4。
-
思路：
从第一个元素开始。每个元素有选择和不选两种情况。然后顺着这两条路，向下分化。 * 如果遇到大于前一个元素的值，该分支就更新目前的最长序列长度，并从新的节点继续寻找。 * * 2 N * * 9 N 9 N * * 3 N 3 N 3 N 3 N * .... * * * 调用：mostSeq(0,0,0,arr) * 测试序列：[2,3,9,0,1] xx表示Integer.MIN_VALUE; * * f(0,xx,0) * * f(1,2,1) f(1,xx,0) * * f(2,3,2) f(2,2,1) f(2,3,1) f(2,xx,0) * * f(3,9,3) f(3,3,2) f(3,2,1) f(3,3,2) f(3,9,2) f(3,3,1) f(3,9,1) f(3,xx,0) * * f(4,0,1) f(4,9,3) ... * * f(5,1,2) f(5,0,1) f(5,1,1) f(5,9,3) ... * * 可以看到有很多重复分支f(i,j,k) 我们只需要选择其中(i,j)相同，但k较大的分支即可。 * 优化后：如果利用备忘录，需要一个三维的数组，内存空间太大。所以考虑动态规划。回溯的代码：
public static int Max_Sequence = Integer.MIN_VALUE; public static void mostSeq(int i,int cur_v,int cur_seq,int[]arr){ if(i==arr.length){ if(cur_seq>Max_Sequence)Max_Sequence = cur_seq; return; } //如果不是第一次选择，并且之前有选择的值。需要判断下个值是否小于当前值。 if(cur_v!=Integer.MIN_VALUE && cur_v>=arr[i]){//如果下个值小于当前值，则更新后，重置序列号。 if(cur_seq>Max_Sequence)Max_Sequence = cur_seq; mostSeq(i+1,arr[i],1,arr); }else{//选当前值 mostSeq(i+1,arr[i],cur_seq+1,arr); } //不选当前值 mostSeq(i+1,cur_v,cur_seq,arr); }思路2：
a[0…i] 的最长子序列为: a[i] 之前所有比它小的元素中子序列长度最大值 + 1
public static int longestIncreaseSubArrayDP(int[] array) { if (array.length < 2) return array.length; int[] state = new int[array.length]; state[0] = 1; for (int i = 1; i < state.length; i++) { int max = 0; for (int j = 0; j < i; j++) { if (array[j] < array[i]) { if (state[j] > max) max = state[j]; } } state[i] = max + 1; } int result = 0; for (int i = 0; i < state.length; i++) { if (state[i] > result) result = state[i]; } return result; }
其他资料
leetcode-322