算法分析设计-动态规划

一. 动态规划（Dynamic programm）

1.什么是动态规划

动态规划，英文是Dynamic Programming，简称DP，擅长解决“多阶段决策问题”，利用各个阶段阶段的递推关系，逐个确定每个阶段的最优决策，并最终得到原问题的最优决策。

2.动态规划的适用条件

一个问题的求解可以拆分为若干个阶段的子问题。
问题的最优解依赖于子问题的最优解。
一个问题的求解过程中，其子问题可能会重复出现。（如斐波那锲数列子问题重复太多，导致时间复杂度高，所以动态规划需要规避重复）

二. 跳跃游戏

1.题目描述

给定一个非负整数数组，你最初位于数组的第一一个位
置。数组中的每个元素代表你在该位置可以跳跃的最
大长度。判断你是否能够到达最后一个位置。

数组1： 2 3 1 1 4

数组2：3 2 1 0 4

2.暴力求解（Brute ）

//暴力求解法
//思路：遍历每一个位置，找到该位置可以跳的所有位置，打上标记
//缺点：有的位置可能多次被打上标记，浪费时间
public static boolean canJumpByBruteForce(int[] nums){
    //记录每一个位置是否可以跳
    boolean[] reachable = new boolean[nums.length];
    //第一个位置默认是可以跳的
    reachable[0] = true;

    //枚举每一个位置，给每个位置可以跳到的位置打上标记
    for (int i = 0; i < nums.length - 1; i++) {
        //判断当前位置是否可以到达
        if (reachable[i]){
            //找到当前位置可以跳的所有位置（不能越界），打上标记
            for (int j = 1; j <= nums[i] && i+j < nums.length; j++) {
                reachable[i+j] = true;
            }
        }
    }

    return reachable[nums.length-1];
}

时间复杂度最坏情况下：

每一个位置跳的长度都是从当前位置当最后的位置：(n-2)+(n-3)+…+1 => O(n²)

3.动态规划（Dynamic programming）

//动态规划
//思路：主要解决了暴力求解可能多次打上标记的问题
//倒着跳，从倒数第二个位置开始跳看是否能跳到第一个（子问题：第二个能否跳到第一个也倒着跳）
//不能的话从倒数第三个位置开始跳看是否能跳到第一个
//...
//这样就避免了重复打标记的问题
public static boolean canJumpByDp(int[] nums){
    return canJump(nums,nums.length-1);
}

//能否从第tail+1个位置跳到第一个位置
public static boolean canJump(int[] nums, int tail){
    //递归结束的条件
    //判断是否跳到了第一个
    if (tail == 0){
        return true;
    }

    //依次倒着跳，找到结果就跳出来
    for (int i = tail-1; i >= 0; i--){
        //判断当前位置是否可以跳到上一个位置
        if (nums[i] + i >= tail) {
            //慢慢跳
            return canJump(nums,i);
        }
    }

    //代码进入到这里肯定没成功
    return false;
}

时间复杂度：θ(n)

倒着跳，平均每个位置经过依次。

4.巧妙解法

//巧妙解法：不能出现 "0" 点
//两个选择：1.不能出现0点
//        2.该0点可以被跳掉
public static boolean canJumpByZeroPoint(int[] nums){
  //数组长度
  int n = nums.length;

  //是否有0点,默认状态-1,没有0点
  int zeroPoint = -1;

  //从倒数第二个位置开始
  for (int i = n-2; i >= 0; i--) {
    //判断当前位置是不是0点
    if (nums[i] == 0){
      //存在0点
      //首先记录第一个0点
      //如果之后出现了可以跳过的点
      //那么就算之间出现的新的0点
      //也会被跳过去，无需考虑
      //
      //如果跳不过去，白搭
      if (zeroPoint == -1){
        //设置0点的位置
        zeroPoint = i;
      }
    }else if (zeroPoint != -1) {
      //当前位置不是0点，且之前有0点，检查是否能跳过
      if (i + nums[i] > zeroPoint) {
        zeroPoint = -1;
      }
    }

  }

  return zeroPoint == -1;
}

三. 最大子串和问题

例:最佳投资时机
假设你已经预测到未来几期的股票市场价格，在这期间你只能买卖一次，请问你该在何时买何时卖?

Day	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Price	100	113	110	85	105	102	86	63	81	101	94	106	101	79	94	90	97

1.暴力求解（Brute force）

/**
 * 暴力求解
 * @param prices
 * @return
 */
public static int[] getByBruteForce(int[] prices) {
    //存储 最大收益 购买时间 卖出时间的变量
    int maxSum = 0,startIndex = 0,endIndex = 0;

    //遍历每一种情况
    for (int i = 0; i < prices.length - 1; i++) {
        for (int j = i+1; j < prices.length; j++) {
            //如果收益超过了当前的最大值 更换最大值
            if (prices[j] - prices[i] > maxSum){
                maxSum = prices[j] - prices[i];
                startIndex = i;
                endIndex = j;
            }
        }
    }

   return new int[]{maxSum,startIndex,endIndex};
}

时间复杂度：θ(n²)

2.分治法（Divide and conquer）

/**
 * 分治求解
 * @param prices
 * @return
 */
static int[] getByDivideConquer(int[] prices) {
    //将每天的资金数据转化为当天和前一天的数据差->最大子串和问题
    int[] changes = new int[prices.length-1];
    for (int i = 0; i < changes.length; i++) {
        changes[i] = prices[i+1]-prices[i];
    }

    return maxSubArray(changes,0,changes.length-1);
}

/**
 * 求解最大子数组
 * @param changes
 * @param head
 * @param tail
 * @return
 */
private static int[] maxSubArray(int[] changes, int head, int tail){
    //存储 最大收益 购买时间 卖出时间的变量
    int maxSum = 0,startIndex = 0,endIndex = 0;

    //如果只有一个元素
    if (head == tail){
        maxSum = changes[head];
        startIndex = head;
        endIndex = tail;

        return new int[]{maxSum,startIndex,endIndex};
    }

    //分治处理
    int middle = (head+tail) / 2;

    //左右数组的最大值
    int[] maxLeft = maxSubArray(changes,head,middle);
    int[] maxRight = maxSubArray(changes,middle+1,tail);

    //找出最大值
    if (maxLeft[0] > maxRight[0]){
        maxSum = maxLeft[0];
        startIndex = maxLeft[1];
        endIndex = maxLeft[2];
    }else {
        maxSum = maxRight[0];
        startIndex = maxRight[1];
        endIndex = maxRight[2];
    }

    //包含左右子数组的最大值
    int[] maxTwoSide = maxTwoSide(changes,head,tail,middle);

    //继续找
    if (maxTwoSide[0] > maxSum){
        maxSum = maxTwoSide[0];
        startIndex = maxTwoSide[1];
        endIndex = maxTwoSide[2];
    }

    return new int[]{maxSum,startIndex,endIndex};
}

/**
 * 求解包含左右子数组的最大值
 * @param changes
 * @param head
 * @param tail
 * @param middle
 * @return
 */
private static int[] maxTwoSide(int[] changes, int head, int tail, int middle) {
    //存储 最大收益 购买时间 卖出时间的变量
    int maxSum = 0,startIndex = 0,endIndex = 0;

    //如果只有一个元素
    if (head == tail){
        maxSum = changes[head];
        startIndex = head;
        endIndex = tail;

        return new int[]{maxSum,startIndex,endIndex};
    }

    //记录当前的和
    int currentSum = 0;

    //从索引处向左扩展
    int leftSum = Integer.MIN_VALUE;
    for (int i = middle; i >= head; i--) {
        currentSum += changes[i];

        if (leftSum < currentSum){
            leftSum = currentSum;

            startIndex = i;
        }
    }

    //从索引处向右扩展
    currentSum = 0;
    int rightSum = Integer.MIN_VALUE;
    for (int i = middle+1; i <= tail; i++) {
        currentSum += changes[i];

        if (rightSum < currentSum){
            rightSum = currentSum;

            endIndex = i;
        }
    }

    //最大收益
    maxSum = leftSum + rightSum;

    return new int[]{maxSum,startIndex,endIndex};
}

类似于平面内最近点对的思想，但是更简单一点。

3.动态规划（Dynamic programming）

/**
 * 动态规划求解
 * @param prices
 * @return
 */
public static int[] getByDynamicProgramming(int[] prices) {
    //将每天的资金数据转化为当天和前一天的数据差->最大子串和问题
    int[] changes = new int[prices.length-1];
    for (int i = 0; i < changes.length; i++) {
        changes[i] = prices[i+1]-prices[i];
    }

    //存储 最大收益 购买时间 卖出时间的变量
    int maxSum = changes[0],startIndex = 0,endIndex = 0;

    //累计收益
    int currentMaxSum = changes[0];

    //遍历每一个位置
    for (int currentIndex = 1; currentIndex < changes.length; currentIndex++){
        //如果累计收益不是正的
        if (currentMaxSum <= 0) {
            //重新计算收益
            currentMaxSum = changes[currentIndex];

            //更改起始位置
            startIndex = currentIndex;
        }else {
            //收益累加
            currentMaxSum += changes[currentIndex];
        }

        //如果累计收益大于最大收益
        if (currentMaxSum > maxSum){
            //重新计算最大收益
            maxSum = currentMaxSum;

            //更改结束位置
            endIndex = currentIndex;
        }
    }

    return new int[]{maxSum,startIndex,endIndex};
}

假设只有前两天有买卖机会，最多赚多少钱?

假设只有前三天有买卖机会，最多赚多少钱?

假设只有前四天有买卖机会，最多赚多少钱?

。。。。

	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
价格变化	13	-3	-25	20	-3	16	-23	18	20	-7	12	-5	-22	15	-4	7
当前累积	13	10	0	20	17	1	0	18	38	31	43	38	16	31	27	34
最大收益	13	13	13	20	20	20	20	20	38	38	43	43	43	43	43	43

这样就将大问题化解为分阶段的小问题，使用动态规划。

时间复杂度：θ(n)（每个位置都经过一次）

四. 切木材问题

1.题目描述

给一个长度为17的木材，可以切成小段卖出去，价格根据小段的长度不同而不同。

Length	i	1	2	3	4	5	6	7	8	9	10
Price	pi	1	4	5	7	10	17	17	20	24	30

如何通过切成小段卖出尽可能高的总价钱?

2.动态规划（Dynamic programming）
|Length |i |1 |2 |3 |4 |5 |6 |7 | 8 | 9 |10|
|:—:|:—:|:—:|:—:|:—:|:—:|:—:|:—:|:—:|:—:|:—:|:—:|
|Price| pi| 1 |4| 5| 7 |10 |17 |17| 20 |24| 30|
|Value |vi | 1 |4| 5| 8| 10 |17| 18| 21| 24 |30|

Length	i	11	12	13	14	15	16	17
Value	vi	31	34	35	38	41	47	48

① 表格法：自下而上

时间复杂度：θ(n²)

for (int i = 1; i < rod_length; i++) {
    for (int j = 0; j < i / 2; j++) { }
}

1/2 * 1 + 1/2 * 2 + 1/2 * 3 + … + 1/2 * n = 1/2 * 1/2 * n(1+n) = 1/4 * (n<sup>2</sup> + n) = θ(n<sup>2</sup>)

② 备忘录法：自上而下

/**
 * 切木头问题 动态规划
 */
public class RodCut {
    /**
     * 表格法：自下而上
     * @param cut_value
     * @param rod_length
     * @return
     */
    public static int getValueByTabulation(int[] cut_value, int rod_length){
        //存储每一个子阶段的最大价值
        int[] rod_value = new int[rod_length];

        //长度为1的木头价值就是其本身
        rod_value[0] = cut_value[0];

        //依次求解之后每个子阶段的最大值
        for (int i = 1; i < rod_length; i++) {
            //因为有可能最大的cut_value < rod_length
            //所以需要判断能不能不切直接卖
            rod_value[i] = cut_value[Math.min(i,cut_value.length-1)];

            //依次比较
            for (int j = 0; j <= i-j-1; j++) {
                rod_value[i] = Math.max(
                        rod_value[i],
                        rod_value[j] + rod_value[i-j-1]
                );
            }
        }

        return rod_value[rod_length-1];
    }

    /**
     * 备忘录法：自上而下
     * @param cut_value
     * @param rod_length
     * @return
     */
    public static int getValueByMemoization(int[] cut_value, int rod_length){
        //存储每一个子阶段的最大价值
        int[] rod_value = new int[rod_length];

        //长度为1的木头价值就是其本身
        rod_value[0] = cut_value[0];

        return getValueByMemoization(cut_value, rod_length, rod_value);
    }

    //重载
    private static int getValueByMemoization(int[] cut_value, int rod_length, int[] rod_value) {
        //递归结束条件
        if (rod_value[rod_length-1] > 0) return rod_value[rod_length-1];

        //因为有可能最大的cut_value < rod_length
        //所以需要判断能不能不切直接卖
        rod_value[rod_length-1] = cut_value[Math.min(rod_length-1,cut_value.length-1)];

        //依次比较
        for (int j = 0; j <= (rod_length-1) - j -1; j++) {
            rod_value[rod_length-1] = Math.max(
                    rod_value[rod_length-1],
                    getValueByMemoization(cut_value,j+1,rod_value) +
                    getValueByMemoization(cut_value,rod_length-j-1,rod_value)
            );
        }

        return rod_value[rod_length-1];
    }
}

package swu.xl.algorithm.code_04_21.experiment_1;

public class RodCutTest {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] cut_value = {1, 4, 5, 7, 10, 17, 17, 20, 24, 30};
		int rod_length = 17;
		System.out.println(RodCut.getValueByTabulation(cut_value,rod_length));
		System.out.println(RodCut.getValueByMemoization(cut_value,rod_length));
	}
}

//运行结果
48
48

五.最长公共子序列

1.题目描述

求解 X (A,B,C,B,D,A,B) Y (B,D,C,A,B,A) 的最长公共子序列

2.代码

① 表格法：自下而上

时间复杂度：θ(n²)

求出一个表格的所有位置 m*n

② 备忘录法：自上而下

package swu.xl.algorithm.code_04_21.experiment_2;

/**
 * 最长公共子序列
 */
public class LCS {
    /**
     * 表格法：自下向上
     * @param str1
     * @param str2
     * @return
     */
    public static String getLCSByTabulation(String str1, String str2) {
        //表格的行数和列数
        int row_num = str1.length();
        int col_num = str2.length();

        //表格的数据结构
        int[][] board = new int[row_num][col_num];

        //表格的第一行，第一列元素
        board[0][0] = (str1.charAt(0) == str2.charAt(0)) ? 1 : 0;

        //初始化第一列元素
        for (int i = 1; i < row_num; i++) {
            board[i][0] = (str1.charAt(i) == str2.charAt(0) || board[i-1][0] == 1) ? 1 : 0;
        }

        //初始化第一行元素
        for (int i = 1; i < col_num; i++) {
            board[i][0] = (str1.charAt(0) == str2.charAt(i) || board[0][i-1] == 1) ? 1 : 0;
        }

        //初始化表格其他位置的元素
        for (int i = 1; i < row_num; i++) {
            for (int j = 1; j < col_num; j++) {
                if (str1.charAt(i) == str2.charAt(j)){
                    board[i][j] = board[i-1][j-1] + 1;
                }else {
                    board[i][j] = Math.max(
                            board[i-1][j],
                            board[i][j-1]
                    );
                }
            }
        }

        //逆着找到一个最长字符串

        //模拟指针
        int i = row_num - 1;
        int j = col_num - 1;

        //存储找到的字符串
        StringBuilder lcs = new StringBuilder();

        //寻找
        while (i != 0 && j != 0){
            if (board[i][j] == board[i-1][j]){
                i--;
            }else if (board[i][j] == board[i][j-1]){
                j--;
            }else {
                lcs.insert(0, str1.charAt(i));
                i--;j--;
            }
        }
        lcs.insert(0, str1.charAt(i));

        return lcs.toString();
    }

    /**
     * 备忘录法：自上向下
     * @param str1
     * @param str2
     * @return
     */
    public static String getLCSByMemoization(String str1, String str2){
        //表格的行数和列数
        int row_num = str1.length();
        int col_num = str2.length();

        //表格的数据结构
        int[][] board = new int[row_num][col_num];

        //模拟指针
        int i = row_num - 1;
        int j = col_num - 1;

        //存储找到的字符串
        StringBuilder lcs= new StringBuilder();

        //逆着找
        while(i != 0 && j != 0){
            board[i][j] = getLCSByMemoization(board, str1, str2, i, j);
            board[i-1][j] = getLCSByMemoization(board, str1, str2, i-1, j);
            board[i][j-1] = getLCSByMemoization(board, str1, str2, i, j-1);

            if (board[i][j] == board[i-1][j]) {
                i--;
            } else if (board[i][j] == board[i][j-1]) {
                j--;
            } else {
                lcs.insert(0, str1.charAt(i));
                i--;j--;
            }
        }
        lcs.insert(0, str1.charAt(i));

        return lcs.toString();
    }

    //重载
    private static int getLCSByMemoization(int[][] board, String str1, String str2, int m, int n){
        if(m < 0 || n < 0) return 0;

        if(board[m][n] != 0){
            return board[m][n];
        }

        if(str1.charAt(m) == str2.charAt(n)){
            board[m][n] = 1 + getLCSByMemoization(board, str1,str2,m-1,n-1);
        }else{
            return Math.max(
                    getLCSByMemoization(board, str1,str2,m-1,n),
                    getLCSByMemoization(board, str1,str2,m,n-1)
            );
        }

        return board[m][n];
    }
}

package swu.xl.algorithm.code_04_21.experiment_2;

public class LCSTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String str1 = "ABCBDAB";
		String str2 = "BDCABA";
		System.out.println(LCS.getLCSByTabulation(str1,str2));
		System.out.println(LCS.getLCSByMemoization(str1,str2));
	}
}

//运行结果
BDAB
BCBA

表格法和备忘录法的区别

表格法：每个子问题都要求解一次，但不会重复求解子问题。自底向上。

备忘录法：只求解哪些确实需要解的子问题。自顶向下。

六. 最短路径问题

1.题目描述

2.代码

时间复杂度：θ(m²)

public class ShortestPath {
    /**
     * 最短路径问题（有向无环图）
     * @param routes
     * @param distances
     * @param origin
     * @param destination
     * @return
     */
    public static LinkedList<String> getByDP(
            HashMap<String, LinkedList<String>> routes,
            HashMap<String, LinkedList<Integer>> distances,
            String origin, String destination) {

        //存储到达某一个点的最短距离的上一个点的信息
        HashMap<String, String> shortest_routes = new HashMap<>();
        //存储到达某一个点的最短距离
        HashMap<String, Integer> shortest_distances = new HashMap<>();

        //加入起点边信息 起点不需要存储点信息
        shortest_distances.put(origin,0);

        //创建队列
        Queue<String> q = new LinkedList<>();
        //加入第一个点
        q.add("A");

        //所有的点的最短路径求完
        while (q.peek() != null){
            //取出队列首元素
            String node = q.remove();

            //求解出当前点可以到达点的距离信息
            if (routes.get(node) != null){
                //将当前点可以到达的所有下一个点放到队列中
                q.addAll(routes.get(node));

                //依次求解当前点到它可以到达的所有点的距离
                //可能1：这个点没有到达过，直接填入求解的值
                //可能2：这个点到达过，需要判断能否更短
                for (int i = 0; i < routes.get(node).size(); i++) {
                    //取得当前点要到达的点
                    String toNode = routes.get(node).get(i);

                    //取出距离
                    int dist = distances.get(node).get(i);

                    //可能1 还没有到达 直接加入
                    if (!shortest_distances.containsKey(toNode)){
                        shortest_routes.put(toNode,node);
                        shortest_distances.put(toNode,shortest_distances.get(node) + dist);
                    }else {
                        //可能2 到达过 判断能否更短
                        if (shortest_distances.get(toNode) > shortest_distances.get(node) + dist){
                            shortest_routes.put(toNode,node);
                            shortest_distances.put(toNode,shortest_distances.get(node) + dist);
                        }
                    }
                }
            }
        }

        //返回路径
        LinkedList<String> route = new LinkedList<>();
        route.add(destination);
        while (shortest_routes.get(route.get(0)) != null){
            route.add(0,shortest_routes.get(route.get(0)));
        }

        return route;
    }
}

七. 矩阵连乘问题

1.题目描述

口 A是一个5x3的矩阵
口 A2是-一个3x4的矩阵
口 A3是一个4x2的矩阵
口 A4是一个2x7的矩阵
口 A5是一个7x5的矩阵
口求矩阵连乘 A = A1A2A3A4A5的最优计算次序和所需的乘法次数?

2.代码

public class MatrixChainMultiplication {
    /**
     * 求解矩阵连续乘的问题
     * @param dims
     * @return
     */
    public static int getMinMultiplicationNum(int[] dims){
        //表格的长度
        int n = dims.length-1;

        //记录连乘结果最小值的表格
        int[][] tab_num = new int[n][n];

        //记录连乘结果最小值时，划分的界限的后一个位置
        int[][] tab_split = new int[n][n];

        //求解出表格
        for (int j = 1; j < n; j++){
            for (int i = j-1; i >= 0; i--){
                //先确认num表的初值
                tab_num[i][j] = tab_num[i][j-1] + dims[i] * dims[j] * dims[j+1];
                //再确认split表的初值
                tab_split[i][j] = j;

                //从所有可能中找到最小的
                for (int k = i+1; k < j; k++){
                    //记录新的一种搭配的值
                    //前半段：tab_num[i][k-1]
                    //后半段：tab_num[k][j]
                    int temp = tab_num[i][k-1] + tab_num[k][j] +  dims[i] * dims[k] * dims[j+1];

                    //判断是不是更优解
                    if (temp < tab_num[i][j]){
                        tab_num[i][j] = temp;
                        tab_split[i][j] = k;
                    }
                }
            }
        }

        //打印两个表格的数据
        for (int i = 0; i < tab_num.length; i++) {
            for (int j = 0; j < tab_num[0].length; j++) {
                String str = String.format("%-3s", tab_num[i][j]);
                System.out.print(str+"  ");
            }
            System.out.println();
        }
        System.out.println();
        for (int i = 0; i < tab_split.length; i++) {
            for (int j = 0; j < tab_split[0].length; j++) {
                String str = String.format("%-3s", tab_split[i][j]);
                System.out.print(str+"  ");
            }
            System.out.println();
        }

        //递归求解结果
        trackBack(tab_split,0,n-1);
        System.out.println();

        return tab_num[0][n-1];
    }

    /**
     * 递归求解分割方法
     * @param tab_split
     * @param head
     * @param tail
     */
    private static void trackBack(int[][] tab_split, int head, int tail) {
        if (head == tail) {
            System.out.print("A"+(head+1));
        }
        else {
            System.out.print("(");
            trackBack(tab_split,head,tab_split[head][tail]-1);
            trackBack(tab_split,tab_split[head][tail],tail);
            System.out.print(")");
        }
    }
}

八. 背包问题

1.题目描述

2.代码

package swu.xl.algorithm.code_04_28.experiment_3;

import java.util.LinkedList;

class Knapsack {
    /**
     * 01背包问题-表格法
     * @param items
     * @param capacity
     * @return
     */
    public static LinkedList<Integer> getByTabulation(int[][] items, int capacity) {
        //物品的个数
        //item 是一个二维数组 第一个值是占据的空间 第二个值是其价值
        int n = items.length;

        //前多少件物品和剩余空间求解最大价值的表格
        //tab[前多少件物品][空间] = 最大价值
        int[][] tab = new int[n+1][capacity+1];

        //依次填表
        //注意：这里的i和c都是序号不是索引
        for (int i = 1; i <= n; i++) {
            for (int c = 1; c <= capacity; c++) {
                //如果还可以装的下
                if (c - items[i-1][0] >= 0){
                    //是否装入该物品
                    tab[i][c] = Math.max(
                            tab[i-1][c],
                            tab[i-1][c-items[i-1][0]] + items[i-1][1]
                    );
                }else {
                    tab[i][c] = tab[i-1][c];
                }
            }
        }

        //求解出装入背包的是那几项
        LinkedList<Integer> packedItems = new LinkedList<>();
        int c = capacity;
        for (int i = n; i > 0; i--) {
            //说明装入该物品
            if (tab[i][c] != tab[i-1][c]){
                packedItems.add(0,i);
                c = c - items[i-1][0];
            }
        }

        return packedItems;
    }
}

九. 凸多边形最优三角剖分问题

1.题目描述

2.代码

public class Edge {
    int point1;
    int point2;

    public Edge(int point1, int point2) {
        this.point1 = point1;
        this.point2 = point2;
    }
}

public class Answer {
    public LinkedList<Edge> partition;
    public double minCost;

    public Answer(LinkedList<Edge> partition, double minCost) {
        this.partition = partition;
        this.minCost = minCost;
    }
}

public class MinTriagulation {
    /**
     * 计算给定的三个点组成的三角形的边长
     * @param points
     * @param i
     * @param j
     * @param k
     * @return
     */
    private static double cost(double[][] points, int i, int j, int k){
        return Math.sqrt(Math.pow(points[i][0]-points[k][0],2) + Math.pow(points[i][1]-points[k][1],2)) +
                Math.sqrt(Math.pow(points[i][0]-points[j][0],2) + Math.pow(points[i][1]-points[j][1],2)) +
                 Math.sqrt(Math.pow(points[j][0]-points[k][0],2) + Math.pow(points[j][1]-points[k][1],2));
    }

    /**
     * 求解凸多边形最优三角剖分问题
     * @param points
     * @return 返回剖分方案和最小剖分成本
     */
    public static Answer getPartition(double[][] points) {
        //多边形点的个数 或者 边数
        int n = points.length;

        //表格法的剖分成本表
        double[][] tab_cost = new double[n][n];
        //表格法的剖分方案表
        int[][] tab_split = new int[n][n];

        //求解表格
        for (int j = 2; j < n; j++) {
            for (int i = j-2; i >= 0; i--){
                //设置默认值
                tab_cost[i][j] = Double.MAX_VALUE;

                //求解某一个位置的最佳值 可能有很多种方案
                for (int k = i + 1; k <= j-1; k++){

                    if (tab_cost[i][j] > (cost(points,i,j,k) + tab_cost[i][k] + tab_cost[k][j]) || tab_cost[i][j] == 0){
                        tab_cost[i][j] = cost(points,i,j,k) + tab_cost[i][k] + tab_cost[k][j];
                        tab_split[i][j] = k;
                    }
                }
            }
        }

        //求解剖分方案
        LinkedList<Edge> partition = new LinkedList<>();
        trackback(tab_split,partition,0,n-1);

        return new Answer(partition,tab_cost[0][n-1]);
    }

    /**
     * 求解剖分方案
     * @param tab_split
     * @param partition
     * @param i
     * @param j
     */
    private static void trackback(int[][] tab_split, LinkedList<Edge> partition, int i, int j) {
        if (j-i > 2){

            if (j - tab_split[i][j] == 1){
                partition.add(new Edge(i,tab_split[i][j]));

                trackback(tab_split,partition,i,tab_split[i][j]);
            }

            if (tab_split[i][j] - i == 1){
                partition.add(new Edge(tab_split[i][j],j));

                trackback(tab_split,partition,tab_split[i][j],j);
            }
        }
    }
}

//测试代码
public class MinTriagulationTest {
    public static void main(String[] args) {
        double[][] points = {{0, 0}, {1, 0}, {2, 1}, {1, 2}, {0, 2}};
        Answer ans = MinTriagulation.getPartition(points);
        for(Edge e : ans.partition) {
            System.out.println("point" + e.point1 + " ---- point" + e.point2);
        }
        System.out.println(ans.minCost);
    }
}

//运行结果
point1 ---- point4
point1 ---- point3
15.30056307974577

十. 最优二叉树搜索问题

1.题目描述

2.代码

public class OptimalBinarySearchTree {
    /**
     * 求解最优二叉搜索树
     * @param key_probability 数据概率
     * @param dummy_probability 间隙概率
     * @return 返回最小成本，并打印动态规划的分支矩阵
     */
    public static double getMinCost(double[] key_probability, double[] dummy_probability) {
        //连续概率表
        int n = dummy_probability.length;
        double[][] tab_continue = new double[n][n];
        initContinueTab(tab_continue,key_probability,dummy_probability);
        //for (int i = 0; i < tab_continue.length; i++) {
            //for (int j = 0; j < tab_continue[0].length; j++) {
                //System.out.print(tab_continue[i][j]+" ");
            //}
            //System.out.println();
        //}

        //搜索成本表
        double[][] tab_search = new double[n][n];
        //分叉结点表
        int[][] tab_node = new int[n][n];
        //填入数据
        for (int i = 0; i < n; i++) {
            tab_search[i][i] = dummy_probability[i];
        }
        for(int j=1;j<n;j++){
            for(int i=j-1;i>=0;i--){
                tab_search[i][j] = Double.MAX_VALUE;
                for(int k=i+1;k<=j;k++){
                    if(tab_search[i][j]>tab_search[k][j]+tab_search[i][k-1]+tab_continue[i][j]){
                        tab_search[i][j]=tab_search[k][j]+tab_search[i][k-1]+tab_continue[i][j];
                        tab_node[i][j]=k;
                    }
                }
            }
        }

        //node
        for (int i = 0; i < tab_node.length; i++) {
            for (int j = 0; j < tab_node[0].length; j++) {
                System.out.print(tab_node[i][j]+" ");
            }
            System.out.println();
        }

        return tab_search[0][n-1];
    }

    /**
     * 初始化连续概率表
     * @param tab_continue
     * @param key_probability
     * @param dummy_probability
     */
    private static void initContinueTab(double[][] tab_continue, double[] key_probability, double[] dummy_probability) {
        //先输入对角线的值
        int n = dummy_probability.length;
        for (int i = 0; i < n; i++)
            tab_continue[i][i] = dummy_probability[i];

        //依次填入其他部分的值
        for (int j = 1; j < n; j++){
            for (int i = j-1; i >= 0; i--){
                //System.out.println("i:"+i+" j:"+j);
                for(int p = i; p <= j; p++){
                    tab_continue[i][j] += dummy_probability[p];

                    if (p != i){
                        tab_continue[i][j] += key_probability[p-1];
                    }
                }
            }
        }
    }
}

//测试代码
public class OptimalBinarySearchTreeTest {
    public static void main(String[] args) {
        double[] key_probability = {0.15, 0.1, 0.05, 0.1, 0.2} ;
        double[] dummy_probability = { 0.05, 0.1, 0.05, 0.05, 0.05, 0.1};
        double cost = OptimalBinarySearchTree.getMinCost(key_probability,dummy_probability);
        System.out.println(cost);
    }
}

//运行结果
0 1 1 2 2 4 
0 0 2 2 2 4 
0 0 0 3 4 5 
0 0 0 0 4 5 
0 0 0 0 0 5 
0 0 0 0 0 0 
2.7500000000000004