leetcode 397. Integer Replacement | 397. 整数替换（动态规划，记忆化搜搜）

Bertha 。 2022-09-02 01:16 31阅读 0赞

## 题目 ##

[https://leetcode.com/problems/integer-replacement/][https_leetcode.com_problems_integer-replacement]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

一开始写了个 dp，结果因为大数组 OOM 了。

dp 数组需要计算每一个值，有的值是用不到的，于是改成了递归，可以避免一些没有必要的计算。

另外要注意其中有一个测试用例是 2^32-1，如果先 +1 再除以 2 的话，会溢出，所以要先除以 2，再加 1。

class Solution { 
        public int integerReplacement(int n) { 
    // 大dp数组Memory Limit Exceeded了。。
    // int[] dp = new int[n + 1];
    // dp[1] = 0;
    // for (int i = 2; i < dp.length; i++) { 
    // if (i % 2 == 1) { 
    // dp[i] = Math.min(dp[i - 1], dp[(i + 1) / 2] + 1) + 1;
    // } else { 
    // dp[i] = dp[i / 2] + 1;
    // }
    // }
    // return dp[n];
    
            // 记忆化搜索
            Map<Integer, Integer> map = new HashMap<>();
            map.put(1, 0);
            return process(map, n);
        }
    
        public int process(Map<Integer, Integer> map, int i) { 
            if (map.containsKey(i)) { 
                return map.get(i);
            } else { 
                int n;
                if (i % 2 == 1) { 
                    n = Math.min(process(map, i - 1), process(map, i / 2 + 1) + 1) + 1;
                } else { 
                    n = process(map, i / 2) + 1;
                }
                map.put(i, n);
                return n;
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_integer-replacement]: https://leetcode.com/problems/integer-replacement/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/11b53aac994d48f380282e566544c403.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/29f926badddf41efbdfff31651352d08.png