DP + Divide and Conquer to solve how many numbers are there within a certain 10 ^ n, which contains 14.

14Matrix.py

class Matrix(list):
  def __init__(self, *args):
    super(Matrix, self).__init__(args)

  def __mul__(self, other):
    def dotproduct(As, Bs):
      return sum(a * b for a, b in zip(As, Bs))

    otherT = zip(*other)
    return Matrix(*[[dotproduct(As, Bs) for Bs in otherT] for As in self])

  def __pow__(self, N):
    """
    O(log(N))-complexity powering algorithm.
    A ** B = (A ** (B / 2)) ** 2
    (2 ** 16) = (2 ** 8) * (2 ** 8)
    """
    assert isinstance(N, int), "Matrix powering only support integer value"
    assert N >= 0, "Doesn't support inverse matrix"
    if N == 0:
      return self.identity
    elif N == 1:
      return self
    elif N % 2 == 0:
      squared = self * self
      return squared ** (N / 2)
    else:
      squared = self * self
      return (squared ** (N / 2)) * self

  @property
  def identity(self):
    return Matrix(*[[int(i == j) for i, x in enumerate(y)] for j, y in enumerate(self)])

  def __repr__(self):
    return "%s\n" % '\n'.join(map(str, self))

def naiveCount(n):  
  return sum(1 for e in xrange(10 ** int(n)) if str(e).find('14') != -1)

def dpCount(N):
  n = int(N)
  if n <= 0:
    return 0 
  elif n == 1:
    return 0
  elif n == 2:
    return 1  
  else:  
    return 10 * dpCount(n - 1) - dpCount(n - 2) + 10 ** (n - 2)

def matrixCount(n):
  """  
  [n       ]  -> [10 * n  ]
  [f(0)    ]  -> [f(1)    ]
  [f(1)    ]  -> [f(2)    ]
  [f(2)    ]  -> [f(3)    ] // f(n) = 10 * f(n - 1) - f(n - 2) + 10 ** (n - 2)
  """    
  A = Matrix(
    [10, 0, 0, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 1],
    [1, 0, -1, 10]
  )
  B = Matrix([10], [0], [0], [1])  
  return (A ** int(n) * B)[1][0]

def get14With(method, number):  
  n = len(str(number))
  return method(n)

def main():
  # common usage
  # print get14With(matrixCount, 10000)
  # print get14With(dpCount, 10000)
  # print get14With(naiveCount, 10000)

  # showing off the matrices ability
  for i in xrange(100):
    print matrixCount(i)

if __name__ == '__main__':
  main()