TopCoder SRM 403 Level2 1000
4和7是幸运数字，如果一个数只包含4和7，那么这个数字也是一个幸运数字
给定一个1－1,000,000的数字，求这个数字是否可以仅由幸运数字相加得出，返回所有的幸运数字加数，如果有多组解，返回加数最少的一组
以前没有遇到过这样的DP题目
这题加深了我对于“每个子问题的答案都是最佳答案”的理解
首先是额外的计算
将范围以内的幸运数字打表
然后从输入数字N开始递减DP计算
N的步数为0
如果最后0的步数为正数
说明有解
再从0开始递增寻找解的路径
不过这个方法最后也没有通过tc的系统测试
数字一大就超时了
后面又时间再研究一下
看看有没有办法在改进
1 import java.util.*;
2 import java.util.regex.*;
3 import java.text.*;
4 import java.math.*;
5 import java.awt.geom.*;
6
7 public class TheSumOfLuckyNumbers
8 {
9
10 public int[] sum(int n)
11 {
12 ArrayList<Integer> table = calTable();
13 int[] dp = new int[n+1];
14 Arrays.fill(dp, Integer.MAX_VALUE-10);
15 dp[n] = 0;
16 int i , j;
17 for(i = n; i > 0 ; -- i){
18 for(int lucky:table){
19 if(i - lucky >=0 && dp[i] + 1 < dp[i - lucky])
20 dp[i - lucky] = dp[i] + 1;
21 }
22 }
23 if(dp[0] == Integer.MAX_VALUE)
24 return new int[0];
25 ArrayList<Integer> ans = new ArrayList<Integer>();
26 int total = dp[0]-1;
27 for(i = 0 ; i <= n; ++ i){
28 for(int lucky:table){
29 if(i + lucky <= n && dp[i + lucky] == total){
30 ans.add(lucky);
31 i += lucky-1;
32 total--;
33 break;
34 }
35 }
36 }
37 int[] ret = new int[ans.size()];
38 for(i = 0 ; i < ans.size(); ++ i)
39 ret[i] = ans.get(i);
40 return ret;
41 }
42
43
44
45 public ArrayList<Integer> calTable(){
46 ArrayList<Integer> table = new ArrayList<Integer>();
47 table.add(4);
48 table.add(7);
49 int i = 1;
50 while(i < 7){
51 ArrayList<Integer> temp = new ArrayList<Integer>();
52 for(int j = 0 ; j < table.size(); ++ j){
53 int newItem = table.get(j) * 10;
54
55 temp.add(newItem+4);
56 temp.add(newItem+7);
57 }
58 i++;
59 table.addAll(temp);
60 }
61 return table;
62 }
63 }