Wednesday, June 15, 2016

Football Game

Question:
football题,比赛得分可能得3分,也可能得6分,如果得了6分得话,后面还可以选择什么touch down或者kick,分别又是得1分或2分,然后如果给你一个N分,问你有几种可能.

DFS Solution:
对于每一个得分N, 可能接下来的得分就是N + 3, N + 6, N + 7, N + 8. 从比分0向下递推,直到最后的得分是N。

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
  private int result = 0;
  public int getScore(int n) {
    if (n < 3) {
      return 0;
    }
    
    getScoreHelper(n);
    
    return result;
  }
  
  private void getScoreHelper(int n) {
    if (n == 0) {
      result++;
      return;
    }
    
    if (n < 3) {
      return;
    }
    
    getScoreHelper(n - 3);
    getScoreHelper(n - 6);
    getScoreHelper(n - 7);
    getScoreHelper(n - 8);
  }
  
  public static void main(String[] args) {
    Solution sol = new Solution();
    
    int n = 11;
    int result = sol.getScore(n);
    System.out.println(result);
  }
}

The DP Solution:
Define dp[n + 1], where dp[i] is the number of possible ways for score i.
dp[i] = dp[i - 3] + dp[i - 6] + dp[i - 7] + dp[i - 8];

Code (Java):
import java.io.*;
import java.util.*;

public class Solution {
  public int getScoreDP(int n) {
    if (n < 3) {
      return 0;
    }
    
    int[] dp = new int[n + 1];
    dp[3] = 1;
    dp[6] = 2;
    dp[7] = 1;
    dp[8] = 1;
    
    for (int i = 9; i <= n; i++) {
      dp[i] = dp[i - 3] + dp[i - 6] + dp[i - 7] + dp[i - 8];
    }
    
    return dp[n];
  }
  
  public static void main(String[] args) {
    Solution sol = new Solution();
    
    int n = 45;
    int result = sol.getScoreDP(n);
    System.out.println(result);
  }
}

No comments:

Post a Comment