用简单方法理解动态规划算法
动态规划在编程中有着广泛的应用,对于某些问题我们可以通过动态规划显著的降低程序的时间复杂度。本质上动态规划并不是一种算法,而是解决一类问题的思想。本篇博客通过一些非常简单而又经典的问题(比如数塔、0-1背包、完全背包、走楼梯问题、最长公共子序列等)来帮助大家理解动态规划的一般套路。
欢迎探讨,如有错误敬请指正
如需转载,请注明出处 http://www.cnblogs.com/nullzx/
1. 动态规划的基本思想
如果我们解决一个问题的时候能将一个大问题转换成一个或者若干个规模较小的同等性质的问题,当我们求解出这些小问题的答案后,大问题的答案很容易解决,对于这样的情况,显然我们可以递归(或者说分治)的方式解决问题。如果在求解这些小问题的过程中发现有些小问题我们需要重复计算多次,那么我们就干脆把已经求解过的小问题的答案记录下来放在一张表中,这样下次遇到这个小问题,我们只需要查表就可以直接得到结果,这个就是动态规划的白话讲解。动态规划的难点在于如何定义问题及子问题。
2. 笨办法的套路
1)如果可以将一个规模较大的问题转换成一个或若干个规模较小的子问题,也就是能找到递推关系,这个时候我们不妨先将程序写成递归的形式。
2)如果使用递归求解规模较小的问题上存在子问题重复求解的现象,那么我们就建立一张表(有可能这个表只有一行)记录需要重复求解的子问题。填表的过程和将大问题划分为子问题的方式相反,我们会从最简单的子问题开始填表。现在我们就利用这个套路解决下面这些经典的问题。
3. 利用套路解题
3.1 菲波那切数列
问题描述:菲波那契数列的定义f(n) = f(n-1) + f(n-2), 且f(1)=1, f(2) = 1,求f(n)的值。斐波那契数列的定义本身就是将大问题转换成两个同性质的子问题,所以我们可以直接根据定义写成递归形式。
public static int recursion(int n) { if (n < 0) { return 0; } if (n == 1 || n == 2) { return 1; } return recursion(n-1) + recursion(n-2); }
我们以f(6)为例现在把递归的过程画出来
我们发现在求解F(6)时,需要求解F(2)四次,求解F(1)三次,求解F(3)三次,F(4)两次,所以说我们的算法的效率是很低的。提高效率的办法就是将F(1),F(2),F(3) ….的结果放在表中,下次要计算这些问题的时候我们直接从表中获取就好了,这就是一个最简单的动态规划的例子。现在我们按照套路,从最小的子问开始填表就好了。
public static int dynamic(int n) { int[] table = new int[n+1]; table[1] = 1; table[2] = 1; /*从小到大填表*/ for (int i = 3; i < table.length; i++) { table[i] = table[i-1] + table[i-2]; } return table[n]; }
需要说明的是,这个例子只是一个入门的例子,实际上它不存在最优子结构的问题,而且也不需要长度为n+1的table数组,只需要两个变量即可(可以理解为动态规划的优化版本),而我们之所以这样讲解只是为了让大家从动态规划的角度去理解问题。
3.2 走楼梯问题
问题描述:总共有n个楼梯,每次可以走2个台阶,或者每次走3个台阶,或者每次走5个台阶,请问这n个楼梯总共有几种走法。
n个阶梯的问题,可以分解成三个小问题,即n-2个阶梯有几种走法,n-3个阶梯有几种走法,n-5个阶梯有几种走法,而n个阶梯的走法就是这三种走法的和。或者可以反过来思考,你已经站在最后一个台阶上了,那么到达最后一个台阶的情况只能是三种情况,最后一步恰好走2个台阶恰好到达,最后一步恰好走3个台阶恰好到达,最后一步恰好走5个台阶恰好到达。通过这个思想,我们就可以写出递归形式的代码。
public static int recursion(int n) { if (n < 0) { return 0; } if (n == 0) { return 1; } return recursion(n - 5) + recursion(n - 3) + recursion(n - 2); }
显然上面递归的处理方式需要重复计算很多子问题,画出递归调用的图就一目了然,由于该图和上一个问题的图很类似,这里就省略了。因此就创建一张表,把子问题的结果都记录下来,dp[i]表示走到第i个阶梯有多少种走法。按照套路,我们应该从小的阶梯数开始填表。
public static int dynamic(int n) { int[] record = new int[n+1]; record[0] = 1; for (int i = 0; i < record.length; i++) { int n2 = i - 2 >= 0 ? record[i-2] : 0; int n3 = i - 3 >= 0 ? record[i-3] : 0; int n5 = i - 5 >= 0 ? record[i-5] : 0; record[i] = n2 + n3 + n5; } return record[n]; }
同样,这里例子中也不存在最优问题。
3.3 数塔问题
问题描述:从顶部出发在每一个节点可以选择向下或者向右下走,一直走到底层,要求找出一条路径,使得路径上的数字之和最大。
对于上图所示的数塔:最大值为379, 绿色的的数字就是被选择的节点。
这个问题不能使用贪心算法,请大家自己用三层的阶梯列举出反例。我们现在试着将这个问题分解成子问题,如下图所示。想求得最大值,我们只要选择的红色边框数塔最大值和蓝色边框数塔的最大值中更大的那个,然后加上32,就整个数塔的最大值。这样我们就将一个大的问题转化成了两个规小的问题,然后这两个规模较小的问题还可以继续分解成更小的子问题。根据这个思路,我们可以得到如下递归形式的代码。
/*我们用一个二维数组的左下半数组表示数塔*/ public static int recursion(int[][] a){ return recursion(a, 0, 0); } /*参数i表示所在的行,j表示所在的列*/ private static int recursion(int[][] a, int i, int j){ /* * 当分解问题到最下一层时, * (a.length - 1, j)位置为顶点的数塔实际上数塔只有一个元素, * 直接返回 */ if (i == a.length - 1){ return a[i][j]; } /*求(i+1, j)位置为顶点的数塔最大值*/ int r1 = recursion(a, i+1, j); /*求(i+1, j+1)位置为顶点的数塔最大值*/ int r2 = recursion(a, i+1, j+1); /*返回(i,j)为顶点位置的数塔的最大值*/ return Math.max(r1, r2) + a[i][j]; }
上述代码能够得到正确的结果,但是我们发现计算大一点的数塔计算会很费时间,这主要是重复计算的问题,我们现在来分析一下为什么会出现重复计算的问题。
上图中的紫色边框数塔既存在于红色边框数塔中,也存在于蓝色边框数塔中,会重复计算两次。实际上,我们使用递归时重复计算的问题显然不止这一个,所以效率不高。为此我们应该创建一张和数塔形状一样的三角形表用来记录更小的数塔的最大值。我们table表示这个表,表中table[i][j]位置的值表示以(i,j)为顶点的数塔的最大值。我们用a[i][j]表示数塔中第i行,第j列的值。那么table[i][j] = a[i][j] + Math.max(table[i-1][j], table[i-1][j-1])。按照套路,我们应该从最小的数塔开始填表。按照table[i][j]的定义,table表的最下面一行就应该等于数塔表中的最下面一行。
按照定义,我们就可以填倒数第二行的dp[i][j]。
table[4][0] = 79 + Math.max(0, 71) = 150 table[4][1] = 69 + Math.max(71, 51) = 140 table[4][2] = 78 + Math.max(51, 82) = 160 table[4][3] = 29 + Math.max(82, 91) = 120 table[4][4] = 63 + Math.max(91, 64) = 154
填入到table表的倒数第二行,如下图所示
有了倒数第二行,我们就可以推出倒数第三行,依次类推,我们就可以得到最上面table [0][0]的数值,它就表示了整个数塔的最大值。除了最大值,如果我们还需要知道走了哪些路径,我们还应该定义一个path表,在填table[i][j]时,同时填写path[i][j]。path[i][j]表示了以(i, j)为顶点的数塔的最大值是由两个子数塔(table[i-1][j]为顶点的数塔和table[i-1][j+1]为顶点的数塔)中的哪一个得到的。
public class NumbericalTower { /*最大值对应的各个顶点位置*/ private LinkedList<Map.Entry<Integer, Integer>> pathList; /*存储整个数塔的最大值*/ private int result; public NumbericalTower(int[][] a) { pathList = new LinkedList<Map.Entry<Integer, Integer>>(); dynamic(a); } private void dynamic(int[][] a){ final int N = a.length; /*path[i][j] 表示(i+1, j)为顶点的数塔和(i+1,j+1)为顶点的数塔 *中较大的那个*/ int[][] path = new int[N][N]; /*动态规划对应的表*/ int[][] table = new int[N][N]; /*从最小的数塔开始填表*/ for (int i = N - 1; i >= 0; i--) { /*根据下层数塔的最大值计算上层的数塔的最大值*/ for (int j = 0; j <= i; j++) { if (i == N - 1) { table[i][j] = a[i][j]; path[i][j] = -1; }else if (table[i+1][j] > table[i+1][j+1]) { table[i][j] = table[i+1][j] + a[i][j]; path[i][j] = j; }else{ table[i][j] = table[i+1][j+1] + a[i][j]; path[i][j] = j+1; } } } result = table[0][0]; /*记录最大值对应的顶点*/ int i = 0, j = 0; pathList.add(new SimpleEntry<Integer, Integer>(0, 0)); while (true) { j = path[i][j]; i = i + 1; pathList.add(new SimpleEntry<Integer, Integer>(i, j)); if (path[i][j] == -1) { break; } } } int max(){ return result; } List<Map.Entry<Integer, Integer>> path(){ return pathList; } public static void main(String[] args) { int[][] a = { {32}, {83, 68}, {40, 37, 47}, { 5, 4, 67, 22}, {79, 69, 78, 29, 63}, { 0, 71, 51, 82, 91, 64} }; NumbericalTower nt = new NumbericalTower(a); int max = nt.max(); List<Map.Entry<Integer, Integer>> path = nt.path(); System.out.println("最大值:" + max); System.out.println("\n\n路径为:"); for (Map.Entry<Integer, Integer> entry : path) { int r = entry.getKey(); int c = entry.getValue(); System.out.println("行 : " + r + ", 列:"+ c); } } }
运行结果
最大值:379 路径为: 行 : 0, 列:0 行 : 1, 列:0 行 : 2, 列:1 行 : 3, 列:2 行 : 4, 列:2 行 : 5, 列:3
3.4 零-壹背包问题
问题描述:有n 个物品,它们有各自的重量(weight)和价值(value),现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和此时背包中的物品?一个物品只有不拿和拿两种情况,可以用0和1表示,所以称之为0-1背包问题。
我们来看一个具体的例子。假设有如下物品:
求背包容量在10的时候的能装物品的最大价值,以及装了哪些物品?
3.4.1 解决背包的最大价值
我们可能首先想到的是贪心算法,我们算出每种物品的单位重量价值(weight/value),然后按照单位重量价值排序。我们放入物品时首先选择单位重量价值高的物品,直到放不下为止。但是很遗憾,这样得不到最优解。我们不妨列举一个极端的例子,假设只有两个物品,A的value = 2.9, weight = 2.1;B的value = 3, weight = 3,显然物品A的单位重量价值要大于B的单位重量价值,但对于容量为3的背包,我们应该选择物品B,所以贪心算法失效。对于0-1背包问题,贪心选择之所以不能得到最优解是因为:它无法保证最终能将背包装满,而部分闲置的背包空间使每公斤背包空间的价值降低了。
回到上面具体的这个问题,它可以表述为
maxValue{宝石、剃须刀、ipad、充电宝、iphone | 背包容量10},
每个物品只有选和不选两种结果,我们不妨从第一个物品开始。如果选了宝石,那么问题转化为当前背包已有价值为50,并在剩下的背包容量(10 - 4)的前提下,再剩下的物品中(即剃须刀、ipad、充电宝、iphone)选取出最大的价值;如果不选宝石,那么问题转化为当前背包价值为0,并在剩下的背包容量10的前提下,在剩下的物品中(即剃须刀、ipad、充电宝、iphone)选取出最大的价值。我们只需要选择:
50 + maxValue{剃须刀、ipad、充电宝、iphone | 背包容量6}
与
0 + maxValue{剃须刀、ipad、充电宝、iphone | 背包容量10}
中较大的那个。而这就直接转化成两个子问题的求解,显然我们已经可以用分治的方式解决这个问题了。我们不妨把递归树(或者说分治树)画出来。
上图就是0-1背包问题的递归树,图左文字边表示当前可选的物品,节点中的值表示背包的容量。我们没有把整个递归树全部都画出来,因为图中我们就已经发现了需要重复计算的子问题。如果背包容量变大,物品种类变多,那么需要重复计算的子问题就越多。需要说明的是上图中有三个背包容量为7的子问题,但是只有被标记的两个子问题才是重复的子问题,因为这两个子问题的背包容量一样,可选物品一样。为了避免子问题的重复求解,我们就建立一张动态规划表,下次遇到重复的子问题,我们就直接查表。下图表示了动态规划表和递归树之间的关系。
那我们现在的主要问题就变成了如何填这样一张表。我们用一个名为dp的二维数组表示这张表,dp[0]行需要单独初始化,从dp[1]行开始填表,规则:从左到右,从上到下。
dp[i][j]表示前i个物品(包括物品i),在背包容量为j时能装的最大价值。
dp[i][j]为下面两者的最大值:
1)物品i不放入背包中:背包容量为j时,前i-1个物品组合出的最大价值
2)物品i放入背包中:物品i的价值 + 除去物品i占用的重量后,剩余背包容量j-weight(i)由前i-1个物品组合出的最大价值
用公式表示为
3.4.2 解决背包有哪些物品
通过dp表,我们还可以知道哪些物品放入了背包中。从表格的右下角开始(第0个物品要单独处理):
1)如果dp[i][j] > dp[i-1][j],说明该物品i被放入到了背包中,令i = i – 1, j = j – weight[i],然后重复步骤1。
2)如果dp[i][j] == dp[i-1][j],且只想得到背包最大价值的其中一种的物品一种组合方式,不妨认为该物品i没有被放入到了背包中,令i = i – 1, 重复步骤1)。
对于步骤2),如果
dp[i][j] == dp[i-1][j] && dp[i][j – weight(i)] + value(i) == dp[i][j]
说明物品i可以放入背包中(令i = i – 1, j = j – weight[i]),也可以不用放入背包中(令i = i - 1)。这里就产生分支,说明放入背包中的物品组合方式不唯一,为了简单起见,我们找到一种物品的组合方式即可。
package demo; import java.util.LinkedList; import java.util.List; public class KnapsacProblem { /*动态规划表*/ private int[][] dp; /*背包装的最大价值*/ private int maxVal; /*背包最大价值时对应的商品编号*/ private List<Integer> goodsNumber; public KnapsacProblem(int[] weight, int[] values, int capacity){ if ( weight.length != values.length ){ throw new IllegalArgumentException(); } int goodsLen = weight.length; /*第0列不使用*/ this.dp = new int[goodsLen][capacity + 1]; goodsNumber = new LinkedList<Integer>(); /*单独初始化第0行*/ for ( int j = 1; j < capacity + 1; j++){ if (j >= weight[0]){ dp[0][j] = values[0]; } } /*填dp表*/ for ( int i = 1; i < goodsLen; i++ ) { for ( int j = 1; j < capacity + 1; j++ ) { if ( weight[i] <= j ) { dp[i][j] = Math.max(dp[i-1][j], values[i] + dp[i-1][j - weight[i]]); } else { dp[i][j] = dp[i-1][j]; } } } maxVal = dp[goodsLen - 1][capacity - 1]; /*找出使用了哪些物品*/ int j = capacity; for (int i = goodsLen - 1; i > 0; i-- ) { if ( dp[i][j] > dp[i-1][j] ) { goodsNumber.add(i); j = j - weight[i]; } } /*单独处理第0行,回退到第0行时发现背包中还有物品,说明物品0在背包中*/ if (j > 0){ goodsNumber.add(0); } } public int getPackageMaxValue(){ return this.maxVal; } public List<Integer> getGoodsNumber(){ return this.goodsNumber; } public static void main(String[] args){ int[] weight = {4, 5, 2, 1, 2}; int[] values = {50, 40, 60, 20, 30}; int capacity = 10; KnapsacProblem kp = new KnapsacProblem(weight, values, capacity); System.out.println(kp.getPackageMaxValue()); System.out.println(kp.getGoodsNumber()); } }
运行结果
160 [4, 3, 2, 0]
如果我们仅仅需要知道最大的价值,不需要知道装了哪些物品,我们就可以对空间复杂度进行优化,动态规划表只需要一维,因为dp[i][?]仅和dp[i-1][?]有关。
3.5 切分“和相等”的子集
Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Note:
1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.
Example 1:
Input: [1, 5, 11, 5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
Example 2:
Input: [1, 2, 3, 5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
这是LeetCode的原题。这个问题本质上还是0-1背包问题,背包容量是数组之和的一半,物品的价值和体积是1比1的关系,额外条件是需要把背包装满。
3.6 完全背包问题
问题描述:有n 种物品,它们有各自的重量(weight)和价值(value),现有给定容量的背包,每种物品可以拿任意多个,如何让背包里装入的物品具有最大的价值,以及每种物品装了几个?
假设,我们还是利用0-1背包中的物品,背包容量为11。
完全背包问题也可以转化成0-1背包问题。因为第i个物品最多拿“背包重量/(物品i的重量)”个,也就是说在0-1背包问题中每个物品i占一行,完全背包问题中,每个物品占“背包重量/(物品i的重量)” 个行,按照这个思路显然已经能够解决这个问题。现在我们不把这个问题转化为0-1背包问题,而从这个问题的根源直接思考。
3.6.1 解决背包的最大价值
完全背包问题可以表述为
maxValue{宝石、剃须刀、ipad、充电宝、iphone | 背包容量10}
每个物品只有选和不选两种结果,我们不妨从第一个物品开始。如果选了宝石,那么问题转化为当前背包已有价值为50,并在剩下的背包容量(10 - 4)的前提下,继续在{宝石、剃须刀、ipad、充电宝、iphone}选取出最大的价值;如果不选宝石,那么我们就在{剃须刀、ipad、充电宝、iphone}中选择一种,那么问题转化为当前背包价值为0,并在剩下的背包容量10的前提下,再剩下的物品中即{剃须刀、ipad、充电宝、iphone }选取出最大的价值。
因此我们只需要选择:
50 + maxValue{宝石、剃须刀、ipad、充电宝、iphone | 背包容量6}
与
0 + maxValue{剃须刀、ipad、充电宝、iphone | 背包容量10}
中较大的那个。
而这就直接转化成两个子问题的求解,显然我们已经可以用分治的方式解决这个问题了。我们同样可以把递归树画出来,同样还会发现存在需要重复求解的子问题,为了避免子问题的重复求解,我们还是建立一张动态规划表,下次遇到重复的子问题,我们就直接查表。这里我们直接给出动态规划表,我们用一个名为dp的二维数组表示这张表,dp[0]行单独初始化,从dp[1]行开始填表,规则:从左到右,从上到下。
dp[i][j]表示前i个物品(包括物品i),在背包容量为j时能装的最大价值。
dp[i][j]为下面二者的最大值:
3.6.2 解决背包中物品的种类和个数
同样,从dp表中我们还可以知道哪些物品被选择了,选择多少次。我们还是从右下角开始回溯。
1)dp[i][j] > dp[i-1][j] 说明i号物品被选择了,j = j – weight[i]
2)dp[i][j] == dp[i-1][j] 为了简单起见,我们认为i号物品没有被选择,令i = i -1(实际上这里同样可能存在分支,即最大价值时物品的组合方式和数量并不唯一,我们这里为了简单处理,就不考虑这个问题了)。
package demo; import java.util.AbstractMap.SimpleEntry; import java.util.LinkedList; public class AllKnapsacProblem { private int maxVal; private LinkedList<SimpleEntry<Integer, Integer>> goodsIdCount; public int getPackageMaxValue(){ return maxVal; } public LinkedList<SimpleEntry<Integer, Integer>> getGoodsCount(){ return goodsIdCount; } public AllKnapsacProblem(int[] weight, int[] values, int capacity){ /*处理最大价值问题============================================*/ if ( weight.length != values.length ){ throw new IllegalArgumentException(); } int goodsLen = weight.length; /*第0列不使用*/ int[][] dp = new int[goodsLen][capacity + 1]; /*第0行单独处理*/ for (int j = weight[0]; j <= capacity; j++){ dp[0][j] = dp[0][j - weight[0]] + values[0]; } for (int i = 1; i < goodsLen; i++){ for (int j = 1; j <= capacity; j++){ int max1 = dp[i-1][j]; int max2 = j - weight[i] >= 0 ? values[i] + dp[i][j - weight[i]] : 0; dp[i][j] = Math.max(max1, max2); } } maxVal = dp[goodsLen-1][capacity]; /*处理物品种类和个数问题问题============================================*/ /*SimpleEntry<Integer, Integer>:key表示物品编号,value表示物品个数*/ goodsIdCount = new LinkedList<SimpleEntry<Integer, Integer>>(); int i = goodsLen - 1; int j = capacity; SimpleEntry<Integer, Integer> entry = new SimpleEntry<Integer, Integer>(i, 0); while (i > 0){ if (dp[i][j] > dp[i-1][j]){ int n = entry.getValue(); entry.setValue(n+1); j = j - weight[i]; } if (dp[i][j] == dp[i-1][j]){ if (entry.getValue() > 0) { goodsIdCount.add(entry); } i--; entry = new SimpleEntry<Integer, Integer>(i, 0); } } /*单独处理第0行*/ if (j > 0) { goodsIdCount.add(new SimpleEntry<Integer, Integer>(0, j/weight[0])); } } public static void main(String[] args){ int[] values = {50, 40, 60, 20, 30}; int[] weight = {4, 5, 2, 1, 2}; int capacity = 11; AllKnapsacProblem ap = new AllKnapsacProblem(weight, values, capacity); System.out.println("背包价值" + ap.getPackageMaxValue()); for (SimpleEntry<Integer, Integer> entry : ap.goodsIdCount) { System.out.printf("物品%d : %d个\n", entry.getKey(), entry.getValue()); } } }
运行结果
320 物品3 : 1个 物品2 : 5个
3.7 找零钱问题
You are given coins of different denominations ([dɪˌnɑ:mɪˈneɪʃn] 面额) and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1。
Example 1:
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:
Input: coins = [2], amount = 3
Output: -1
这道题目是LeetCode上面的原题。假设在一堆面值为 1,2,5,11面值的硬币,问最少需要多少个硬币才能找出总值为以兑换15元。面对这个问题我们也会首先想到贪心算法,但是贪心算法给出的组合方案为{11,1,1,1,1},但其实最优方案为{5,5,5}。如果使用枚举算法,每种硬币都有选0个,选1个,选2个,选…,这样时间复杂度太高。这个问题本质上还是完全背包问题,物品的价值和重量比是1比1,额外条件是需要把背包装满,所以我们可以使用动态规划算法去解决它,代码这里就不给出了。
3.8 最长公共子序列
我们首先看一下子序列的定义。假设给定一个字符串,我们抽取任意多个不超过字符串长度的字符,并保持它们的前后关系,这样的字符我们称之为子序列。对于字符串ABCDEFG而言, BEF、C、AG等等都是它的一个子序列。
Longest common sequence问题:给定两个字符串s1和s2,求这两个字符串中最长的公共子序列。比如给定两个字符串s1:bdcaba和s2:abcbdab,它们的公共子序列
长度为4,最长公共子序列是:bcba。
字符串s1的长度用n表示,字符产s2的长度用m表示,字符串s1和s2的最长公共字串用lcs(n,m)。那么这个问题可以转化为三个子问题
1)求lcs(n-1, m-1)
2)求lcs(n-1, m)
3)求lcs(n, m-1)
当我们求的上述三个子问题的答案,那么lcs(n, m)的结果就可以通过如下方式得到:
如果s1[n] == s2[m]
lcs(n, m) = lcs(n-1, m-1)+1
如果s1[n] != s2[m] :
lcs(n, m) = max{ lcs(n-1, m-1), lcs(n-1, m), lcs(n, m-1) }
但是实际上lcs(n,m)只要转化成两个子问题lcs(n-1, m)和lcs(n, m-1)就好了。
而子问题lcs(n-1, m-1)是没有必要的,因为lcs(n-1, m-1)必定小于等于lcs(n-1, m)和lcs(n, m-1)中的en任意一个。从常理上来说很好理解,不可能两个字符串中的任意一个变长了,公共子序列反而减少了。而本质上是由于lcs(n-1, m-1)也是lcs(n-1, m)和lcs(n, m-1)这两个问题的子问题。
通过上面的分析,我们把大的问题转化成小的问题,就可以通过递归(或者说分治)的方式把问题解决了,下面就是递归对应的代码。
public static void recursion (char[] s1, char[] s2) { maxLen = recursion0 (s1, s1.length-1, s2, s2.length-1); } private static int recursion0 (char[] s1, int idx1, char[] s2, int idx2){ if(idx1 < 0 || idx2 < 0){ return 0; } int max1, max2; max1 = recursion0 (s1, idx1, s2, idx2 - 1); max2 = recursion0 (s1, idx1 - 1, s2, idx2); if (s1[idx1] == s2[idx2]){ return Math.max(max1, max2) + 1; }else{ return Math.max(max1, max2); } }
显然上述也同样存在很多重复计算的子问题,为了降低时间复杂度,要一张二维表记录重复计算的子问题的结果,这张表我们用dp表示, dp[i][j]就表示以s1[i]和s2[j]结尾的字符串最长公共子序列。按照套路填表规则要从最小的子问题开始,
第0行,表示“b”和“bdcaba”的公共子序列,可以单独处理,同理第0列也可以单独处理,填表完成后如上图所示。从第二行开始,dp表按照从上到下,从左到右的填表顺序填表。根据子递归中子问题的定义,dp[i][j]的取值如下:
当填完整张表时,右下角的值就是公共子序列的最大长度。如果我们还需要知道公共子序列是什么,那么我们可以从右下角开始回溯,如果dp[i][j] > dp[i-1][j] 且 dp[i][j] > dp[i][j-1], 说明s1[i]或者s2[j]是公共子序列,否则选择走dp[i-1][j]和dp[i][j-1]中较大的那个,同样第0行要单独处理。
package demo; public class LongestCommonSequence { private int[][] dp; private int maxLen; private String lcs; private char[] s1, s2; public int maxLen(){ return maxLen; } public String getLCS() { return lcs; } public LongestCommonSequence(String str1, String str2) { s1 = str1.toCharArray(); s2 = str2.toCharArray(); dynamic(); getString(); } /*动态规划算法*/ private void dynamic(){ dp = new int[s1.length][s2.length]; /*单独处理第0行*/ for(int j = 0, x = 0; j < s2.length; j++){ if (s1[0] == s2[j]){ x = 1; } dp[0][j] = x; } /*单独处理第0列*/ for (int i = 0, x = 0; i < s1.length; i++) { if (s2[0] == s1[i]){ x = 1; } dp[i][0] = x; } for (int i = 1; i < s1.length; i++) { for(int j = 1; j < s2.length; j++){ if(s1[i] == s2[j]){ dp[i][j] = 1 + dp[i-1][j-1]; }else{ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } maxLen = dp[s1.length - 1][s2.length - 1]; } /*回溯求出公共子序列*/ private void getString(){ int cnt = maxLen; StringBuffer sb = new StringBuffer(); int i = s1.length - 1, j = s2.length - 1; while (i > 0 && j > 0){ if (dp[i][j] > dp[i-1][j] && dp[i][j] > dp[i][j-1]){ sb.append(s1[i]); i--; j--; cnt--; }else{ if (dp[i-1][j] > dp[i][j-1]){ i--; }else{ j--; } } } /*单独处理第0行, i和j必然有一个为0*/ if (cnt > 0){ while (true){ if (s1[i] == s2[j]){ sb.append(s1[i]); break; } if (i > 0){ i--; } if (j > 0){ j--; } } cnt--; } lcs = sb.reverse().toString(); } public static void main(String[] args){ LongestCommonSequence lcs = new LongestCommonSequence("bcba", "bdcaba"); System.out.println(lcs.maxLen); System.out.println(lcs.getLCS()); } }
4. 动态规划算法总结
枚举算法:如果为了方便的解决这个问题,我们需要将大问题化简成小问题,将所有小问题中的最优解作为我们解决大问题的基础。
贪心算法:如果为了方便的解决这个问题,我们需要将大问题化简成小问题,在所有小问题中,仅选择对当前最有利的小问题作为我们解决大问题的基础。
动态规划:如果为了方便的解决这个问题,我们需要将大问题化简成小问题,记录已解决过的小问题,将所有小问题中的最优解作为我们解决大问题的基础。换句话说,能用贪心算法解决的,动态规划算法也肯定能解决,反之不成立。
能用动规解决的问题的特点
1) 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有最优子结构性质。
2) 无后效性。当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关和之前是采取哪种手段或经过哪条路径演变到当前的这若干个状态,没有关系。
5. 参考内容
[1]. 动态规划:最长上升子序列(LIS)
[2]. 什么是动态规划?动态规划的意义是什么?
[3]. 漫画:什么是动态规划?
推荐阅读
-
epoll简介及触发模式(accept、read、send)-epoll的简单介绍 epoll在LT和ET模式下的读写方式 一、epoll的接口非常简单,一共就三个函数:1. int epoll_create(int size);创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大。这个参数不同于select中的第一个参数,给出最大监听的fd+1的值。需要注意的是,当创建好epoll句柄后,它就是会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close关闭,否则可能导致fd被耗尽。2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);epoll的事件注册函数,它不同与select是在监听事件时告诉内核要监听什么类型的事件,而是在这里先注册要监听的事件类型。第一个参数是epoll_create的返回值,第二个参数表示动作,用三个宏来表示:EPOLL_CTL_ADD:注册新的fd到epfd中;EPOLL_CTL_MOD:修改已经注册的fd的监听事件;EPOLL_CTL_DEL:从epfd中删除一个fd;第三个参数是需要监听的fd,第四个参数是告诉内核需要监听什么事,struct epoll_event结构如下:struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */};events可以是以下几个宏的集合:EPOLLIN :表示对应的文件描述符可以读(包括对端SOCKET正常关闭); EPOLLIN事件:EPOLLIN事件则只有当对端有数据写入时才会触发,所以触发一次后需要不断读取所有数据直到读完EAGAIN为止。否则剩下的数据只有在下次对端有写入时才能一起取出来了。现在明白为什么说epoll必须要求异步socket了吧?如果同步socket,而且要求读完所有数据,那么最终就会在堵死在阻塞里。 EPOLLOUT:表示对应的文件描述符可以写; EPOLLOUT事件:EPOLLOUT事件只有在连接时触发一次,表示可写,其他时候想要触发,那要先准备好下面条件:1.某次write,写满了发送缓冲区,返回错误码为EAGAIN。2.对端读取了一些数据,又重新可写了,此时会触发EPOLLOUT。简单地说:EPOLLOUT事件只有在不可写到可写的转变时刻,才会触发一次,所以叫边缘触发,这叫法没错的!其实,如果真的想强制触发一次,也是有办法的,直接调用epoll_ctl重新设置一下event就可以了,event跟原来的设置一模一样都行(但必须包含EPOLLOUT),关键是重新设置,就会马上触发一次EPOLLOUT事件。1. 缓冲区由满变空.2.同时注册EPOLLIN | EPOLLOUT事件,也会触发一次EPOLLOUT事件这个两个也会触发EPOLLOUT事件 EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);EPOLLERR:表示对应的文件描述符发生错误;EPOLLHUP:表示对应的文件描述符被挂断;EPOLLET: 将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。EPOLLONESHOT:只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);等待事件的产生,类似于select调用。参数events用来从内核得到事件的集合,maxevents告之内核这个events有多大,这个maxevents的值不能大于创建epoll_create时的size,参数timeout是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。-------------------------------------------------------------------------------------------- 从man手册中,得到ET和LT的具体描述如下EPOLL事件有两种模型:Edge Triggered (ET)Level Triggered (LT)假如有这样一个例子:1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符2. 这个时候从管道的另一端被写入了2KB的数据3. 调用epoll_wait(2),并且它会返回RFD,说明它已经准备好读取操作4. 然后我们读取了1KB的数据5. 调用epoll_wait(2)......Edge Triggered 工作模式:如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志,那么在第5步调用epoll_wait(2)之后将有可能会挂起,因为剩余的数据还存在于文件的输入缓冲区内,而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候,调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。在上面的例子中,会有一个事件产生在RFD句柄上,因为在第2步执行了一个写操作,然后,事件将会在第3步被销毁。因为第4步的读取操作没有读空文件输入缓冲区内的数据,因此我们在第5步调用 epoll_wait(2)完成后,是否挂起是不确定的。epoll工作在ET模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。最好以下面的方式调用ET模式的epoll接口,在后面会介绍避免可能的缺陷。 i 基于非阻塞文件句柄 ii 只有当read(2)或者write(2)返回EAGAIN时才需要挂起,等待。但这并不是说每次read时都需要循环读,直到读到产生一个EAGAIN才认为此次事件处理完成,当read返回的读到的数据长度小于请求的数据长度时,就可以确定此时缓冲中已没有数据了,也就可以认为此事读事件已处理完成。Level Triggered 工作模式相反的,以LT方式调用epoll接口的时候,它就相当于一个速度比较快的poll(2),并且无论后面的数据是否被使用,因此他们具有同样的职能。因为即使使用ET模式的epoll,在收到多个chunk的数据的时候仍然会产生多个事件。调用者可以设定EPOLLONESHOT标志,在 epoll_wait(2)收到事件后epoll会与事件关联的文件句柄从epoll描述符中禁止掉。因此当EPOLLONESHOT设定后,使用带有 EPOLL_CTL_MOD标志的epoll_ctl(2)处理文件句柄就成为调用者必须作的事情。然后详细解释ET, LT:LT(level triggered)是缺省的工作方式,并且同时支持block和no-block socket.在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表.ET(edge-triggered)是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once),不过在TCP协议中,ET模式的加速效用仍需要更多的benchmark确认(这句话不理解)。在许多测试中我们会看到如果没有大量的idle -connection或者dead-connection,epoll的效率并不会比select/poll高很多,但是当我们遇到大量的idle- connection(例如WAN环境中存在大量的慢速连接),就会发现epoll的效率大大高于select/poll。(未测试)另外,当使用epoll的ET模型来工作时,当产生了一个EPOLLIN事件后,读数据的时候需要考虑的是当recv返回的大小如果等于请求的大小,那么很有可能是缓冲区还有数据未读完,也意味着该次事件还没有处理完,所以还需要再次读取: 这里只是说明思路(参考《UNIX网络编程》) while(rs) {buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);if(buflen < 0){// 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读// 在这里就当作是该次事件已处理处.if(errno == EAGAIN)break; else return; }else if(buflen == 0) { // 这里表示对端的socket已正常关闭. } if(buflen == sizeof(buf) rs = 1; // 需要再次读取 else rs = 0; } 还有,假如发送端流量大于接收端的流量(意思是epoll所在的程序读比转发的socket要快),由于是非阻塞的socket,那么send函数虽然返回,但实际缓冲区的数据并未真正发给接收端,这样不断的读和发,当缓冲区满后会产生EAGAIN错误(参考man send),同时,不理会这次请求发送的数据.所以,需要封装socket_send的函数用来处理这种情况,该函数会尽量将数据写完再返回,返回-1表示出错。在socket_send内部,当写缓冲已满(send返回-1,且errno为EAGAIN),那么会等待后再重试.这种方式并不很完美,在理论上可能会长时间的阻塞在socket_send内部,但暂没有更好的办法. ssize_t socket_send(int sockfd, const char* buffer, size_t buflen) { ssize_t tmp; size_t total = buflen; const char *p = buffer; while(1) { tmp = send(sockfd, p, total, 0); if(tmp < 0) { // 当send收到信号时,可以继续写,但这里返回-1. if(errno == EINTR) return -1; // 当socket是非阻塞时,如返回此错误,表示写缓冲队列已满, // 在这里做延时后再重试. if(errno == EAGAIN) { usleep(1000); continue; } return -1; } if((size_t)tmp == total) return buflen; total -= tmp; p += tmp; } return tmp; } 二、epoll在LT和ET模式下的读写方式 在一个非阻塞的socket上调用read/write函数, 返回EAGAIN或者EWOULDBLOCK(注: EAGAIN就是EWOULDBLOCK) 从字面上看, 意思是: * EAGAIN: 再试一次 * EWOULDBLOCK: 如果这是一个阻塞socket, 操作将被block * perror输出: Resource temporarily unavailable 总结: 这个错误表示资源暂时不够, 可能read时, 读缓冲区没有数据, 或者, write时,写缓冲区满了 。 遇到这种情况, 如果是阻塞socket, read/write就要阻塞掉。 而如果是非阻塞socket, read/write立即返回-1, 同 时errno设置为EAGAIN. 所以, 对于阻塞socket, read/write返回-1代表网络出错了. 但对于非阻塞socket, read/write返回-1不一定网络真的出错了. 可能是Resource temporarily unavailable. 这时你应该再试, 直到Resource available. 综上, 对于non-blocking的socket, 正确的读写操作为: 读: 忽略掉errno = EAGAIN的错误, 下次继续读 写: 忽略掉errno = EAGAIN的错误, 下次继续写 对于select和epoll的LT模式, 这种读写方式是没有问题的. 但对于epoll的ET模式, 这种方式还有漏洞. epoll的两种模式 LT 和 ET
-
像首席技术官一样思考:如何高效管理 30 人的研发团队?-管理越多越轻松。好的研发团队,应该是上拨下用,即下级对上级的向上管理;而不是反过来,总是向下管理,甚至是 CTO 做经理的事,经理做工程师的事,工程师最终会被当成实习生。如果是这样,就会越管越累,不仅团队无法成长,而且团队整天很忙还效率低下,问题一大堆。 有这样一个小故事:一位高级经理下班后帮忙倒垃圾,结果被老板训斥了一顿。这就好比首席技术官做了实习生自己该做的事。事情本身没有对错之分,只是从不同的角度有不同的理解。 古人云:"用人不疑,疑人不用"。在面对自己的研发团队时,应该相信他们能做好,授权一线开发人员充分发挥专业特长,不要限制他们的工作。但在相信他们的同时,也要进行二次确认,始终秉持 "我相信,但我要确认 "的原则和严谨的精神。因为每个人都会犯错和疏忽,通过发挥团队的智慧,团队犯错的机会就会大大减少。比如回归测试、代码审查、开发演示、变更审批等等。 如前所述,每个人都难免会犯错。但作为管理者,你所设计和商定的流程不能出错。管理者的每一个决定和沟通都应该经过深思熟虑。就像红绿灯的交通设计,某辆车不小心闯红灯可能会扣分,但红绿灯的设计一定要正确、人性化、统一。再比如,开发人员可能会因为疏忽大意写出 bug,但研发流程的设计和上线流程的发布不能有任何差错。因此,流程体系的设计,一方面要结合当前团队规模、业务特点和需要重点解决的问题来设计,另一方面也要在人员防错、效率提升、发挥团队集体智慧等维度进行综合考量。应该站在更高更抽象的角度去思考,不断思考一个倍受欢迎的园区应该如何设计,思考一个灵动、经典、永恒的建筑应该遵循怎样的模式,思考一个成功、优秀、卓越的研发团队应该需要怎样的流程和制度。 最后,反馈很重要。向上汇报很重要,向下反馈也很重要。能够保持顺畅的双向反馈和闭环管理,对研发团队的协作和沟通有着非常明显的积极作用。在向上汇报方面,要培养团队在正式汇报、会议汇报、私下沟通、书面总结、非正式场合等方面的沟通能力,提醒下属报喜也要报忧。凡事先记录,再跟进,最后反馈。反馈很重要,主动汇报更难得。 另一方面,同时也不要忽视向下反馈。好的爱,是双向的。团队也是如此,没有严格的上下级之分,只是分工和角色不同而已。作为管理者,不必总保持一种 "神秘感",让人 "捉摸不透 "才是牛。当团队做得好或有人做得好时,要记得在公开或私下场合给予肯定和赞许。业务有增长、业绩有提升时,别忘了给团队一些鼓励,或者安排一次下午茶或聚餐。在例会或正式会议上,也可以同步向大家传达一些重要信息和高层指示。"欲速则不达,欲远则同行"。 当向上汇报、向下反馈的沟通闭环形成后,同时结合前面研发过程的管理闭环,双管齐下,就能形成良性循环。如此反复,持之以恒,优秀卓越的研发团队,必将呈现。 能力、产出和效率 接下来,继续重复关于能力、产出和效率的话题。 站在不同的角色,以及一个企业经营、生存和发展所需要的基础上,我把研发生产力分为三个层次,分别是:一线员工关心的研发能力、管理层关心的软件产出和操作人员关心的企业生产效率。简单概括就是:既要把工作做好,又要能出成果,还要能帮企业赚钱。
-
纯干货分享 | 研发效能提升——敏捷需求篇-而敏捷需求是提升效能的方式中不可或缺的模块之一。 云智慧的敏捷教练——Iris Xu近期在公司做了一场分享,主题为「敏捷需求挖掘和组织方法,交付更高业务价值的产品」。Iris具有丰富的团队敏捷转型实施经验,完成了企业多个团队从传统模式到敏捷转型的落地和实施,积淀了很多的经验。 这次分享主要包含以下2个部分: 第一部分是用户影响地图 第二部分是事件驱动的业务分析Event driven business analysis(以下简称EDBA) 用户影响地图,是一种从业务目标到产品需求映射的需求挖掘和组织的方法。 在软件开发过程中可能会遇到一些问题,比如大家使用不同的业务语言、技术语言,造成角色间的沟通阻碍,还会导致一些问题,比如需求误解、需求传递错误等;这会直接导致产品的功能需求和要实现的业务目标不是映射关系。 但在交付期间,研发人员必须要将这些需求实现交付,他们实则并不清楚这些功能需求产生的原因是什么、要解决客户的哪些痛点。研发人员往往只是拿到了解决方案,需要把它实现,但没有和业务侧一起去思考解决方案是否正确,能否真正的帮助客户解决问题。而用户影响地图通常是能够连接业务目标和产品功能的一种手段。 我们在每次迭代里加入的假设,也就是功能需求。首先把它先实现,再逐步去验证我们每一个小目标是否已经实现,再看下一个目标要是什么。那影响地图就是在这个过程中帮我们不断地去梳理目标和功能之间的关系。 我们在软件开发中可能存在的一些问题 针对这些问题,我们如何避免?先简单介绍做敏捷转型的常规思路: 先做团队级的敏捷,首先把产品、开发、测试人员,还有一些更后端的人员比如交互运维的同学放在一起,组成一个特训团队做交付。这个团队要包含交付过程中所涉及的所有角色。 接着业务敏捷要打通整个业务环节和研发侧的一个交付。上图中可以看到在敏捷中需求是分层管理的,第一层是业务需求,在这个层级是以用户目标和业务目标作为输入进行规划,同时需要去考虑客户的诉求。业务人员通过获取到的业务需求,进一步的和团队一起将其分解为产品需求。所以业务需求其实是我们真正去发布和运营的单元,它可以被独立发布到我们的生产环境上。我们的产品需求其实就是产品的具体功能,它是我们集成和测试的对象,也就是我们最终去部署到系统上的一个基本单元。产品需求再到了我们的开发团队,映射到迭代计划会上要把它分解为相应的技术任务,包括我们平时所说的比如一些前端的开发、后端的开发、测试都是相应的技术任务。所以业务敏捷要达到的目标是需要去持续顺畅高质量的交付业务价值。 将这几个点串起来,形成金字塔结构。最上层我们会把业务目标放在整个金字塔的塔尖。这个业务目标是通过用户的目标以及北极星指标确立的。确认业务目标后再去梳理相应的业务流程,最后生产。另外产品需求包含了操作流程和业务规则,具需求交付时间、工程时间以及我们的一些质量标准的要求。 谈到用户影响的地图,在敏捷江湖上其实有一个传说,大家都有一个说法叫做敏捷需求的“任督二脉”。用户影响地图其实就是任脉,在黑客马拉松上用过的用户故事地图其实叫督脉。所以说用户影响地图是在用户故事地图之前,先帮我们去梳理出我们要做哪些东西。当我们真正识别出我们要实现的业务活动之后,用户故事地图才去梳理我们整个的业务工作流,以及每个工作流节点下所要包含的具体功能和用户故事。所以说用户影响地图需要解决的问题,我们包括以下这些: 首先是范围蔓延,我们在整张地图上,功能和对应的业务目标是要去有一个映射的。这就避免了一些在我们比如有很多干系人参与的会议上,那大家都有不同想法些立场,会提出很多需求(正确以及错误的需求)。这个时候我们会依据目标去看这些需求是否真的是会影响我们的目标。 这里提到的错误需求,比如是利益相关的人提出的、客户认为产品应该有的、某个产品经理需求分析师认为可以有的....但是这些功能在用户影响地图中匹配不到对应目标的话,就需要降低优先级或弃掉。另外,通常我们去制定解决方案的时候,会考虑较完美的实现,导致解决方案括很多的功能。这个时候关键目标至关重要,会帮助我们梳理筛选、确定优先级。 看一下用户影响到地图概貌 总共分为一个三层的结构: 第一层why,你的业务目标哪个是最重要的,为什么?涉及到的角色有哪些? 第二层how ,怎样产生影响?影响用户角色什么样的行为? (不需要去列出所有的影响,基于业务目标) 第三层what,最关键的是在梳理需求时不需一次把所有细节想全,这通常团队中经常遇到的问题。 我们用这个例子来看一下 这是一个客服中心的影响地图,业务目标是 3个月内不增加客服人数的前提下能支持1.5倍的用户数。此业务目标设定是符合 smart 原则的,specific非常的具体,miserable 是可以衡量的,action reoriented是面向活动的, real list 也是很实际的。 量化的目标会指引我们接下来的行动,梳理一个业务目标,尽量去量化,比如 :我们通过打造一条什么样的流水线,能够提高整个部署的效率,时间是原来的 1/2 。这样才是一个能量化的有意义的目标。 回到这幅图, how 层级识别出来的内容,客服角色:想要对它施加的影响,把客户引导到论坛上,帮助客户更容易的跟踪问题,更快速的去定位问题。初级用户:方论坛上找到问题。高级用户:在论坛上回答问题。通过我们这些用户角色,进行活动,完成在不增加客户客服人数的前提下支持更多的用户数量。 最后一个层级,才是我们日常接触比较多的真正的功能的特性和需求,比如引导到客户到论坛上,其实这个产品就需要有一个常见问题的论坛的链接。这个层次需要我们团队进一步地在交付,在每个迭代之前做进一步的梳理,细化成相应的用户故事。 这个是云智慧团队中,自己做的影响地图的范例,可以看下整个的层级结构。序号表示优先级。 那我们用户影响地图可以总结为:
-
aps是什么意思_不同的富士APS-C画幅微单区别在哪里,档次是怎么划分的?-X-A系列原本指的是富士的入门级微单,最大的特点是没有使用富士X-Trans™CMOS 传感器,目前在售的有两款,分别是XA5和XA7。 富士(FUJIFILM)X-A5/XA5 15-45套机 富士(FUJIFILM)X-A7/XA7 15-45套机 目前这两款相机都处于历史最低价附近,XA5套机2699元,XA7套机3999元。XA5就是一个标准的入门级相机,定位就是时尚小巧自拍,在2699这个价位不要对它的性能有太多的奢求。 XA7价格来到了3999元,这就很有意思了,富士把入门型的相机价格推到了4000元,并且提供了自拍翻转屏和4K30P视频录制,这样一款相机就很有性价比了。 XE3是老款的中端相机,价格和入门级的XA7是一样的,都是3999元,这两款相机如何做选择呢?XE3有着更多的按键意味着更好的操控,但屏幕不是自拍翻转屏所以这点不如XA7好用。 要注意的是XE3用的是富士独有的X-Trans™CMOS III传感器,XA7是普通的2400万像素传感器,你可以理解为X-Trans才是富士的精髓。 富士(FUJIFILM)X-E3 15-45套机 当然,买新不买旧,XA7的新功能和自拍翻转屏可能会更适合你。 XT200是富士专门针对vlog市场推出的相机,其实之前的XA7也可以拍摄vlog,但XT200是富士官方宣传中的第一款vlog相机。数码防抖+3.5mm 麦克风口+自拍翻转屏+无裁切4K30P,这些都是XT200的优势,但这款相机也是普通的2400万像素传感器,没有用富士独有的X-Trans,可能是从价格角度考虑做了阉割吧。 富士(FUJIFILM)X-T200/XT200 微单相机 Vlog相机 富士XT30是我认为富士性价比最高的微单照相机,注意我说的是照相机。理由很简单,因为从拍照角度来看XT30和XTXT3几乎没有明显差距,主要是操控差了一些、视频性能大幅削弱,但好歹也是个有着双波轮+曝光补偿波轮+快门速度波轮的相机,操控方面不会太差的。视频方面也有着超采4K 30P的规格,支持F-log输出。 可以这么说,如果你只拍照,那么XT30是富士微单中性价比最高的,视频方面XT30也不差,只不过没有专业的10bit和4K60P而已。 富士(FUJIFILM)X-T30/XT30 15-45套机 XT3和XT4得放在一起说,这两款相机其实都挺好,420 10bit 4K60P的专业视频模式基本代表了APS-C画幅的上限水平。XT4还提升了电池续航增加了五轴防抖,配上富士独特的胶片滤镜,不管是拍照还是拍视频都非常优秀。 不要觉得这两款相机贵,同价位里能做到4K60P的微单也就是M43画幅的GGHGH5S,最便宜的G9机身也要7000多,这APS-C画幅的XT3机身接近8000也算合理价格范围内。除此之外的4K60P机身只有13998的松下S5和15999的佳能R6了。 富士(FUJIFILM)X-T3/XT3 1855套机 富士(FUJIFILM)X-T4/XT4 微单相机 套机(18-55mm) B站更新4K视频投稿后有很多人想拍摄4K升格,在很长一段时间里富士XT3和XT4是最优选,毕竟兼顾视频和拍照,对焦也还算能用。 X-Pro3和X-Pro2这两款微单可以算是旁轴相机,是富士官方意义上的旗舰级相机。从用料做工操控按键角度来说的确是旗舰级别,但视频性能方面只有4K30P,价格却比XT3还贵,可能这就是旁轴情怀带来的溢价吧。 富士(FUJIFILM)X-Pro3 微单相机 机身 黑色 我在之前的文章里提过很多次,有一些相机属于如果你想买你压根不会看测评,如果你犹豫那么这款相机不适合你,为什么这么说,因为有一些比较小众的相机可能在性能上并不好,但独特的外形、操控、体积、传承赋予了它独特的定位。譬如富士X-Pro系列微单就是旁轴的电子化,理光GR传承大师的扫街理念,尼康DF的外形源自胶片时代的相机,这些相机就不是针对大多数消费者的,定位就是小众。所以我说喜欢就买,不要考虑什么性能规格。 X100系列相机是一款不可换镜头的等效35mm旁轴数码相机,从外形看就是经典的复古造型。这两款相机和X-Pro3一样,如果你喜欢那就买,别犹豫, 你在市场上找不到同类型的其他数码相机,徕卡Q是28mm,索尼RX1R系列是35mm但外形不够复古,X100系列就是独特的你没有其他选择。 那么X100F和X100V该如何选择呢?X100F的镜头很一般甚至算不上好,如果我没记错的话和初代的X100是同款镜头,X100V的镜头是全新制作的很棒,X100V的机身性能也和XTX-Pro3差不多。 富士(FUJIFILM)X100F 数码相机 旁轴 2430万像素 富士(FUJIFILM)X100V 数码相机 旁轴 2610万像素 还是那句话,这两款相机也是那种如果你喜欢那就毫不犹豫下单的类型,而且这两款相机也没有竞品。 以前不推荐富士的原因是原厂镜头太贵,现在唯卓仕给富士出了四款可以自动对焦的大光圈镜头,覆盖35到130mm的焦段,可以基本满足人像摄影爱好者的需求。拍风景的话国产很多镜头厂商都有富士卡口的手动镜头可以选择,从这个角度来说富士微单就非常值得入手了。 和友商竞品相比:
-
Spring IOC 的简单理解和创建对象的方法
-
刘韧工作手册(2023年版)-17 共同学习,共同进步,搭建共识。一起工作的基础,是对彼此能力的认可,继续一起工作的基础,是能力的共同提高。共同进步的基础,就是共同学习,共同学习的基础,是看过同样的书。 年轻时,男女谈恋爱,双方世界观趋同,差距不大。后来,世界观逐渐拉大,对话成了鸡同鸭讲,我讲,你听不懂。你讲,我不感兴趣,甚至闹离婚,双方自然而然走不下去了。工作也一样,同事间如果差距越来越大,最终,无法一起工作。 我为了和别人搭建共识,会处心积虑向其推荐读书。听什么歌,观什么电影,看什么书,能在一定程度了解一个人。 有人说,金庸的书是文学。我说,那是娱乐。文学是“真、善、美”,首先是要“真”,就是情感真实。而在金庸的小说里,类似“九阴真经”、“葵花宝典”的秘籍是假的,小说里的人物寻得秘籍,一夜之间就能武功猛增……这样的情节,在现实中可能吗?生活中,漂亮的富家女黄蓉会爱上傻小子郭靖吗?金庸看多了,人会追求走捷径,工作生活“走捷径”会害死自己。 18 礼物,是人际交往中的情感润滑剂。互相送礼物,增进感情。不知道买什么,就买吃的。 英国人做客,会送主人红酒、鲜花和小卡片,回家后,会写感谢信。在新加坡,朋友们来家,常带些做好的熟食,大家一起吃。 2000年,我听说谷歌在办公室给员工备吃的。当时不太理解,后来才知道,“在一起吃”这个行为,有助于消除紧张和敌意,人更容易感到温暖和轻松,更愿意敞开心扉,是社交中增进感情的好方式之一。脸书新加坡总部,午餐,公司会请高级厨师做六种风格的菜,每一道菜都做的极好,甚至比五星级酒店的饭菜都好吃。他们的员工告诉我,根本不想回家,就想在公司吃饭。 19 坦诚,不装懂,打破沙锅问到底。想当然半天,不如简单试一下。要学会积攒各种低成本测试方法,并勤快地去试。超大额跨国汇款,先汇1元,测试路径是否畅通。没有招,没有策略库,一筹莫展。 有句古话,叫“以其昏昏,使人昭昭”。很多人对“学而优则仕”这句话的理解,是典型的“以其昏昏,使人昭昭”。这句话常被人解释为“学习好了就去当官”,若照此解释,下一句“仕而优则学”只能解释为“当官当好了就去学习”!这显然说不通。这里的“优”,不是“优秀”,而是“空闲”的意思。很多人不清楚,却到处教人解释这句话。 《水浒传》是中国版的黑帮小说,讲的是厚黑学,没有道德底线。梁山人为了拉扈三娘入伙,杀光了她全家,把原本是千金小姐,花容月貌的扈三娘指婚丑陋的王英。直到今天,《水浒传》常被解释为“侠义”。 在群里,遇到信口雌黄国学的人,我会问他们,论语中,第一句话“学而时习之不亦说乎”中的“习”是什么意思?很多人解释为“复习”。其实,繁体字中,“习”的写法是“習”,下面一个“白”,上面一个“羽”,指的是“雏鸟学飞”。意思是,雏鸟利用老鸟教的技巧,终于飞起来了。因此,“习”的本意是指老师手把手把心得教给你,让你学会了,有了收获和进步,绝不是指反复“复习”和“练习”的意思。 维特根斯坦说:“凡是可说的就要说清楚,凡是不可说的就该保持沉默。”别不懂装懂。 20 善待帮助你的人。一个人能否成功,要看有没有人愿意帮你。有多大成功,要看有多少人愿意帮你。 别人发现你出错了,提醒你,这些都是你所能得到的“举手之劳”的帮助,你知道了,能改掉,你容易成长。 如何做一个有很多人愿意帮你的人呢? 首先,滴水之恩,当涌泉相报。每次收到礼物,我一定会表示感谢。 其次,得到帮助,一定要反馈。很多帮助不一定非得要你用物质来交换,可能仅仅是你要领情。我会记录所有受到的帮助,并广而告之。我写书时,会把帮助我的人都列举出来,这样做成本不高,但被提到的人会感动。 你们可以回忆一下,有多少人帮过你?如果脱口说出的人数越多,说明你离成功越近。要是发现世界上,愿意帮你的人只有父母,那就要反思了。(完) 刘韧商业写作通识
-
用C语言自定义函数快速找到三个数中的最大值,简单、高效且易懂方法
-
人人都在偷偷用的神器!别错过推特视频下载的超简单方法~
-
用新方法解锁Linux内核,简单上手操作系统
-
用Java简易理解地实现排列与组合方法