动态规划题目总结

题目1：

输出描述:

对于每组数据，输出一个整数，代表最长递增子序列的长度（不需要连续）。

输入例子:

2
7
89 256 78 1 46 78 8
5
6 4 8 2 17

输出例子:

3
3
package dynamatic;
import java.util.Scanner;
public class D1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            //1.初始化
            int count = in.nextInt();      
            for (int i=0; i<count; i++) {
                int length = in.nextInt();
                int[] array = new int[length];
                int[] values = new int[length];
                for (int j=0; j<length; j++) {
                    array[j] = in.nextInt();
                }
                findMaxSLength(array, values);
            }
        }
    }
     //1.深度优先搜索
    public static void findMaxSLength(int[] array, int[] values) {       
        int length = array.length;
        for (int i=0; i<length; i++) {
            if (i==0) {
                values[i] = 1;
            } else {
                int max = 0;
                for (int j=i-1; j>=0; j--) {
                    if (array[j] < array[i]) {
                        //2.关键的判断value[]--[1, 1, 2, 1, 3]在此基础上判断，倒推，动态更新
                        int temp = values[j] + 1;
                        if (temp > max) {
                            max = temp;
                        }
                    }
                    values[i] = max == 0?1:max;
                }                
            }
        }        
        int max=0;
        for (int k : values) {
            if (k>max) {
                max = k;
            }
        }
        System.out.print(max);    
    }
}

变化

输入例子:

2
7
89 256 78 1 46 78 8
5
6 4 8 2 17

输出例子:

1 46 78
6 8 17
package dynamatic;
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class D22 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int size = in.nextInt();
            for (int i = 0; i < size; i++) {
                int len = in.nextInt();
                int[] data = new int[len];
                for (int j = 0; j < len; j++) {
                    data[j] = in.nextInt();
                }
                lisB(data);
            }
        }
        in.close();
    }
    public static  void lisB(int[] array) { //dp时间复杂度（o(n2)）
        //边界判断
        ArrayList<Integer> result = new ArrayList<>();
        if(array == null || array.length == 0) return;
        int length = array.length;
        //存储各个位置
        ArrayList<ArrayList<Integer>> buffer = new ArrayList<>();//每个索引下的最大子序列长度列
        //DFS
        for(int i = 0; i < length; i++) {
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(array[i]);
            buffer.add(temp);
            for(int j = i - 1; j >= 0; j--) {                
                if(array[i] > array[j] && buffer.get(i).size() <= buffer.get(j).size()) {  //j < i && array[j] < array[i]
                    buffer.set(i,new ArrayList<Integer>(buffer.get(j)));   //
                    buffer.get(i).add(array[i]);
                }
            }
            if(result.size() < buffer.get(i).size()) {
                result = buffer.get(i);
            }
        }
        for (int j = 0; j < result.size(); j++) {
            if (j==result.size()-1) {
                System.out.print(result.get(j));
            }else {
                System.out.print(result.get(j)+" ");
            }
        }
       // return result;
    }
}

2.求CD个数

你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ？

输入描述:

每组测试用例仅包含一组数据，每组数据第一行为三个正整数 n, s, L。 保证 n ≤ 100 , s ≤ L ≤ 10000

输出描述:

输出一个整数代表你至少需要的 CD 数量。

输入例子:

7 2 6

输出例子:

4
package dynamatic;
import java.util.*;
public class D4CD{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();//歌曲总数
            int s = in.nextInt();//每首哥的时间
            int l = in.nextInt();//CD容量
            int count = (l+1)/(s+1);//每张容纳多少歌曲---都加一个空，看为整体（最大值）
            count = Math.min(n, count);//防止歌曲过少
            if(count%13==0){
                count--;
            }
            int sum = n/count;//需要多少CD
            int yu = n%count;//余数！！！！最后一个专辑剩下的歌曲
            /*
             * yu是最后一张专辑的歌曲数，如果yu是13的倍数，为了不增加专辑的数量，---没张容纳》13
             * 我们可以考虑从倒数第二张专辑中借一首歌，此时倒数第二张专辑的歌曲数是count-1，
             * 若(count-1)==yu，这种情况只能在多出一张专辑。不知道有没有讲明白？我的表述有点不到位，防止最后count-1为13倍数。
             * 
             * */
            if(yu!=0){
                sum++;
                if(yu%13==0&&(count-yu)==1){//查看最后最后一张专辑的情况
                    sum++;
                }
            }
            System.out.println(sum);
        }
    }
}

3.背包问题

小萌是个WOW发烧友，每天都痴迷于他的法师号。精诚所至金石为开，小萌穿越到WOW的世界中了…
初来乍到的小萌在暴风城的小巷中，遇见了一位善良的德鲁伊。德鲁伊听了小萌的故事，打算帮助他在WOW这个世界好好活下去，于是，把自己的东西都给了小萌了…
德鲁伊的东西太多了，于是小萌去拍卖行买了几个包裹，一切妥当之后，小萌开始把东西装进包裹里。
不过，因为小萌穿越时候脑袋先着地，所以脑子不好用，每次他拿起一个物品，要不装进包里，要不就直接扔掉…
而且，一个背包一旦不往里装东西，小萌就会封上口不再用…
现在，告诉你小萌每个物品的体积，背包的个数和容量，以及小萌拿物品的顺序，你要帮助小萌求出他能拿走多少东西。

输入描述:

输入的第一行为一个整数T，代表测试数据组数。
  第一行：三个正整数 N、T、M。 分别表示物品的个数，背包的容量，背包个数。
  第二行：N个数。表示每个物品的体积。
  保证：
  1<=N,T,M<=20,0<=vi<=30

输出描述:

对于每组数据，输出一个整数，代表小萌可以拿走的最多物品个数。

输入例子:

2
5 5 2
4 3 4 2 1

输出例子:

3
package dynamatic;
import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
public class D22 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int size = in.nextInt();
            for (int i = 0; i < size; i++) {
                int len = in.nextInt();
                int[] data = new int[len];
                for (int j = 0; j < len; j++) {
                    data[j] = in.nextInt();
                }
                lisB(data);
            }
        }
        in.close();
    }
    public static  void lisB(int[] array) { //dp时间复杂度（o(n2)）
        //边界判断
        ArrayList<Integer> result = new ArrayList<>();
        if(array == null || array.length == 0) return;
        int length = array.length;
        //存储各个位置
        ArrayList<ArrayList<Integer>> buffer = new ArrayList<>();//每个索引下的最大子序列长度列
        //DFS
        for(int i = 0; i < length; i++) {
            ArrayList<Integer> temp = new ArrayList<>();
            temp.add(array[i]);
            buffer.add(temp);
            for(int j = i - 1; j >= 0; j--) {                
                if(array[i] > array[j] && buffer.get(i).size() <= buffer.get(j).size()) {  //j < i && array[j] < array[i]
                    buffer.set(i,new ArrayList<Integer>(buffer.get(j)));   //
                    buffer.get(i).add(array[i]);
                }
            }
            if(result.size() < buffer.get(i).size()) {
                result = buffer.get(i);
            }
        }
        for (int j = 0; j < result.size(); j++) {
            if (j==result.size()-1) {
                System.out.print(result.get(j));
            }else {
                System.out.print(result.get(j)+" ");
            }
        }
       // return result;
    }
}

例4数石子：找规律

Alice 和 Bob 在玩一个取石子的游戏，有 n 堆石子，第 i 堆有 ai 个石子，两个人轮流行动，Alice 先手。每个人每次行动必须选择一堆非空的石子，拿走其中的一部分石子，谁不能行动谁就输了。

他们玩过很多次这个游戏之后都觉得太无聊了，于是决定给游戏增加一个要求：当某个人要拿第 i 堆中的石子时必须要保证第 1 .. i-1 堆的石子都已经拿光了。也就是说两个人必须先拿光第 1 堆中的石子，然后再拿第 2 堆的，第 3 堆的……以此类推。

所以现在问在这个新游戏规则下，两个人都知道石子的堆数和每堆的数量，假设两个人都绝顶聪明而且不会失误，先手的 Alice 是否一定可以必胜？

输入描述:

每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n (1 ≤ n ≤ 60) ， 接下来一行有 n 个整数 ai 表示第 i 堆的石子数量( 1 ≤ ai ≤ 1000000000)。

输出描述:

如果 Alice 必胜，输出 Alice，否则输出 Bob。
 对于样例，Alice 第一步只能拿走第 1 堆上的 1 个石子，接下来 Bob 只要拿走第 2 堆上的全部石子即可获胜。但如果两堆石子数分别是 2 1 ，那么 Alice 就必胜了。

输入例子:

2
1 2

输出例子:

Bob
//总结：先分析清楚题目的规律！！！！！----下笔如有神助
package dynamatic;
import java.util.Scanner;
public class D4 {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        boolean flag = false;// 找规律！！！12大数字前面奇数个1，--bob，偶数个----alice
        //只输入一次！！
        while (s.hasNext()) {
            int n = Integer.parseInt(s.nextLine());
            int[] a = new int[n];
            String[] str = s.nextLine().split(" ");
            int count = 0;
            int temp = 0;
            for (int i = 0; i < str.length; i++) {//得到超过1的最早位置
                if (Integer.parseInt(str[i]) > 1) {
                    temp = i;
                    break;
                }
            }
            for (int j = 0; j < temp; j++) {
                if (Integer.parseInt(str[j]) == 1) {//统计1的个数
                    count++;
                }
            }
            if (count % 2 == 0) {//奇数偶数判断
                flag = false;
                break;
            } else {
                flag = true;
                break;
            }
        }
        if (flag) {
            System.out.println("Bob");
        } else {
            System.out.println("Alice");
        }
    }
}