动态规划与最短路径算法

发表于 2024-05-12 更新于 2024-11-19 分类于 Algorithm Waline：

最近在leetcode看到了一道题，很有意思，可以用动态规划解，也可以用Dijkstra算法来解，这道题最大的启发就是：

动态规划的每个节点就是图中的节点，状态转移方程其实就是两个节点之间的连线，我们可以用Dijkstra算法求解从开始节点到目标结点的最短路径。

题目描述

厨房里总共有 n 个橘子，你决定每一天选择如下方式之一吃这些橘子：

吃掉一个橘子。
如果剩余橘子数 n 能被 2 整除，那么你可以吃掉 n/2 个橘子。
如果剩余橘子数 n 能被 3 整除，那么你可以吃掉 2*(n/3) 个橘子。

每天你只能从以上 3 种方案中选择一种方案。

请你返回吃掉所有 n 个橘子的最少天数。

解题思路

动态规划

最容易想到的思路就是动态规划，每次状态转移只有三种方式

f(i) = \begin{cases} 1, i = 1, \\ min{f(i - 1), f(i / 2), f(i / 3)} + 1, i 是 6 的倍数 \\ min{f(i -1), f(i / 2)} + 1, i 是 6 的倍数\\ min{f(i -1), f(i / 3)} + 1, i 是 6 的倍数\\ f(i - 1), 其他情况 \end{cases}

示例代码：

/**
 * @param {number} n
 * @return {number}
 */
var minDays = function(n) {
    const res = new Array(n + 1).fill(0);
    res[1] = 1;

    for(let i = 2; i <= n; i++) {
        res[i] = 1 + res[i - 1];
        if (i % 2 === 0) {
            res[i] = Math.min(res[i], 1 + res[i / 2]);
        }
        if (i % 3 === 0) {
            res[i] = Math.min(res[i], 1 + res[i / 3]);
        }
    }

    return res[n];
};

记忆化搜搜

思路与算法

动态规划的递推是「自底向上」的，我们可以试着将这个过程改成「自顶向下」的记忆化搜索，并深度挖掘题目的性质。

由于我们需要用最少的天数吃完所有的橘子，而「吃掉一个橘子」这样的操作是很不优秀的，不像另外的两种操作可以直接将橘子数变为当前的 1/2 和 1/3。直观地来说，我们希望「吃掉一个橘子」的操作次数尽可能少。

为了叙述方便，我们称「吃掉一个橘子」为操作 1，「吃掉一半橘子」为操作 2，「吃掉三分之二橘子」为操作 3。

我们可以证明，在最优的方法中，操作 1 的次数是十分有限的：

如果我们连续地进行了 k 次操作 1 之后进行了操作 2，那么橘子数从 n 变成了 (n−k)/2。我们设 $k_0$ 为 k 对 2 取模的值， $0 \leq k_0 \leq 1$ , 那么我们只需要依次进行 $k_0$ 次操作 1，1 次操作2， $(k - k_0) / 2$ 次操作 1，同样也能得到:

(n - k_0) / 2 - (k - k_0) / 2 = (n - k) / 2

结果相同，而操作次数仅为

k_ 0 + 1 + (k - k_0) / 2

解不等式：

k_ 0 + 1 + (k - k_0) / 2 \le k + 1

得：

k \ge k_0

这个不等式在 k 为正整数时显然成立，因此我们可以用对应的操作替代 k 次操作 1，这样我们保证了在任意一次操作 2 之前，操作 1 的次数都不会超过 1 次。

如果我们连续地进行了 k 次操作 1 之后进行了操作 3，那么橘子数从 n 变成了 (n−k)/3。我们设 $k_0$ 为 k 对 3 取模的值， $0 \leq k_0 \leq 2$ , 那么我们只需要依次进行 $k_0$ 次操作 1，1 次操作3， $(k - k_0) / 3$ 次操作 1，同样也能得到:

(n - k_0) / 3 - (k - k_0) / 3 = (n - k) / 3

结果相同，而操作次数仅为

k_ 0 + 1 + (k - k_0) / 3

解不等式：

k_ 0 + 1 + (k - k_0) / 3 \le k + 1

得：

k \ge k_0

这个不等式在 k 为正整数时显然成立，因此我们可以用对应的操作替代 k 次操作 1，这样我们保证了在任意一次操作 3 之前，操作 1 的次数都不会超过 2 次。

如果我们连续地进行了 k 次操作 1 并吃完了所有橘子（即接下来没有进行操作 2 或 3），那么橘子数从 k 变成 0。只要 $k \ge 2$ ，我们可以在 k=2 的时候将操作 1 用等价的操作 2 替代（即 2−1=2/2），这样在操作 2 之前的 k−2 次操作 1 就可以再通过上面提到的方法进行替代。因此，k 只能等于 1，也就是说，只要当前的橘子数多于 1 个，我们就没有必要一直进行操作 1 直到橘子被吃完。

根据上面的分析，我们可以得到三条重要的结论：

在任意一次操作 2 之前最多只会有 1 次操作 1；
- 对于任意的橘子数 i≥2，唯一的操作方法是将 n 通过操作 1 减少到最近的 2 的倍数，随后进行一次操作 2。写成递推式即为：f(i)=i%2+1+f(⌊i/2⌋)
在任意一次操作 3 之前最多只会有 2 次操作 1；
- 对于任意的橘子数 i≥3，唯一的操作方法是将 n 通过操作 1 减少到最近的 3 的倍数，随后进行一次操作 3。写成递推式即为 f(i)=i%3+1+f(⌊i/3⌋)
除了最后的一次操作 1 之外，其余连续的操作 1 之后都会有操作 2 或 3。即：f(1)=1

用记忆化搜索的方式来实现：

var minDays = function(n) {
    const memo = new Map([[0, 0], [1, 1]]);

    function helper(n) {
        if (memo.has(n)) {
            return memo.get(n);
        }
        memo.set(n, Math.min(n % 2 + 1 + helper(Math.floor(n / 2)), n % 3 + 1 + helper(Math.floor(n / 3))));
        return memo.get(n);
    }
    return helper(n);
};

最短路径算法

我们也可以将方法一中的思路抽象成一个「最短路」问题，即：

图 G 中有若干个节点，每个节点表示着一个数。根据方法一，每个节点对应着一个 $\lfloor n \ (x^x3^y) \rfloor$ ，节点数为 O(log⁡2n)；

图 G 中有若干条有向边，如果某个节点表示的数为 i，那么 i 到 ⌊i/2⌋ 有一条长度为 i%2+1 的有向边，i 到 ⌊i/3⌋ 有一条长度为 i%3+1 的有向边。边数同样为 O(log⁡2n), 我们需要求出 n 对应的节点到 1 对应的节点的最短路径的长度。

因此我们可以用 Dijkstra 算法求出答案。

var minDays = function(n) {
    const q = new MinPriorityQueue();
    q.enqueue([0, n], 0);
    const visited = new Set();
    let ans = 0;
    while (true) {
        [days, rest] = q.dequeue().element;
        console.log(days, rest);
        if (visited.has(rest)) {
            continue;
        }
        visited.add(rest);
        if (rest == 1) {
            ans = days + 1;
            break;
        }
        q.enqueue([days + rest % 2 + 1, Math.floor(rest / 2)], days + rest % 2 + 1);
        q.enqueue([days + rest % 3 + 1, Math.floor(rest / 3)], days + rest % 3 + 1);
    }
    return ans;
};