一、零钱兑换 I 自顶向下、使用备忘录(HashMap)的递归解法 // 备忘录Map<Integer, Integer> memoMap = new HashMap<>();public int coinChange(int[] coins, int amount) { // 查备忘录，避免重复计算 if (memoMap.containsKey(amount)) { return memoMap.get(amount); } // base case if (amount == 0) return 0; // 下面的递归入参，假如 amount - coin < 0，则返回 -1 if (amount < 0) return -1; // 最差的情况，就是使用 amount 个面值为 1 的硬币，而 amount + 1 就是个不存在的值，下面要比较最小值，则每次递归都使用 amount + 1 比较求最小值即可 int res = amount + 1; for (int coin : coins) { // 子问题（目标金额减去当前 coin） int subProblem = coinChange(coins, amount - coin); if (subProblem == -1) continue; // 求最值，即 res 与 子问题加上一个 coin(与上面`目标金额减去当前 coin`相对应，即自顶向下的思想) 求最值 res = Math.min(res, subProblem + 1); } res = res == amount + 1 ? -1 : res; memoMap.put(amount, res); return res;}...
本文整理于自己的学习笔记.. 一、打家劫舍 I 自顶向下、使用备忘录的递归解法 自顶向下：递归一般是自顶向下，依赖于子问题优化函数的结果，只有子问题完全求出，也就是子问题的递归返回结果，原问题才能求解。...
葵花宝典 状态转移框架dp[i][k][1]：表示今天是第 i 天，手上持有股票，至今最多允许交易 k 次dp[i][k][0]：表示今天是第 i 天，手上没有持有股票，至今最多允许交易 k 次 /** * 解释：今天我没有持有股票，有两种可能： * 1、要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有； * 2、要么是我昨天持有股票，但是我今天 sell 了，所以我今天没有持有股票了。 * max( 选择 rest， 选择 sell ) */ ...
