<p>There is only one character <code>&#39;A&#39;</code> on the screen of a notepad. You can perform one of two operations on this notepad for each step:</p>

<ul>
	<li>Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).</li>
	<li>Paste: You can paste the characters which are copied last time.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>the minimum number of operations to get the character</em> <code>&#39;A&#39;</code> <em>exactly</em> <code>n</code> <em>times on the screen</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> Initially, we have one character &#39;A&#39;.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get &#39;AA&#39;.
In step 3, we use Paste operation to get &#39;AAA&#39;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

from functools import cache
pre_computed = {1: 0, 2: 2, 3: 3, 4: 4, 5: 5, 6: 5, 7: 7, 8: 6, 9: 6, 10: 7, 11: 11, 12: 7, 13: 13, 14: 9, 15: 8, 16: 8, 17: 17, 18: 8, 19: 19, 20: 9, 21: 10, 22: 13, 23: 23, 24: 9, 25: 10, 26: 15, 27: 9, 28: 11, 29: 29, 30: 10, 31: 31, 32: 10, 33: 14, 34: 19, 35: 12, 36: 10, 37: 37, 38: 21, 39: 16, 40: 11, 41: 41, 42: 12, 43: 43, 44: 15, 45: 11, 46: 25, 47: 47, 48: 11, 49: 14, 50: 12, 51: 20, 52: 17, 53: 53, 54: 11, 55: 16, 56: 13, 57: 22, 58: 31, 59: 59, 60: 12, 61: 61, 62: 33, 63: 13, 64: 12, 65: 18, 66: 16, 67: 67, 68: 21, 69: 26, 70: 14, 71: 71, 72: 12, 73: 73, 74: 39, 75: 13, 76: 23, 77: 18, 78: 18, 79: 79, 80: 13, 81: 12, 82: 43, 83: 83, 84: 14, 85: 22, 86: 45, 87: 32, 88: 17, 89: 89, 90: 13, 91: 20, 92: 27, 93: 34, 94: 49, 95: 24, 96: 13, 97: 97, 98: 16, 99: 17, 100: 14, 101: 101, 102: 22, 103: 103, 104: 19, 105: 15, 106: 55, 107: 107, 108: 13, 109: 109, 110: 18, 111: 40, 112: 15, 113: 113, 114: 24, 115: 28, 116: 33, 117: 19, 118: 61, 119: 24, 120: 14, 121: 22, 122: 63, 123: 44, 124: 35, 125: 15, 126: 15, 127: 127, 128: 14, 129: 46, 130: 20, 131: 131, 132: 18, 133: 26, 134: 69, 135: 14, 136: 23, 137: 137, 138: 28, 139: 139, 140: 16, 141: 50, 142: 73, 143: 24, 144: 14, 145: 34, 146: 75, 147: 17, 148: 41, 149: 149, 150: 15, 151: 151, 152: 25, 153: 23, 154: 20, 155: 36, 156: 20, 157: 157, 158: 81, 159: 56, 160: 15, 161: 30, 162: 14, 163: 163, 164: 45, 165: 19, 166: 85, 167: 167, 168: 16, 169: 26, 170: 24, 171: 25, 172: 47, 173: 173, 174: 34, 175: 17, 176: 19, 177: 62, 178: 91, 179: 179, 180: 15, 181: 181, 182: 22, 183: 64, 184: 29, 185: 42, 186: 36, 187: 28, 188: 51, 189: 16, 190: 26, 191: 191, 192: 15, 193: 193, 194: 99, 195: 21, 196: 18, 197: 197, 198: 19, 199: 199, 200: 16, 201: 70, 202: 103, 203: 36, 204: 24, 205: 46, 206: 105, 207: 29, 208: 21, 209: 30, 210: 17, 211: 211, 212: 57, 213: 74, 214: 109, 215: 48, 216: 15, 217: 38, 218: 111, 219: 76, 220: 20, 221: 30, 222: 42, 223: 223, 224: 17, 225: 16, 226: 115, 227: 227, 228: 26, 229: 229, 230: 30, 231: 21, 232: 35, 233: 233, 234: 21, 235: 52, 236: 63, 237: 82, 238: 26, 239: 239, 240: 16, 241: 241, 242: 24, 243: 15, 244: 65, 245: 19, 246: 46, 247: 32, 248: 37, 249: 86, 250: 17, 251: 251, 252: 17, 253: 34, 254: 129, 255: 25, 256: 16, 257: 257, 258: 48, 259: 44, 260: 22, 261: 35, 262: 133, 263: 263, 264: 20, 265: 58, 266: 28, 267: 92, 268: 71, 269: 269, 270: 16, 271: 271, 272: 25, 273: 23, 274: 139, 275: 21, 276: 30, 277: 277, 278: 141, 279: 37, 280: 18, 281: 281, 282: 52, 283: 283, 284: 75, 285: 27, 286: 26, 287: 48, 288: 16, 289: 34, 290: 36, 291: 100, 292: 77, 293: 293, 294: 19, 295: 64, 296: 43, 297: 20, 298: 151, 299: 36, 300: 17, 301: 50, 302: 153, 303: 104, 304: 27, 305: 66, 306: 25, 307: 307, 308: 22, 309: 106, 310: 38, 311: 311, 312: 22, 313: 313, 314: 159, 315: 18, 316: 83, 317: 317, 318: 58, 319: 40, 320: 17, 321: 110, 322: 32, 323: 36, 324: 16, 325: 23, 326: 165, 327: 112, 328: 47, 329: 54, 330: 21, 331: 331, 332: 87, 333: 43, 334: 169, 335: 72, 336: 18, 337: 337, 338: 28, 339: 116, 340: 26, 341: 42, 342: 27, 343: 21, 344: 49, 345: 31, 346: 175, 347: 347, 348: 36, 349: 349, 350: 19, 351: 22, 352: 21, 353: 353, 354: 64, 355: 76, 356: 93, 357: 27, 358: 181, 359: 359, 360: 17, 361: 38, 362: 183, 363: 25, 364: 24, 365: 78, 366: 66, 367: 367, 368: 31, 369: 47, 370: 44, 371: 60, 372: 38, 373: 373, 374: 30, 375: 18, 376: 53, 377: 42, 378: 18, 379: 379, 380: 28, 381: 130, 382: 193, 383: 383, 384: 17, 385: 23, 386: 195, 387: 49, 388: 101, 389: 389, 390: 23, 391: 40, 392: 20, 393: 134, 394: 199, 395: 84, 396: 21, 397: 397, 398: 201, 399: 29, 400: 18, 401: 401, 402: 72, 403: 44, 404: 105, 405: 17, 406: 38, 407: 48, 408: 26, 409: 409, 410: 48, 411: 140, 412: 107, 413: 66, 414: 31, 415: 88, 416: 23, 417: 142, 418: 32, 419: 419, 420: 19, 421: 421, 422: 213, 423: 53, 424: 59, 425: 27, 426: 76, 427: 68, 428: 111, 429: 27, 430: 50, 431: 431, 432: 17, 433: 433, 434: 40, 435: 37, 436: 113, 437: 42, 438: 78, 439: 439, 440: 22, 441: 20, 442: 32, 443: 443, 444: 44, 445: 94, 446: 225, 447: 152, 448: 19, 449: 449, 450: 18, 451: 52, 452: 117, 453: 154, 454: 229, 455: 25, 456: 28, 457: 457, 458: 231, 459: 26, 460: 32, 461: 461, 462: 23, 463: 463, 464: 37, 465: 39, 466: 235, 467: 467, 468: 23, 469: 74, 470: 54, 471: 160, 472: 65, 473: 54, 474: 84, 475: 29, 476: 28, 477: 59, 478: 241, 479: 479, 480: 18, 481: 50, 482: 243, 483: 33, 484: 26, 485: 102, 486: 17, 487: 487, 488: 67, 489: 166, 490: 21, 491: 491, 492: 48, 493: 46, 494: 34, 495: 22, 496: 39, 497: 78, 498: 88}
class Solution:
    def minSteps(self, n: int) -> int:
        if n in pre_computed:
            return pre_computed[n]
        @cache
        def helper(count,paste):
            if count == n:
                return 0
            elif count >n:
                return 1000
            choice_1 = 1 + helper(count+paste, paste)
            choice_2 = 2 + helper(2*count, count)
            return min(choice_1, choice_2)
        return 1 + helper(1,1)
        
32491