• home > theory > algorithm > leetcode >

    DP笔记(4):线性动态规划—零钱兑换、2键/4键键盘

    Author:zhoulujun Date:

    零钱兑换(322 Coin Change)零钱兑换 II(518 Coin Change 2)

    零钱兑换兑换问题

    322 可以使用动态规划或回溯算法求解,而 518 通常使用动态规划求解。 本篇都用动态规划来解题

    零钱兑换

    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

    你可以认为每种硬币的数量是无限的。

    示例 1:输入:coins = [1, 2, 5], amount = 11   输出:3    解释:11 = 5 + 5 + 1

    示例 2:输入:coins = [2],        amount = 3     输出:-1

    示例 3:输入:coins = [1],        amount = 0     输出:0

    当我一眼看完题目,我判断出这道题应该要用动态规划的思维来做,主要有两个原因:

    • 有可选择的东西(硬币)

    • 求到达一个目标数(amount)的最小硬币数(也就是最优解)

    解决动态规划问题,就是一个求最优解的问题,同时也是一个求最优子解的问题,在零钱问题中,求到amount的最小硬币数,就是求到amount前子问题的最小硬币数。

    前子问题是什么?

    我们先举个例子,输入: coins = [1, 2, 5], amount = 11  输出: 3

    目标数是11,那目标数的子问题是什么?

    没错,就是 amount - coins,在这道题中就是10, 9, 6

    那题就转换成了去求到达目标数10,到达目标数9,到达目标数6的最小硬币数,

    继续这样缩小范围,直到最基本的问题,也就是amount == 1的时候。

    我们采用自下而上的方式进行思考。仍定义 F(i) 为组成金额 iii 所需最少的硬币数量,假设在计算 F(i) 之前,我们已经计算出 F(0)−F(i−1) 的答案。 则 F(i) 对应的转移方程应为

    image.png

    前面我们说了,动态规划问题要找出状态和选择,

    状态是什么?

    状态就是到达这个目标数的最小硬币数!

    选择是什么?选择就是这个硬币我选还是不选?

    依据是什么?依据是能不能让我硬币数达到最小,

    比如到达目标数8,是让 5 + 1 + 1 + 1呢? 还是5 + 2 + 1呢?

    当然就是后者,这就是选择。

    dp数组记录的是什么?是状态。

    那可以转换成我们的状态转移方程了,

    // dp[i] 初始化为最大值
    dp[i] = MAX_VALUE
        
    dp[i] = min(dp[i - coins] + 1, dp[i])
    // i 代表当前目标数
    // coins代表硬币数额
    // +1,表示加上一个硬币数

    状态转移方程的问题解决了,这道题也就解决了一半了



    2键/4键键盘

    四键键盘

    假设你有一个特殊的键盘包含下面的按键:

    • Key 1: (A):在屏幕上打印一个 'A'。

    • Key 2: (Ctrl-A):选中整个屏幕。

    • Key 3: (Ctrl-C):复制选中区域到缓冲区。

    • Key 4: (Ctrl-V):将缓冲区内容输出到上次输入的结束位置,并显示在屏幕上。

    现在,你只可以按键 N 次(使用上述四种按键),请问屏幕上最多可以显示几个 'A'呢?

    • 样例 1:  输入: N = 3    输出: 3     解释:   我们最多可以在屏幕上显示三个'A'通过如下顺序按键: A, A, A

    • 样例 2:  输入: N = 7    输出: 9     解释:  我们最多可以在屏幕上显示九个'A'通过如下顺序按键: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

    如何在 N 次敲击按钮后得到最多的 A?我们穷举呗,对于每次按键,我们可以穷举四种可能,很明显就是一个动态规划问题。

    第一种思路

    这种思路会很容易理解,但是效率并不高,我们直接走流程:对于动态规划问题,首先要明白有哪些「状态」,有哪些「选择」

    具体到这个问题,对于每次敲击按键,有哪些「选择」是很明显的:4 种!就是题目中提到的四个按键:A、Ctrl-A(C-A)、Ctrl-C(C-C)、和Ctrl-V(C-V)。

    接下来,思考一下对于这个问题有哪些「状态」?或者换句话说,我们需要知道什么信息,才能将原问题分解为规模更小的子问题?

    你看我这样定义三个状态行不行:

    1. 剩余的按键次数,用n表示;

    2. 当前屏幕上字符 A 的数量,用a_num表示;

    3. 剪切板中字符 A 的数量,用copy表示。

    如此定义「状态」,就可以知道 base case:当按键次数用完时(即 n 为0),屏幕上字符A的数量(即 a_num)就是我们想要的答案

    结合刚才说的 4 种「选择」,我们可以把这几种选择通过状态转移表示出来:

    状态转移:

    根据每种按键操作,我们可以将状态转移表示出来:

    1. 按下A键:增加一个字符A,同时消耗1次按键次数。

      • 新状态:dp(n - 1, a_num + 1, copy)

    2. 按下Ctrl-V(C-V)键:将剪切板中的字符A粘贴到屏幕上,同时消耗1次按键次数。

      • 新状态:dp(n - 1, a_num + copy, copy)

    3. 按下Ctrl-A(C-A)和Ctrl-C(C-C):全选并复制屏幕上的字符A到剪切板,同时消耗2次按键次数。

      • 新状态:dp(n - 2, a_num, a_num)

    这样可以看到问题的规模n在不断减小,肯定可以到达n = 0的 base case,所以这个思路是正确的:

    function maxA(n) {
        const memo = new Map();
    
        function dp(n, a_num, copy) {
            if (n <= 0) return a_num;
            const key = `${n},${a_num},${copy}`;
            if (memo.has(key)) return memo.get(key);
    
            const pressA = dp(n - 1, a_num + 1, copy);
            const pressCV = dp(n - 1, a_num + copy, copy);
            const pressCA_CC = n > 1 ? dp(n - 2, a_num, a_num) : 0;
    
            const result = Math.max(pressA, pressCV, pressCA_CC);
            memo.set(key, result);
            return result;
        }
        return dp(n, 0, 0);
    }

    在这个代码中,我们使用一个递归函数 dp 来计算在剩余 n 次按键下,最大可能的字符A数量。我们用一个 memo(记忆化存储)来避免重复计算。

    n 是一个明确的变量,最多为 N,但是 a_num 和 copy 可以在理论上达到非常高的值,这导致状态空间变得非常大,从而使得算法的复杂度非常高,可能会达到 O(N^3 ) 甚至更高。

    为了改进这个算法,我们需要重新定义状态,以便减少状态空间和优化时间复杂度。我们可以通过将状态定义得更加抽象,专注于每一步操作时的选择和影响,从而简化问题。

    第二种思路

    这种思路稍微有点复杂,但是效率高。继续走流程,「选择」还是那 4 个,但是这次我们只定义一个「状态」,也就是剩余的敲击次数n。

    这个算法基于这样一个事实,最优按键序列一定只有两种情况:

    • 要么一直按A:A,A,…A(当 N 比较小时)。

    • 要么是这么一个形式:A,A,…C-A,C-C,C-V,C-V,…C-V(当 N 比较大时)。

    因为字符数量少(N 比较小)时,C-A C-C C-V这一套操作的代价相对比较高,可能不如一个个按A;而当 N 比较大时,后期C-V的收获肯定很大。这种情况下整个操作序列大致是:开头连按几个A,然后C-A C-C组合再接若干C-V,然后再C-A C-C接着若干C-V,循环下去

    换句话说,最后一次按键要么是A要么是C-V。明确了这一点,可以通过这两种情况来设计算法:

    int[] dp = new int[N + 1];
    // 定义:dp[i] 表示 i 次操作后最多能显示多少个 A
    for (int i = 0; i <= N; i++) 
        dp[i] = max(
                这次按 A 键,
                这次按 C-V
            )

    对于「按A键」这种情况,就是状态i - 1的屏幕上新增了一个 A 而已,很容易得到结果:

    // 按 A 键,就比上次多一个 A 而已
    dp[i] = dp[i - 1] + 1;

    刚才说了,最优的操作序列一定是C-A C-C接着若干C-V,所以我们用一个变量j作为若干C-V的起点。那么j之前的 2 个操作就应该是C-A C-C了:

    function maxA(N) {
      const dp = Array(N + 1).fill(0); // dp[0] = 0;
      for (let i = 1; i <= N; i++) {
        dp[i] = dp[i - 1] + 1;// 按下A键
        for (let j = 2; j < i; j++) { // 按下C-A C-C组合和若干次C-V键
          // 全选&复制 dp[j-2],连续粘贴i-j次  屏幕上共 dp[j-2]*(i-j+1)个 A
          dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
        }
      }
      return dp[N];
    }

    其中j变量减 2 是给C-A C-C留下操作数,看个图就明白了:

    4键盘问题动态递归算法

    这样,此算法就完成了,时间复杂度 O(N^2),空间复杂度 O(N),这种解法应该是比较高效的了。

    总结:

    动态规划难就难在寻找状态转移,不同的定义可以产生不同的状态转移逻辑,虽然最后都能得到正确的结果,但是效率可能有巨大的差异。

    回顾第一种解法,重叠子问题已经消除了,但是效率还是低,到底低在哪里呢?抽象出递归框架:

    def dp(n, a_num, copy):
        dp(n - 1, a_num + 1, copy),    # A
        dp(n - 1, a_num + copy, copy), # C-V
        dp(n - 2, a_num, a_num)        # C-A C-C

    看这个穷举逻辑,是有可能出现这样的操作序列C-A C-C,C-A C-C...或者C-V,C-V,...。显然这种操作序列的结果不是最优的,但是我们并没有想办法规避这些情况的发生,从而增加了很多没必要的子问题计算

    回顾第二种解法,我们稍加思考,发现最优的序列应该是这种形式:A,A..C-A,C-C,C-V,C-V..C-A,C-C,C-V..。

    根据这个事实,我们重新定义了状态,重新寻找了状态转移,从逻辑上减少了无效的子问题个数,从而提高了算法的效率。


    两个键的键盘

    最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作:

    • Copy All(复制全部):复制这个记事本中的所有字符(不允许仅复制部分字符)。

    • Paste(粘贴):粘贴 上一次 复制的字符。

    给你一个数字 n ,你需要使用最少的操作次数,在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

    示例 1:输入:3   输出:3

    解释: 最初, 只有一个字符 'A'。

    • 第 1 步, 使用 Copy All 操作。

    • 第 2 步, 使用 Paste 操作来获得 'AA'。

    • 第 3 步, 使用 Paste 操作来获得 'AAA'。

    示例 2:输入:n = 1   输出:0

    对于一个数n,他需要进行多少次的复制全部和粘贴的操作,比如25个A,最大能被25整除(比25小的数中)的数是5,那么我需要复制5个A粘贴5次就可以得到25个A,那么怎么得到5个A,最大能被5整除(比5小的数中)的数是1,因此只能通过复制一个A并粘贴5次。

    • 当n = 1时,已经有一个A了,我们不需要其他操作,返回0

    • 当n = 2时,我们需要复制一次,粘贴一次,返回2

    • 当n = 3时,我们需要复制一次,粘贴两次,返回3

    • 当n = 4时,这就有两种做法,一种是我们需要复制一次,粘贴三次,共4步,另一种是先复制一次,粘贴一次,得到AA,然后再复制一次,粘贴一次,得到AAAA,两种方法都是返回4

    • 当n = 5时,我们需要复制一次,粘贴四次,返回5

    • 当n = 6时,我们需要复制一次,粘贴两次,得到AAA,再复制一次,粘贴一次,得到AAAAAA,共5步,返回5

    可以看出对于n,至多需要n步,即cppppp....,而如果可以分解成相同的几份,则可以减少次数,比如n=6时,目标是AAAAAA,可以分解为两个AAA或者三个AA

    假设 n%m=0,n/m=min_val; m的范围[1,n-1](总共需要输出n个A,一次复制M个,最小粘贴min_val次

    那么动态转移方程为:

    dp[n]=dp[m]+(min_val-1)+1;
    • dp[m]代表要得到m个A最少需要多少次操作;

    • min_val-1代表需要对m个A进行粘贴的次数;

    最后+1是复制m个A的次数。

    function minSteps(n) {
      const dp = new Array(n + 1).fill(0); // 创建一个长度为 n+1 的数组 dp,初始化所有元素为 0
      dp[1] = 0; // dp[1] 初始化为 0,因为已经有一个 'A'
    
      for (let i = 2; i <= n; ++i) {  
        let min_val = Infinity;  // 初始化最小粘贴次数为无穷大
        let index;
    
        for (let j = i - 1; j >= 1; --j) {// 找出最大的能被 i 整除的 j
          if (i % j === 0) {
            let val = i / j;
            if (val < min_val) {
              min_val = val; // 最少的粘贴次数
              index = j;     // 在哪个位置粘贴
            }
          }
        }
        dp[i] = dp[index] + min_val - 1 + 1;// 更新 dp[i]
      }
    
      return dp[n];// 找出最大的能被 i 整除的 j
    }

    这个如果你没有看明白。那么,为了简化问题,我们可以反过来思考:

    假设我们已经有 i 个 'A',如何获得这些 'A' 是通过一些 j 个 'A' 复制若干次得到的

    因此,我们需要找到一个 j,使得 j 个 'A' 通过粘贴操作能得到 i 个 'A',即 i % j == 0。

    更具体地:如果 i 能被 j 整除(即 i % j == 0),说明可以通过先获得 j 个 'A',然后粘贴若干次(具体是 i / j 次)得到 i 个 'A'

    例如,假设我们要得到 i = 16 个 'A':

    1. 我们可以通过先获得 8 个 'A',然后粘贴一次得到 16 个 'A'。操作步骤是:

      1. 先获得 8 个 'A' 的操作次数是 dp[8]。

      2. 再粘贴一次得到 16 个 'A',总操作次数是 dp[8] + 1。

    2. 而要获得 8 个 'A',可以先获得 4 个 'A' 然后粘贴一次,操作次数是 dp[4] + 1。

      1. 获得 4 个 'A' 是通过先获得 2 个 'A' 然后粘贴一次,操作次数是 dp[2] + 1。

      2. 获得 2 个 'A' 是通过先获得 1 个 'A' 然后粘贴一次,操作次数是 dp[1] + 1。

    通过这种方式递归地计算,我们可以找到最优的操作次数。

    状态转移方程

    dp[i] 表示获得 i 个 'A' 的最小操作次数。那么:

    • 对于每个 i,我们要找到最大的 j(1 <= j < i),使得 i % j == 0。

    • 一旦找到这个 j,可以通过 dp[j] 的操作次数,再加上从 j 到 i 的粘贴次数,即 i / j - 1 次粘贴操作(注意第一次的“复制”操作,所以加 1),总操作次数为 dp[j] + i / j。

    标准动态规划代码:

    function  minSteps(n) {
      if (n == 1) return 0;
      // 对每一个格子,如果i可以被j除尽,说明j个A可以通过复制粘贴得到i个A,复制粘贴次数为i / j。
      let dp = new Array(n + 1).fill(0);//到i第个A的最小操作次数
      dp[1] = 0;// dp[1] 初始化为 0,因为已经有一个 'A',1个A 不需要复制
    
      for (let i = 2; i <= n; ++i) {// 对于每个 i 从 2 到 n,找到最大的能被 i 整除的 j,并更新 dp[i]。
        for (let j = 1; j <= i / 2; ++j) {// 找出最大的能被 i 整除的 j
          if (i % j == 0) {//找到可以整除的因子
            dp[i] = Math.min(dp[i], dp[j] + (i / j));//状态转移
          }
        }
      }
      return dp[n];
    }


    参考文章:

    https://waiterxiaoyy.github.io/2020/03/24/LeetCode学习笔记——零钱凑数(动态规划)/

    650.只有两个键的键盘(动态规划) https://blog.csdn.net/Linke66/article/details/120384747

    Leetcode [650] 只有两个键的键盘 & Leetcode [651] 四键键盘 动态规划 https://www.cnblogs.com/zl1991/p/14742514.html

    动态规划:不同的定义产生不同的解法  https://mp.weixin.qq.com/s/DeanOw0acBNU1ZoI4cE8nw




    转载本站文章《DP笔记(4):线性动态规划—零钱兑换、2键/4键键盘》,
    请注明出处:https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9112.html