挑战程序竞赛系列（1）：2.3动态规划

用户1147447

发布于 2019-05-26 09:43:45

2820

发布于 2019-05-26 09:43:45

文章被收录于专栏：机器学习入门机器学习入门

2.3记录结果再利用的动态规划

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

POJ 3176: Cow Bowling

水题，思路题目已经告诉你，不需要自己找递推式。

public class SolutionDay02_P3176 {

    static int N = 350;
    static int[][] dp = new int[N][N];
    static int[][] score = new int[N][N];
    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        for (int i = 0; i < n; i++){
            for (int j = 0; j <= i; j++){
                score[i][j] = in.nextInt();
            }
        }

        dp[0][0] = score[0][0];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0){
                    dp[i][0] = dp[i-1][0] + score[i][j];
                    continue;
                }
                if (j == i){
                    dp[i][j] = dp[i-1][j-1] + score[i][j];
                    continue;
                }
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-1]) + score[i][j];
            }
        }

        int max = 0;
        for (int j = 0; j < n; j++){
            max = Math.max(max,dp[n-1][j]);
        }

        System.out.println(max);

        in.close();
    }

POJ 2229: Sumsets

递推式：

i 偶数: dp[i] = dp[i/2] + dp[i-1];
i 奇数: dp[i] = dp[i-1];

递推思路，i递增后，相当于把所有的1加在了最前方，而当i为奇数时，无法构成新的2的幂，当i为偶数时，能多出一部分解，而多出的那部分解即为dp[i/2]的值。

public class SolutionDay02_P2229 {

    static int MAX_N = 1000000;
    static int[] dp = new int[MAX_N+1];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        dp[0] = 1;
        for (int i = 1; i <= n;i++){
            if ((i & 0x01) == 0){
                dp[i] = dp[i/2];
            }
            dp[i] += dp[i-1];
            dp[i] %= 1000000000;
        }
        System.out.println(dp[n]);
        in.close();
    }
}

POJ 2385: Apple Catching

O(n)O(n)阶段，多状态问题。注意阶段和状态的区分。状态：

int[][][] dp = new int[T][W][P];

表示在第T阶段，现状态为移动了W次且在位置P处的最优解。

那么无非就是在一个阶段中30*2 = 60种状态下取最优。递推式分为四种情况：

//1. 当前不移动，且能吃到苹果 （停留在原地，为了吃苹果）
//2. 移动，且吃不到当前苹果 （为了后续最大考虑，虽然吃不到当前苹果，但没准未来是最优的选择之一）
//3. 当前不移动，且吃不到当前苹果 （同2）
//4. 移动，且能吃到苹果 （切换树，为了吃苹果）

简单来说，就是对这四种情况的状态都得存下，为了后续求解最优。代码如下：

public class SolutionDay02_P2385 {
    static int MAX_T = 1000;
    //防止dp越界
    static int[][][] dp = new int[MAX_T][32][2];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        int W = in.nextInt();

        int[] nums = new int[T];
        for (int i = 0; i < T; i++){
            nums[i] = in.nextInt();
        }

//      int[] nums = {2,1,1,2,2,1,1};
//      int W = 2;

        //阶段0 移动0次 位置1时 最大值
        dp[0][0][0] = nums[0] == 1 ? 1 : 0;

        //阶段0 移动1次 位置2时 最大值
        dp[0][1][1] = nums[0] == 1 ? 0 : 1;

        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j <= W; j++) {
                for (int k = 1; k <= 2; k++) {
                    if (k == nums[i]){
                        // not move and eat
                        dp[i][j][k-1] = Math.max(dp[i][j][k-1], dp[i-1][j][k-1] + 1);
                        // move and not eat
                        dp[i][j+1][move(k)-1] = Math.max(dp[i][j+1][move(k)-1], dp[i-1][j][k-1]);
                    }else{
                        // not move and not eat
                        dp[i][j][k-1] = Math.max(dp[i][j][k-1], dp[i-1][j][k-1]);
                        // move and eat
                        dp[i][j+1][move(k)-1] = Math.max(dp[i][j+1][move(k)-1], dp[i-1][j][k-1]+1);
                    }
                }
            }
        }
        System.out.println(Math.max(dp[nums.length-1][W][0],dp[nums.length-1][W][1]));
    }

    private static int move (int n){
        return n == 1 ? 2 : 1;
    }
}

POJ 3616: Milking Time

最大值产生在生成过程当中，递推式相当简单。

dp[i] = Math.max(dp[i],dp[j]+efficiency[i])

但该递推式需要符合j.endTime + R >= i.startTime，代码如下：

public class SolutionDay02_P3616 {
    static int MAX_M = 1000;
    static int[] dp = new int[MAX_M];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int R = in.nextInt();

        Interval[] intervals = new Interval[M];
        for (int i = 0; i < M; i++){
            int start = in.nextInt();
            int end = in.nextInt();
            int eff = in.nextInt();
            intervals[i] = new Interval(start, end, eff);
        }

//      int M = 4;
//      int R = 2;
//      Interval[] intervals = new Interval[M];
//      intervals[0] = new Interval(1, 2, 8);
//      intervals[1] = new Interval(10, 12, 19);
//      intervals[2] = new Interval(3, 6, 24);
//      intervals[3] = new Interval(7, 10, 31);

        Arrays.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start != o2.start ? o1.start-o2.start : o1.end - o2.end;
            }
        });

        for (int i = 0; i < M; i++){
            dp[i] = intervals[i].efficiency;
            for (int j = 0; j < i; j++){
                if (intervals[j].end + R <= intervals[i].start){
                    dp[i] = Math.max(dp[i],intervals[i].efficiency+dp[j]);
                }
            }
        }

        int max = 0;
        for (int i = 0; i < M; i++){
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
        in.close();
    }
}

class Interval{
    int start;
    int end;
    int efficiency;

    Interval(int start,int end,int efficiency){
        this.start = start;
        this.end = end;
        this.efficiency = efficiency;
    }
}

POJ 3280: Cheapest Palindrome

区间DP，在做leetcode时，也遇到了很多相关的回文DP，题目的意思是让我们求删和加得到最新回文的代价最小。

3 4
abcb
a 1000 1100
b 350 700
c 200 800

如abcb有很多种做法如1. abcba 2. bcbabcb，在这里显然bcbabca最小。

主要思想：

遍历顺序：

i = 0
ab       删a -> b    加a -> aba
abc      删a -> bc   加a -> abca
abcb     删a -> bcb  加a -> abcba
## "bc"可以被看成已经进行回文操作。

j = M - 1
ab       删b -> a    加b -> bab
abc      删c -> ab   加c -> cabc
abcb     删b -> abc  加b -> babcb
## "ab","abc"均可以被看成已经进行回文操作。

判断条件：（ss[i] == ss[j]）首尾元素相等，可以忽略不看。

public class SolutionDay02_P3280 {

    static int[] cost = new int[26];
    //static int[][] dp = new int[2048][2048];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        String s = in.next();

        int[][] dp = new int[M][M];

        for (int i = 0; i < N; i++){
            char c = in.next().charAt(0);
            int add = in.nextInt();
            int delete = in.nextInt();
            cost[c-'a'] = Math.min(add, delete);
        }

//      int N = 3;
//      int M = 4;
//      String s = "abcb";
//      
//      cost[0] = 1000;
//      cost[1] = 350;
//      cost[2] = 200;

        char[] ss = s.toCharArray();
        for (int i = M - 1; i >= 0; i--) {
            for (int j = i + 1; j < M; j++) {
                dp[i][j] = Math.min(dp[i + 1][j] + cost[ss[i] - 'a'], 
                        dp[i][j - 1] + cost[ss[j] - 'a']);
                if (ss[i] == ss[j]) {
                    dp[i][j] = Math.min(dp[i][j], dp[i + 1][j - 1]);
                }
            }
        }

        System.out.println(dp[0][M-1]);
    }
}

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017年05月02日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度