java数据结构03

1.动态规划

如果使用上面的递归函数进行计算，会导致如下的重复计算：

示例：

1.1实战示例1

从一个列表中选出一堆（若干）不相邻的数字，使这些数字相加的和最大。

package datastruct.t05dynamic_programming;

public class DynamicProgramming {
    /**
     * 递归方式
     * 
     * @param arr：数组
     * @param i：第i个位置
     * @return
     */
    public static int recOpt(int[] arr, int i) {
        if (i == 0)
            return arr[0];
        if (i == 1)
            return Math.max(arr[0], arr[1]);
        else {
            int A = recOpt(arr, i - 2) + arr[i];
            int B = recOpt(arr, i - 1);
            return Math.max(A, B);
        }
    }

    /**
     * 非递归的方式
     */
    public static int dpOpt(int[] arr) {
        int[] opt = new int[arr.length];
        opt[0] = arr[0];
        opt[1] = Math.max(arr[0], arr[1]);
        for (int i = 2; i < arr.length; i++) {
            int A = opt[i - 2] + arr[i];
            int B = opt[i - 1];
            opt[i] = Math.max(A, B);
        }
        return opt[arr.length - 1];
    }

    public static void main(String[] args) {
        int[] arr = { 1, 2, 4, 1, 7, 8, 3 };
        int res = recOpt(arr, arr.length - 1);
        System.out.println(res);
        int res2 = dpOpt(arr);
        System.out.println(res2);
    }

}

1.2实战示例2

从某一数组里找出两个数字的和正好等于给定的数字，如果存在返回true，不存在返回false。

package datastruct.t05dynamic_programming;

public class Subset {
    /**
     * 递归的方式实现
     */
    public static boolean recSubset(int[] arr, int i, int target) {
        if (target == 0) {
            return true;
        } else if (i == 0) {
            return arr[0] == target;
        } else if (arr[i] > target) {
            return recSubset(arr, i - 1, target);
        } else {
            boolean A = recSubset(arr, i - 1, target - arr[i]);
            boolean B = recSubset(arr, i - 1, target);
            return A || B;
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 34, 4, 12, 5, 2 };
        int target1 = 9;
        int target2 = 10;
        int target3 = 13;
        boolean res1 = recSubset(arr, arr.length - 1, target1);
        boolean res2 = recSubset(arr, arr.length - 1, target2);
        boolean res3 = recSubset(arr, arr.length - 1, target3);
        System.out.println(res1);
        System.out.println(res2);
        System.out.println(res3);
    }

}

package datastruct.t05dynamic_programming;

public class Subset {

    /**
     * 非递归方式实现
     */
    public static boolean dpSubset(int[] arr, int target) {
        boolean[][] subset = new boolean[arr.length][target + 1];
        // 所有行，第0列
        for (int i = 0; i < subset.length; i++) {
            subset[i][0] = true;
        }
        // 第0行，所有列
        for (int j = 0; j < subset[0].length; j++) {
            subset[0][j] = false;
        }
        subset[0][arr[0]] = true;
        
        for (int i = 1; i < subset.length; i++) {
            for (int s = 1; s < subset[0].length; s++) {
                if (arr[i] > s) {
                    subset[i][s] = subset[i - 1][s];
                } else {
                    boolean A = subset[i - 1][s - arr[i]];
                    boolean B = subset[i - 1][s];
                    subset[i][s] = A || B;
                }
            }
        }
        return subset[subset.length-1][subset[0].length-1];
    }

    public static void main(String[] args) {
        int[] arr = { 3, 34, 4, 12, 5, 2 };
        int target1 = 9;
        int target2 = 10;
        int target3 = 13;
    
        boolean res4 = dpSubset(arr, target1);
        boolean res5 = dpSubset(arr, target2);
        boolean res6 = dpSubset(arr, target3);
        System.out.println(res4);
        System.out.println(res5);
        System.out.println(res6);
    }

}