// Problem 1 (Naive)
  // O(k^k)
  public static int smsNaive(int k) {
    int result = 0;
    for (int i = 1; i < k + 1; i++) {
      result += smsNaiveHelper(i);
    }
    return result;
  }

  public static int smsNaiveHelper(int k) {
    if (k < 0) return 0;
    if (k == 0) return 1;
    return 8 * smsNaiveHelper(k - 1) + 
           8 * smsNaiveHelper(k - 2) + 
           8 * smsNaiveHelper(k - 3) + 
           2 * smsNaiveHelper(k - 4);
  }

  // Problem 1 (DP)
  // O(k^2)
  public static int smsDP(int k) {
    // dp[i] - is a number of messages
    // that uses 'i' presses
    int dp[] = new int[k + 1];

    // initial state
    // we can write only one message (an empty with length 0) by zero presses
    dp[0] = 1;

    // result
    int result = 0;

    // fill the dp
    for (int i = 1; i < k + 1; i++) {
      dp[i] += dp[i - 1] * 8;
      if (i - 1 > 0) {
        dp[i] += dp[i - 2] * 8;
      }
      if (i - 2 > 0) {
        dp[i] += dp[i - 3] * 8;
      }
      if (i - 3 > 0) {
        dp[i] += dp[i - 4] * 2;
      }

      result += dp[i];
    }

    return result;
  }

// Problem 1 (DP)
  // O(k^2)
  public static int smsDP(int k) {
    // base case
    if (k == 0) return 1;

    // dp[i][j] - is a number of messages
    // that with length 'i' that uses 'j' presses
    int dp[][] = new int[k + 1][k + 1];

    // initial state
    // we can write only one message (an empty with length 0) by zero presses
    //for (int i = 0; i < k; i++) {
      dp[0][0] = 1;
    //}

    // answer
    int result = 0;

    // fill the dp
    // we can't write message with length M by pressing N keys, where M > N
    // this is why we're trying to get an upper triangular matrix
    for (int i = 1; i < k + 1; i++) {
      for (int j = i; j < k + 1; j++) {
        dp[i][j] = dp[i - 1][j - 1] * 8;
        if (j - 1 > 0) {
          dp[i][j] += dp[i - 1][j - 2] * 8;
        }
        if (j - 2 > 0) {
          dp[i][j] += dp[i - 1][j - 3] * 8;
        }
        if (j - 3 > 0) {
          dp[i][j] += dp[i - 1][j - 4] * 2;
        }

        if (j == k) {
          result += dp[i][j];
        }
      }
    }

    return result;
  }