Untitled
unknown
plain_text
a month ago
940 B
4
Indexable
Never
def min_moves(n): """ Returns the minimum number of moves required to reduce the enemy army to 1 soldier. :param n: The number of enemy soldiers. :return: The minimum number of moves. """ memo = {1: 0} # Base case: 0 moves required for 1 soldier def recursive_min_moves(n): if n in memo: return memo[n] # Try all three moves and choose the one with the minimum number of moves move1 = recursive_min_moves(n - 1) + 1 move2 = recursive_min_moves(n // 2) + 1 if n % 2 == 0 else float('inf') move3 = recursive_min_moves(n // 3) + 1 if n % 3 == 0 else float('inf') # Store the result in the memo dictionary memo[n] = min(move1, move2, move3) return memo[n] return recursive_min_moves(n) # Example usage: n = int(input("Enter the number of enemy soldiers: ")) print("Minimum number of moves:", min_moves(n))
Leave a Comment