贪心算法
思路
所谓贪心算法就是我们在寻找整体最优解的情况下，先找到局部最优解。
例如:
12 可以多种组合表示
12 = 10 + 1 + 1 -> XII
12 = 9 + 1 + 1 + 1 -> IXIII
12 = 5 + 5 + 1 + 1 -> VVII
12 = 5 + 4 + 1 + 1 + 1 -> VIVIII
12 = 4 + 4 + 4 -> IVIVIV
这里我们为了用更少的罗马数字来表示整数，所以一般将整数拆分为尽可能大的数来表示，即12 = 10 + 1 +1 = XII。由此我们可以通过对给定整数不断循环减去尽可能大的数，同时对结果添加相应罗马字符来获取结果。
class Solution: def intToRoman(self, num: int) -> str: if num > 3999 or num < 1: return "out of range" nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] romans = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] index = 0 result = ‘‘ while index < len(romans): while num >= nums[index]: result += romans[index] num -= nums[index] index += 1 return result
原文：https://www.cnblogs.com/nilhxzcode/p/12772296.html