DP example for "Power of Two" in Python I'm not familiar with Python but want to provide a code snippet for an SO question about Dynamic Programming. 

The snippet should show the bottom-up approach of DP.

The function isPowerOfTwo returns True if the given number n is a power of two otherwise False. The implementation uses a button-up table results.

def isPowerOfTwo(n):
    results = {}
    for i in range(1, n + 1):
        if i == 2:
            results[i] = True
        elif i % 2 != 0:
            results[i] = False
        else:
            results[i] = results[i/2]
    return results[n]


Do you have any recommendations?
There are some major issues with your approach, the major one being that it is going to terribly break down for really large numbers. But if you want to go with it, here are a couple of improvements:


Don't use a dictionary. If your indices are consecutive integers, then a list is the right data structure.
You already know that most of your entries are going to be False, so why not initialize those in bulk and worry only about setting the Trues?

def is_power_of_two(n):
    sieve = [False] * (n + 1)
    pot = 2
    while pot &lt; len(sieve):
        sieve[pot] = True
        pot *= 2
    return sieve[n]



The name sieve is taken from the approach being somewhat similar to the sieve of Erathostenes algorithm.

In your case you can take things one step further, and rather than storing the full array, store only the indices of the True entries:

def is_power_of_two(n):
    pots = [2]
    while pots[-1] &lt; n:
        pots.append(pots[-1]*2]
    return pots[-1] == n


If you look at that code, you don't really need to store the whole array, since you are only using the last value. So you can get the same time complexity, \$O(\log n)\$, but with constant space, by doing:

def is_power_of_two(n):
    pot = 2
    while pot &lt; n:
        pot *= 2
    return pot == n


Of course the proper, fast way of checking if a number is a power of two is with a little bit twiddling hack that give \$O(1)\$ performance:

def is_power_of_two(n):
    return not n &amp; (n - 1)