|
|
back to boardHow can I improve this program? Num = int(raw_input())
Array = [0] * (Num + 1)
def Rec (Sum, Start):
global Array
if Start == Num + 1 or Sum + Start > Num: return
if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1
Rec (Sum + Start, Start + 1)
Rec (Sum, Start + 1)
Rec (0, 1)
print Array[Num]
It produces following output (first column input, second column output)
0 0
1 0
2 0
3 1
4 1
5 2
6 3
7 4
8 5
9 7
10 9
11 11
12 14
13 17
14 21
15 26
16 31
17 37
18 45
19 53
20 63
But it exceeds 1 sec limit when the input is 88.
Edited by author 23.06.2013 10:28
Edited by author 23.06.2013 10:28 Re: How can I improve this program? Num = int(raw_input())
Array = [0] * (Num + 1)
def Rec (Sum, Start):
global Array
if Start == Num + 1 or Sum + Start > Num: return
if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1
Rec (Sum + Start, Start + 1)
Rec (Sum, Start + 1)
Rec (0, 1)
print Array[Num]
It produces following output (first column input, second column output)
0 0
1 0
2 0
3 1
4 1
5 2
6 3
7 4
8 5
9 7
10 9
11 11
12 14
13 17
14 21
15 26
16 31
17 37
18 45
19 53
20 63
But it exceeds 1 sec limit when the input is 88.
Never mind. Memoization did the trick. |
|
|
