a. 证明：可能的接缝的数量是m的指数函数，假定n>1。
第一行：n种可能选取像素点
第二行到m行：每行有2到3种可能选中A[i][j-1],A[i][j],A[i][j+1];当j=1或者j=n时，有2种可能。所以接缝数量：n*.
b. 设计算法，寻找破坏度最低的接缝。分析算法的时间复杂度。
算法设计描述：
c[i, j]记录接缝走到当前像素的最低破坏度，r[i, j]记录当前结点来自于上一行的那个像素（用-1,0,1分别表示左上，正上和右上方向）。
从第一行开始，c[i, j]只有当前像素的破坏度，直接赋值即可；
第i行，每个像素的上一个像素来源一共有三个，左上、正上和右上方，每次计算c[i, j]时，需要去三种情况中破坏度最低的情况然后加上当前像素的破坏度，就是接缝走到当前像素的最低破坏度。同时更新r[i, j].
第n行，接缝走到这里结束，在第n行找出最小值，c[i, j]即为最低的破坏度，通过r[i, j]向上走，直到第一行，所经的路径即为破坏度最小的接缝。
解释：
递归
递归
最后结果
代码实现：
package seamCarving;
public class Main {
public static int row = 3,col = 5;
private static int min(int[][] sum, int location, int j) {
int temp=0;
if(j==1)
temp = sum[location-1][j]>sum[location-1][j+1]?sum[location-1][j+1]:sum[location-1][j];
else if (j==col) {
temp = sum[location-1][j]>sum[location-1][j-1]?sum[location-1][j-1]:sum[location-1][j];
}else {
if(sum[location-1][j]>sum[location-1][j-1]){
temp = sum[location-1][j-1];
if(sum[location-1][j-1]>sum[location-1][j+1])
temp = sum[location-1][j+1];
}
else{
temp = sum[location-1][j];
if(sum[location-1][j]>sum[location-1][j+1])
temp = sum[location-1][j+1];
}
}
return temp;
}
private static void print(int[][] sum, int i, int temp) {
int t;
if (i==0) {
return ;
}else {
if(temp==col)
t = sum[i][temp]>sum[i][temp-1]?temp-1:temp;
else if (temp==1) {
t = sum[i][temp]>sum[i][temp+1]?temp+1:temp;
}else {
if (sum[i][temp]>sum[i][temp-1]) {
t=temp-1;
if (sum[i][temp-1]>sum[i][temp+1])
t=temp+1;
}
else{
t=temp;
if(sum[i][temp]>sum[i][temp+1])
t=temp+1;
}
}
}
print(sum, i-1, t);
System.out.println("第 "+i+" row;第 "+t+" col像素点;");
}
//删除 A[i-1][j-1] A[i-1][j] A[i-1][j+1]中的任意一个像素点
//递推式：A[i][j] = d[i][j]+min{A[i-1][j-1],A[i-1][j],A[i-1][j+1]}
private static void seam_carving(int[][] d) {
int[][] sum=new int[row+1][col+1];
int location=1;
for (location = 1; location <=col; location++) {
sum[1][location]=d[1][location];
}
for (location = 2; location <=row; location++) {
for (int j = 1; j <=col; j++) {
sum[location][j]=d[location][j]+min(sum,location,j);
}
}
int min_init = Integer.MAX_VALUE,temp=0;
for (location = 1; location <= col; location++) {
if(sum[row][location]<min_init){
min_init=sum[row][location];
temp=location;
}
}
System.out.println("min的破坏点之和为："+min_init);
print(sum,row,temp);
//for (location = 0; location <=col; location++)
//sum[location]=null;
//sum=null;
}
public static void main(String[] args) {
int d[][] = new int[row+1][col+1];
//int[][] data={{0,0,0,0,0,0},{0,3,2,2,3,3},{0,1,2,1,2,1},{0,3,2,1,3,1},{0,2,1,1,2,2},{0,1,2,2,3,3},{0,2,2,2,1,1}};
int[][] data={{0,0,0,0,0,0},{0,1,4,3,5,2},{0,4,3,8,4,5},{0,8,5,7,6,5}};
for (int j = 0; j <=row; j++) {
for (int k = 0; k <= col; k++) {
d[j][k] = data[j][k];
}
}
seam_carving(d);
}
}
输入：
int[][] data={{0,0,0,0,0,0},{0,1,4,3,5,2},{0,4,3,8,4,5},{0,8,5,7,6,5}};
输出：
min的破坏点之和为：9
第 1 row;第 1 col像素点;
第 2 row;第 2 col像素点;
第 3 row;第 2 col像素点;
参考：
https://blog.csdn.net/yuan3683084/article/details/35994157
https://blog.csdn.net/z84616995z/article/details/38562467
