TopCoder SRM 403 Level2 1000
4和7是幸運(yùn)數(shù)字，如果一個(gè)數(shù)只包含4和7，那么這個(gè)數(shù)字也是一個(gè)幸運(yùn)數(shù)字
給定一個(gè)1－1,000,000的數(shù)字，求這個(gè)數(shù)字是否可以僅由幸運(yùn)數(shù)字相加得出，返回所有的幸運(yùn)數(shù)字加數(shù)，如果有多組解，返回加數(shù)最少的一組
以前沒有遇到過這樣的DP題目
這題加深了我對(duì)于“每個(gè)子問題的答案都是最佳答案”的理解
首先是額外的計(jì)算
將范圍以內(nèi)的幸運(yùn)數(shù)字打表
然后從輸入數(shù)字N開始遞減DP計(jì)算
N的步數(shù)為0
如果最后0的步數(shù)為正數(shù)
說明有解
再?gòu)?開始遞增尋找解的路徑
不過這個(gè)方法最后也沒有通過tc的系統(tǒng)測(cè)試
數(shù)字一大就超時(shí)了
后面又時(shí)間再研究一下
看看有沒有辦法在改進(jìn)
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 }