动态规划问题集锦

5
8 32 12 16 4

4

8
20 6 200 4 36 108 40 2

5

8
108 4 360 6 756 18 2 36

6

 思路：先把数组排序，再对每一个元素计算当包含当前元素及其前面元素时，当前元素所在最大子集的大小。

附代码如下：

// Don't place your source in a package
import java.util.*;
import java.lang.*;
import java.io.*;

// Please name your class Main
class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    Scanner in = new Scanner(System.in);
		int number = in.nextInt();
		int[] arr = new int[number];
		for(int i = 0; i < number; i++)
			arr[i] = in.nextInt();
		int[] arrflag = new int[number];
		for(int i = 0; i < arrflag.length; i++)
			arrflag[i] = 1;
		int answer = 0;
		Arrays.sort(arr);
		for(int i = 1; i < arr.length; i++) {
			for(int j = 0; j < i; j++) {
				if(arr[i] % arr[j] == 0 && arrflag[i] < arrflag[j] + 1)
					arrflag[i] = arrflag[j] + 1;
			}
			if(arrflag[i] > answer)
				answer = arrflag[i];
		}
		System.out.println(answer);
	}
}