8000 Create B228.FootBallPoints.cs · xieqilu/Qilu-leetcode@201a66c · GitHub
[go: up one dir, main page]
Skip to content

Commit 201a66c

Browse files
xieqiluxieqilu
committed
Create B228.FootBallPoints.cs
1 parent a7852b4 commit 201a66c

File tree

1 file changed

+127
-0
lines changed

1 file changed

+127
-0
lines changed

‎B228.FootBallPoints.cs

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
/**
2+
第一个是football题，比赛得分可能得3分，也可能得6分，如果得了6分得话，
3+
后面还可以选择什么touch down或者kick，分别又是得1分或2分，然后如果给你一个N分，问你有几种可能。
4+
就是把这个想成一个树形结构，root是N，下面可以有3、6、7、8，然后每个再下面又3、6、7、8
5+
这样递归一个就好了，代码很简单
6+
7+
8+
Idea:
9+
This problem is very similiar to Fibonacci sequence. We can solve it both bottom-up and top-down.
10+
According to the description, each time, we can score 3 points, 6 points, 7 points or 8 points.
11+
Our task is to find out how many different combinations to score N points. For N points, we know
12+
from the last play, we have four situations that can lead to N points which are N-3 points, N-6
13+
points, N-7 points and N-8 points. Suppose f(n) is the number of combinatons to score n points.
14+
If we already know f(n-3), f(n-6), f(n-7), f(n-8), then by summing them up we can get f(n). So
15+
the recursion relationship is as follows:
16+
f(n) = f(n-6) + f(n-3) + f(n-7) + f(n-8)
17+
18+
And the base case is when we only need to score 0 points, we can always have one way to do that, we
19+
don't play at all. And obviously if n is less than 0, no way to score a negative points. Thus we
20+
actually have two base cases:
21+
f(0) = 1 and when n<0 f(n) = 0.
22+
23+
So we can easily sovel this problem using recursion. In order to make the algorithm more efficient,
24+
we can use an array to cache results of recursion so that we don't need to caculate f(n) repeatedly.
25+
26+
We can also use Dynamic Programming to solve this problem from bottom-up and don't use recursion at all.
27+
28+
29+
Solution1: Naive Recursive solution
30+
Don't use any cache, for any n, we use recursion to get its value. Then the calling structure is
31+
actualy like a tree in which each root has 4 children. Thus the time complexiy is O(4^n) and since
32+
execution stack will hold all recursive call, so the space complexity is also likely O(4^n). Both
33+
are not efficient.
34+
35+
Solution2: Recursive solution with caching
36+
We can use an array with size of n+1 to cache all intermideate results for the recursive calls.
37+
And cache[n] is the number of combinations for scoring n points. Initially cache[0] is 1 and all
38+
other cache[i] is -1. So in the recursive call, if n<0, return 0. Then we look up cache[n], if it
39+
is -1, means cache[n] is not filled yet. So we use recursion to caculate cache[n] and return it. If
40+
cache[n] is not -1, means it's been filled before, so we directly return its value.
41+
Then we will only fill each cache[i] for once, so the time and space complexity are both O(n).
42+
43+
Solution3: DP solution
44+
We also use an array with size of n+1, and dp[i] is the number of combinations to score i points.
45+
Then we can actually fill the array dp from smaller index to larger index (bottom-up). First set
46+
dp[0] =1, then traverse from i=0 to n, for each i we add the value of dp[i] to dp[i+3], dp[i+6],
47+
dp[i+7] and dp[i+8]. Because in the tree structure, dp[i] could be child of those 4 roots. If i+3,
48+
i+6, i+7. i+8 are larger than n, we just ignore them since we only need to know dp[n]. After the
49+
loop, return n.
50+
51+
Obviously the time and space complexity are both O(n).
52+
*/
53+
54+
using System;
55+
using System.Collections.Generic;
56+
public class Test
57+
{
58+
//Solution1: Top-Down Naive Recursive Solution (with no caching)
59+
//Time: O(4^n) Space: O(1)
60+
public static int FootBall(int n){
61+
if(n==0) //base case#1
62+
return 1;
63+
if(n<0) //base case#2
64+
return 0;
65+
return FootBall(n-3) + FootBall(n-6) + FootBall(n-7) + FootBall(n-8);
66+
}
67+
68+
//Solution2: Top-Down Recursive Solution with caching
69+
//Time: O(n) Space: O(n)
70+
public static int FootBallCaching(int n){
71+
int[] cache = new int[n+1];
72+
for(int i=1;i<n+1;i++)
73+
cache[i] = -1;
74+
cache[0] = 1;
75+
return Helper(n, cache);
76+
}
77+
78+
private static int Helper(int n, int[] cache){
79+
if(n<0)
80+
return 0;
81+
if(cache[n]!=-1) //if cache[n] is already caculated, directly get the value
82+
return cache[n];
83+
cache[n] = Helper(n-3,cache)+Helper(n-6,cache)+Helper(n-7,cache)+Helper(n-8,cache);
84+
return cache[n];
85+
}
86+
87+
//Solution3: Bottom-Up Dynamic Programming Solution Time: O(n) Space: O(n)
88+
//Better than naive recursive solution
89+
public static int FootBallIter(int n){
90+
int[] dp = new int[n+1];
91+
dp[0] = 1;
92+
for(int i=0;i<n+1;i++){ //O(n)
93+
if(i+3<n+1)
94+
dp[i+3]+=dp[i];
95+
if(i+6<n+1)
96+
dp[i+6]+=dp[i];
97+
if(i+7<n+1)
98+
dp[i+7]+=dp[i];
99+
if(i+8<n+1)
100+
dp[i+8]+=dp[i];
101+
}
102+
return dp[n];
103+
}
104+
105+
106+
public static void Main()
107+
{
108+
Console.WriteLine("Test naive recursive solution");
109+
Console.WriteLine(FootBall(4)); //0
110+
Console.WriteLine(FootBall(6)); //2
111+
Console.WriteLine(FootBall(9)); //3
112+
Console.WriteLine(FootBall(12)); //5
113+
Console.WriteLine(FootBall(13)); //5
114+
Console.WriteLine("Test recursive solution with caching");
115+
Console.WriteLine(FootBallCaching(4)); //0
116+
Console.WriteLine(FootBallCaching(6)); //2
117+
Console.WriteLine(FootBallCaching(9)); //3
118+
Console.WriteLine(FootBallCaching(12)); //5
119+
Console.WriteLine(FootBallCaching(13)); //5
120+
Console.WriteLine("Test Dp solution");
121+
Console.WriteLine(FootBallIter(4)); //0
122+
Console.WriteLine(FootBallIter(6)); //2
123+
Console.WriteLine(FootBallIter(9)); //3
124+
Console.WriteLine(FootBallIter(12)); //5
125+
Console.WriteLine(FootBallIter(13)); //5
126+
}
127+
}

0 commit comments

Comments
 (0)
0