[每日一题]DP二：最优子结构

正文

请到「今天看啥」查看全文

这道题有很多解法，我们在这篇总结里只讨论 DP 的解法。

本题可以抽象成一颗树，树的根节点是 n , 叶子节点的值都是 1，在每一个节点的决策路径是 ： 当 n 是偶数的时候， n = n / 2; 当 n 是奇数的是 n = n + 1 或者 n = n - 1。

根据定义，我们可以推出如下的等式

1. 如果 n 是偶数: f(n) = f(n/2) + 1

2. 如果 n 是奇数： f(n) = min(f(n-1), f(n+1)) + 1
   
   

以 n  = 9 为例，那么 n 经过一系列的替换 变成 1 的可能方案有如下几种：

1. 5个步骤：9 -> 8 -> 4 -> 2 -> 1

2. 5个步骤：9 -> 10 -> 5 -> 4 -> 2 -> 1

3. 7个步骤：9 -> 10 -> 5 -> 6 -> 3 -> 4 -> 2 -> 1

4. 9个步骤：9 -> 10 -> 5 -> 6 -> 3 -> 5 -> 6 -> 3 -> 2 -> 1

请到「今天看啥」查看全文