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 }