算法学习之路：使用最简单的方式给你讲讲动态规划算法

2021-09-06  本文已影响0人  攻城狮Chova
动态规划算法

动态规划算法

斐波那契数列

直接递归

int fib(int N) {
    if (N == 1 || N == 2) {
        return 1;
    } 
    return fib(N-1) + fib(N-2);
}

这是最简单易懂的直接递归的方法,同时也是效率最低的方法,可以通过画出递归树看出

  • 当N=20时,斐波那契数列递归树分析:
    • 要计算f(20),就要计算出f(19)和f(18),然后要计算f(19),就要计算出f(18)和f(17),以此类推.最后到f(2)和f(1)的时候,结果已知.此时递归树结束
    • 根据递归算法时间复杂度等于子问题个数乘以解决一个子问题需要的时间:
      • 子问题个数: 也就是递归树中节点的总数.因为二叉树的节点总数为指数级别,所有子问题的个数为O(2N)
      • 解决一个子问题需要的时间: 因为这个算法中没有循环,只有f(n-1)+f(n-2)一个加法操作,所有时间为O(1)
      • 直接递归算法时间复杂度: O(2n),为指数级别.相当复杂
    • 观察递归树,分析出算法低效的原因:
      • 存在大量的重复计算
      • f(18)被计算了两次,以f(18)为根的递归树体量巨大,多算一遍,就会耗费大量时间
      • 而且,不止f(18)这一个节点会被重复计算,进而导致算法低下
      • 这个问题就是动态规划的第一个性质 : 重叠子问题

带备忘录的递归算法

int fib(int N) {
    if (N < 1) {
        return 0;
    }
    // 备忘录初始化为0 
    vector<int> memo(N+1, 0);
    // 初始化最简情况
    return helper(memo, N); 
}

int helper(vector<int>& memo, int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    // 已经计算过的直接返回
    if (memo[n] != 0) {
        return memo[n];
    }
    memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
    return memo[n];
}
  • 带备忘录的递归算法的递归树分析:
    • 带备忘录的递归树算法是将一棵存在巨量冗余的递归树通过剪枝, 改造成了一幅不存在冗余的递归图,极大减少了子问题,即递归树中节点的个数
    • 根据递归算法时间复杂度等于子问题个数乘以解决一个子问题需要的时间:
      • 子问题个数: 即递归树中节点的总数.由于不存在冗余计算,子问题就是f(1),f(2)...f(20),数量和输入的规模n成正比,所以子问题的个数就是O(n)
      • 解决一个子问题需要的时间: 因为这个算法中没有没有循环,只有加法操作,所以时间为O(1)
      • 带备忘录的递归算法时间复杂度: O(n).比直接递归算法高效得多

DP数组的迭代算法

int fib(int N) {
    vector<int> dp(N+1, 0);
    dp[1] = dp[2] = 1;
    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[N];
}

DP Table和备忘录的递归树剪枝后的结构很相似,只不过是反过来计算而已.实际上,带备忘录的递归解法中的备忘录, 最终完成的就是这个DP Table. 所以带备忘录的递归算法和DP数组的迭代算法在大部分情况下的算法效率是相同的

斐波那契数列解法补充

int fib(int n) {
    if (n == 1 || n ==2) {
        return 1;
    }
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

凑零钱问题

直接递归

def coinChange(coins: List[int], amount: int):
    def dp(n):
        if n==0: return 0
        if n < 0: return -1
        # 求最小值,所以初始化为正无穷
        res = float('INF')
        for coin in coins:
            subproblem = dp(n - coins)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        return res if res != float('INF') else -1
    return dp(amount);

带备忘录的递归算法

def coinChanges(coins: List[int], amount: int):
    # 备忘录
    memo = dict()
    def dp(n):
        # 查看备忘录,避免重复计算
        if n in memo: return memo[n]
        # 如果备忘录中不存在,则进行计算
        if n = 0: return 0
        if n < 0: return -1
        # 求最小值,所以初始化为正无穷
        res = float('INF')
        for coin in coins:
            subproblem = dep(n - coin)
            if subproblem == -1: continue
            res = min(res, 1 + subproblem)
        # 将计算结果记入备忘录
        memo[n] = res if res != float('INF') else -1
        return memo[n]
    return dep(amount)

DP数组的迭代算法

int coinChanges(vector<int> coins, int amount) {
    // 数组大小为amount+1,初始值也为amount+1
    vector<int> dp(amount + 1, amount + 1);
    /*
     * dp[i] = x:
     *  当目标金额为i时,至少需要x枚硬币   
     */
     for (int i = 0; i < dp.size(); i++) {
        // 内层for求所有子问题+1的最小值
        for (coin in coin) {
            // 如果子问题无解,则跳过循环
            if (i - coin < 0) {
                continue;
            }
            dp[i] = min(dp[i], 1 + dp[i - coin])
        }
     }
     return (dp[amount] == dp[amount + 1]) ? -1 : dp[amount];
}

总结

上一篇 下一篇

猜你喜欢

热点阅读