美文网首页
1.4 动态规划

1.4 动态规划

作者: 月影追猎者 | 来源:发表于2020-06-18 20:17 被阅读0次
// 斐波那契数列 - 递归
// fib(n) = fib(n - 1) + fib(n -2)
int fib(n) {
    return (n < 2) ? n : fib(n - 1) + fib(n - 2);
}

T(0) = T(1) = 1, T(n) = T(n - 1) + T(n - 2) + 1
T(n) = O(fib(n + 1)) = O(2n)
各递归实例被大量重复调用,导致算法低效

记忆(memoization):将已计算实例的结果制表备查
动态规划(dynamic programming):颠倒计算方向,自顶而下递归,自底而上迭代

// 斐波那契数列 - 动态规划
int fib(n) {
    f = 0;
    g= 1;
    while (0 < n--) {
        g = g + f;
        f = g - f;
    }
    return g;
}

T(n) = O(n)

子序列(subsequence),由序列中若干字符(元素),按原相对次序构成。
最长公共子序列(LCS, longest common subsequence),两个序列公共子序列中最长者。

递归
对于序列A[0, n]与序列B[0, m],LCS(A, B)有3种情况:
0) 若n = -1或m = -1,则取作空序列("")
1) 若A[n] = B[m] = 'X',则取作LCS(A[0, n), B[0, m)) + 'X'
2) 若A[n] ≠ B[m],则取LCS(A[0, n], B[0, m))与LCS(A[0, n), B[0, m])较长者

迭代
0/) 将所有子问题列成一张表
1/) 颠倒计算方向,从LCS(A[0], B[0])开始依次计算所有项
dp[i][j]=\left\{\begin{array}{cc} 0 & i=0 \text { or } j=0 \\ dp[i-1][j-1]+1 & i,j>0 \text { and } x_{i} = y_{i} \\ \max(dp[i][j-1], dp[i-1][j]) & i,j>0 \text { and } x_{i} \neq y_{i} \end{array}\right.

public int longestCommonSubsequence(String text1, String text2) {
    if (text1 == null || text2 == null || text1.length() == 0 || text2.length() == 0) return 0;
    char[] chas1 = text1.toCharArray();
    char[] chas2 = text2.toCharArray();
    int m = chas1.length, n = chas2.length;
    int[][] dp = new int[m][n];
    dp[0][0] = chas1[0] == chas2[0] ? 1 : 0;
    for (int i = 1; i < m; i++) dp[i][0] = chas1[i] == chas2[0] ? 1 : dp[i - 1][0];
    for (int j = 1; j < n; j++) dp[0][j] = chas1[0] == chas2[j] ? 1 : dp[0][j - 1];
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            if (chas1[i] == chas2[j]) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
        }
    }
    return dp[m - 1][n - 1];
}

相关文章

  • 1.4 动态规划

    T(0) = T(1) = 1, T(n) = T(n - 1) + T(n - 2) + 1T(n) = O(f...

  • Algorithm进阶计划 -- 动态规划(上)

    动态规划动态规划的基本原理动态规划的运用 1. 动态规划的基本原理 动态规划(Dynamic Programmi...

  • 4. 动态规划算法

    1. 动态规划算法总结2. 漫画:什么是动态规划?3.算法之动态规划4. 动态规划-算法

  • 动态规划 Dynamic Programming

    从运筹学和算法的角度综合介绍动态规划 算法分类总结动态规划与静态规划的关系浅析静态规划和动态规划动态规划解非线性规...

  • 《数据结构与算法之美》27——初识动态规划

    前言 今天开始学习动态规划,一共有三节,分别是:初识动态规划、动态规划理论、动态规划实战。今天这一节就是初识动态规...

  • 算法3:动态规划

    5.动态规划5.1 什么是动态规划?5.2 自底向上的动态规划:5.3 自顶向下的动态规划5.4 0-1背包问题:...

  • 动态规划

    动态规划(Dynamic Programming) 本文包括: 动态规划定义 状态转移方程 动态规划算法步骤 最长...

  • Dynamic Programming(动态规划)类算法分析随笔

    #动态规划 关于动态规划,先摘一段[wiki][1]的描述: ``` 动态规划(英语:Dynamic progra...

  • 什么是动态规划

    目录 动态规划解决了什么 什么是动态规划 典型的动态规划 1. 动态规划解决了什么 的思想就是将大问题拆分成小问题...

  • 斐波那契数列

    递归解法 动态规划解法1 动态规划解法2

网友评论

      本文标题:1.4 动态规划

      本文链接:https://www.haomeiwen.com/subject/navztktx.html