#!/usr/bin/env python
"""
Optimally solve the problem of reducing a given integer number to 1
using the followng rules:
Rule 1: You can always decrease the number by 1
Rule 2: If the number is even, youy can divide it by 2
Rule 3: If the number is a multiple of 3, you can divide it by three
We search for the shortest sequence of rule applications, e.g.
10->9->3->1 (using rules 1, 3, 3).
"""
import sys
import getopt
def brute(n):
"""
Brute force solution. Recursively find the cost for all three
alternatives, find the best, add 1.
"""
if n == 1:
return 0
else:
subcost = brute(n-1)
rule = 1
if n%2 == 0:
tmp = brute(n/2)
if tmp0:
start = int(args[0])
if "brute" in selection:
print "Brute Force"
print "==========="
res= brute(start)
print "Optimal cost:", res
if "recdp" in selection:
print "Recursive DP"
print "============"
res = dpinit(start)
print "Optimal cost:", res
if "bupdp" in selection:
print "Bottom-up DP"
print "============"
res = dpbup(start)
print "Optimal cost:", res