投稿
  1. 首页
  2. 随笔

力扣算法 Java 刷题笔记【动态规划篇 DP】hot100（一）动态规划解题核心框架 & 斐波那契数 & 零钱兑换 5

文库网 • 2022-12-16 • 随笔 • 阅读 22

力扣算法 Java 刷题笔记【动态规划篇 DP】hot100（一）动态规划解题核心框架 & 斐波那契数 & 零钱兑换 5,第1张

力扣算法 Java 刷题笔记【动态规划篇 DP】hot100（一）动态规划解题核心框架 & 斐波那契数 & 零钱兑换 5

文章目录
  • 1. 什么是动态规划：
  • 2. 求解动态规划
    • 2.1 核心问题是穷举：
    • 2.2 求状态转移方程框架
    • 2.3 什么是状态转移方程 & 状态
  • 3. 举例
    • 3.1 斐波那契数
    • 3.2 零钱兑换

1. 什么是动态规划：

动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法，只不过在计算机问题上应用比较多，比如说让你求最长递增子序列呀，最小编辑距离呀等等。

动态规划（dynamic programming) 与分治法相似，都是通过组合子问题的解来求解原问题，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子问题。通常按照下面4个步骤来设计一个动态规划算法：

  1. 刻画一个最优解的结构特征。
  2. 递归地定义最优解的值
  3. 计算最优解的值，通常采用自底向上的方法
  4. 利用计算出的信息构造一个最优解
    这是算法导论上的定义，但是这个定义对于初学者来说并没有很大的帮助，因为不知道如何划分子问题和刻画最优解的结构
2. 求解动态规划 2.1 核心问题是穷举：

  • 首先，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。

  • 而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。

    要符合「最优子结构」，子问题间必须互相独立。

  • 另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的「状态转移方程」，才能正确地穷举。

2.2 求状态转移方程框架

以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素。具体什么意思等会会举例详解，但是在实际的算法问题中，写出状态转移方程是最困难的，这也就是为什么很多朋友觉得动态规划问题困难的原因，

我来提供我研究出来的一个思维框架，辅助你思考状态转移方程：

  • 明确 base case
  • 明确「状态」：也就是原问题和子问题中会变化的变量。
  • 明确「选择」 ：也就是导致「状态」产生变化的行为。
  • 定义 dp 数组/函数的含义。
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)
2.3 什么是状态转移方程 & 状态

这里，引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式：

为啥叫「状态转移方程」？其实就是为了听起来高端。你把 f(n) 想做一个状态 n，这个状态 n 是由状态 n - 1 和状态 n - 2 相加转移而来，这就叫状态转移，仅此而已。

你会发现，上面的几种解法中的所有 *** 作，例如 return f(n - 1) + f(n - 2)，dp[i] = dp[i - 1] + dp[i - 2]，以及对备忘录或 DP table 的初始化 *** 作，都是围绕这个方程式的不同表现形式。可见列出「状态转移方程」的重要性，它是解决问题的核心。而且很容易发现，其实状态转移方程直接代表着暴力解法。

千万不要看不起暴力解，动态规划问题最困难的就是写出这个暴力解，即状态转移方程。只要写出暴力解，优化方法无非是用备忘录或者 DP table，再无奥妙可言。

3. 举例 3.1 斐波那契数

地址: https://leetcode-cn.com/problems/fibonacci-number/submissions/
2021/12/15
做题反思：注意备忘录的位置
解法一：自顶向下（递归）

class Solution {
    int[] memo = null;
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        if (memo == null) {
            memo = new int[n + 1];
        }
        if (memo[n] != 0) {
            return memo[n];
        }
        memo[n] = fib(n - 1) + fib(n - 2);
        return memo[n];
    }
}

子问题个数，即图中节点的总数，由于本算法不存在冗余计算，子问题就是 f(1), f(2), f(3) … f(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。

解决一个子问题的时间，同上，没有什么循环，时间为 O(1)。

所以，本算法的时间复杂度是 O(n)。

实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。

若不加备忘录：
首先计算子问题个数，即递归树中节点的总数。显然二叉树节点总数为指数级别，所以子问题个数为 O(2^n)。
然后计算解决一个子问题的时间，在本算法中，没有循环，只有 f(n - 1) + f(n - 2) 一个加法 *** 作，时间为 O(1)。
所以，这个算法的时间复杂度为二者相乘，即 O(2^n)，指数级别，爆炸。

解法二：自底向上（dp 数组的迭代解法）

class Solution {
    public int fib(int n) {
        if (n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0; dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}


解法三：优化解法二的空间复杂度 -> 状态压缩

class Solution {
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }

        int[] dp = new int[n + 1];
        int pre = 0, cur = 1;
        for (int i = 2; i <= n; i++) {
            int sum = pre + cur;
            pre = cur;
            cur = sum;
            dp[i] = cur;
        }
        
        return dp[n];
    }
}

有人会问，动态规划的另一个重要特性「最优子结构」，怎么没有涉及？下面会涉及。斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在说明重叠子问题的消除方法，演示得到最优解法逐步求精的过程。下面，看第二个例子，凑零钱问题。

3.2 零钱兑换

地址: https://leetcode-cn.com/problems/coin-change/
2021/12/16
解法一：自顶向下（递归）
做题反思：subProblem
1.有辅助函数 1

int[] memo;

int coinChange(int[] coins, int amount) {
    memo = new int[amount + 1];
    // dp 数组全都初始化为特殊值
    Arrays.fill(memo, -666);

    return dp(coins, amount);
}

int dp(int[] coins, int amount) {
    if (amount == 0) return 0;
    if (amount < 0) return -1;
    // 查备忘录，防止重复计算
    if (memo[amount] != -666)
        return memo[amount];

    int res = Integer.MAX_VALUE;
    for (int coin : coins) {
        // 计算子问题的结果
        int subProblem = dp(coins, amount - coin);
        // 子问题无解则跳过
        if (subProblem == -1) continue;
        // 在子问题中选择最优解，然后加一
        res = Math.min(res, subProblem + 1);
    }
    // 把计算结果存入备忘录
    memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
    return memo[amount];
}

1.有辅助函数 2

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] memo = new int[amount + 1];
        Arrays.fill(memo, -666);
        return dp(coins, amount, memo);
    }

    int dp(int[] coins, int amount, int[] memo) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        if (memo[amount] != -666) {
            return memo[amount];
        }
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subProblem = dp(coins, amount - coin, memo);
            if (subProblem == -1) {
                continue;
            }
            res = Math.min(res, subProblem + 1);
        }
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        return memo[amount];
    }
}

2.无辅助函数

class Solution {
    int[] memo = null;
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (amount < 0) {
            return -1;
        }
        
        if (memo == null) {
            memo = new int[amount + 1];
            Arrays.fill(memo, -666);
        }
        if (memo[amount] != -666) {
            return memo[amount];
        }
        
        int res = Integer.MAX_VALUE;
        for (int coin : coins) {
            int subProblem = coinChange(coins, amount - coin);
            if (subProblem == -1) {
                continue;
            }
            res = Math.min(res, subProblem + 1);
        }   
        memo[amount] = (res == Integer.MAX_VALUE) ? -1 : res;
        
        return memo[amount];
    }
}

那么，既然知道了这是个动态规划问题，就要思考如何列出正确的状态转移方程？

  1. 确定 base case，这个很简单，显然目标金额 amount 为 0 时算法返回 0，因为不需要任何硬币就已经凑出目标金额了。

  2. 确定「状态」，也就是原问题和子问题中会变化的变量。由于硬币数量无限，硬币的面额也是题目给定的，只有目标金额会不断地向 base case 靠近，所以唯一的「状态」就是目标金额 amount。

  3. 确定「选择」，也就是导致「状态」产生变化的行为。目标金额为什么变化呢，因为你在选择硬币，你每选择一枚硬币，就相当于减少了目标金额。所以说所有硬币的面值，就是你的「选择」。

  4. 明确 dp 函数/数组的定义。我们这里讲的是自顶向下的解法，所以会有一个递归的 dp 函数，一般来说函数的参数就是状态转移中会变化的量，也就是上面说到的「状态」；函数的返回值就是题目要求我们计算的量。就本题来说，状态只有一个，即「目标金额」，题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义 dp 函数：

    dp(n) 的定义：输入一个目标金额 n，返回凑出目标金额 n 的最少硬币数量。

解法二：自底向上
做题反思：dp[i - coin]

class Solution {
    public int coinChange(int[] coins, int amount) {
         int[] dp = new int[amount + 1];
         Arrays.fill(dp, amount + 1);
         dp[0] = 0;
         for (int i = 0; i <= amount; i++) {
             for (int coin : coins) {
                 if (i - coin < 0) {
                     continue;
                 }  
                 dp[i] = Math.min(dp[i], dp[i - coin] + 1);
             }
         }
         return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zaji/5671475.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
文库网 文库网 一级用户组
0 0
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表（0条）

保存