算法 - 动态规划

动态规划技术的核心是“子问题划分”和“记忆化”。比如，leetcode#70. 爬楼梯与leetcode#120. 三角形最小路径和。#70的子问题划分是这样的 ---- 由于每次只能向上爬一个或两个台阶，所以，爬到最高层的楼梯的路径数 \(f(n)\) 一定是爬到最高层往下一层的路径数 \(f(n-1)\) 与往下两层的路径数 \(f(n-2)\) （如果存在的话）之和。而#70的记忆化是这样的 ---- 如果按照从目标到起点的子问题划分方式来计算的话，那就是将递归思想实现为递归算法。但是，递归算法存在重复计算的情况，比如计算 \(f(n-1)\) 的时候也会计算一次 \(f(n-2)\)。记忆化就是一种用空间换取时间的算法，毕竟，如果问题规模即楼梯数有限的话，将中间数据全部列出来所消耗的内存一般情况也是可以接受的。而且，大多数情况又是可以用“滚动数组”的思想，将内存消耗压缩到\(O(1)\)。斐波那契数列问题的求解也是如此。对于#120来说，子问题的划分是这样的 ---- 假设到最高层以下所有节点的路径花费都已经计算出来了，那么从跟节点到叶子节点的最佳路径就是从所有第二层节点中选择一个最小的。于是，算法就是从最底层一直往上求解。只是这里的记忆化是无法用滚动数组来压缩内存消耗的。
另外，再来看leetcode#322例子中的一个细节点，即，某些子孙问题可能是不存在结果的，这种不存在在个别情况下是无需考虑的，比如#70中所有的子问题都是有解且每个子问题对最终解都是有用的。这里可以统一为记忆化数组填充一个最值，或者像Java的Optional类型那样单独用一个字段或是否为空来表示存在与否，示例代码如下。

// leetcode#322
import java.util.Arrays;
import java.util.OptionalInt;

class Solution {
    public static void main(String[] args) {
        var s = new Solution();
        var coins = new int[][]{{1, 2, 5}, {2}, {1}};
        var amount = new int[]{11, 3, 0}; // 5+5+1,
        var ans = new int[]{3, -1, 0};
        for (int i = 0; i < ans.length; ++i) {
            System.out.println(ans[i] == s.coinChange(coins[i], amount[i]));
        }
    }

    public int coinChange(int[] coins, int amount) {
        OptionalInt[] ans = new OptionalInt[amount + 1];
        Arrays.fill(ans, OptionalInt.empty());
        ans[0] = OptionalInt.of(0);
        for (int i = 1; i <= amount; ++i) {
            for (var c : coins) {
                int iMinusCoin = i - c;
                if (iMinusCoin < 0 || ans[iMinusCoin].isEmpty()) { // breakdown
                    continue;
                }
                if (ans[i].isPresent()) {
                    ans[i] = OptionalInt.of(Math.min(ans[iMinusCoin].getAsInt() + 1, ans[i].getAsInt()));
                } else {
                    ans[i] = OptionalInt.of(ans[iMinusCoin].getAsInt() + 1);
                }
            }
        }
        return ans[amount].orElse(-1);
    }
}