首页 / 算法 / 【算法总结】动态规划 (Dynamic Programming)

【算法总结】动态规划 (Dynamic Programming)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法总结】动态规划 (Dynamic Programming)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11921字，纯文字阅读大概需要18分钟。

内容图文

[算法总结] 动态规划

本文组织结构如下：

前言
最长公共子序列（LCS）
最长不下降子序列（LIS）
最大连续子序列之和
最长回文子串
数塔问题
背包问题（Knapsack-Problem）
矩阵链相乘
总结

前言

在学过的算法当中，DP给我的感觉是最难的了。借着本次写blog好好复习一下这个算法。

众所周知，DP算法的关键点：

抽象出问题的状态表示
定义状态转移方程
填表顺序

最长公共子序列

最长公共子序列（Longest Common Subsequence,LCS），顾名思义，是指在所有的子序列中最长的那一个，子序列要求都出现过并且出现顺序与母串保持一致。

例如，给定字符串 a和 b:

string a = "cnblog"
string b = "belong";

blog 都出现过，且字母顺序一致，那就一个公共子序列（在这里也是最长的公共子序列）。

状态定义：

dp[i, j] 表示 a[0,...,i] 与 b[0,...j] 的最长公共子序列的长度

那么现在的目的就是求出：dp[alen, blen]

状态转移方程：

            = 0                             if i=0 or j=0
dp[i,j]     = dp[i-1,j-1]+1                 if a[i]=b[j]
            = max(dp[i-1,j], dp[i, j-1])    if a[i]!=b[j]

观察可知，每一个 dp[i,j] 都是依赖于 “左边、上边、左上角” 的三个元素之一，所以对于数组 dp ，可以从前往后填写。

DP算法一个关键的地方就是需要初始化边界。在此处，就是需要初始化 dp 数组的第 0 列，以及第 0 行。

代码如下，其中 plat 数组用于求解最大的公共子序列是什么（回溯法+DFS，具体不展开细讲，其他blog写了很多）。

int lcs(string &a, string &b)
{
    string result = "";
    int alen = a.length();
    int blen = b.length();
    vector<vector<int>> dp(alen + 1, vector<int>(blen + 1, 0));
    vector<vector<char>> plat(alen + 1, vector<char>(blen + 1, 0));
    for (int i = 1; i <= alen; i++)
    {
        for (int j = 1; j <= blen; j++)
        {
            if (a[i - 1] == b[j - 1])  //此处为什么是 a[i-1] 和 b[j-1] 呢？
                dp[i][j] = dp[i - 1][j - 1] + 1, plat[i][j] = '\\';
            else
            {
                if (dp[i - 1][j] >= dp[i][j - 1])
                    dp[i][j] = dp[i - 1][j], plat[i][j] = '|';
                else
                    dp[i][j] = dp[i][j - 1], plat[i][j] = '-';
            }
        }
    }

    print(plat, alen, blen);
    return dp.back().back();
}

上面的代码中，需要特别留意和加以理解的地方就是内层循环中的 if 语句。

可以使用下图来理解，实际上当 i=0 or j=0 时，表示的是字符串为空串，即 s="" 。但是在代码当中，字符串的下标是从 0 开始计数的。在上面的状态转移方程当中，dp[1,1] 实际上需要判断两个字符串的第一个字符是否相等，即 a[0] == b[0]。

      B D C A B A
    0 1 2 3 4 5 6 
  0   0 0 0 0 0 0 
A 1 0
B 2 0
C 3 0
B 4 0
D 5 0
A 6 0
B 7 0

完整代码：

#include <iostream>
#include <cassert>
#include <string>
#include "leetcode.h"
#include <vector>
using namespace std;
string a = "ABCBDAB", b = "BDCABA";
// string a = "xyxxzxyzxy", b = "zxzyyzxxyxxz";
void print(vector<vector<char>> &plat, int i, int j)
{
    if (i <= 0 || j <= 0)
    {
        return;
    }
    if (plat[i][j] == '-')
    {
        print(plat, i, j - 1);
    }
    else if (plat[i][j] == '|')
    {
        print(plat, i - 1, j);
    }
    else if (plat[i][j] == '\\')
    {
        print(plat, i - 1, j - 1);
        cout << a[i - 1];
    }
    else
    {
    }
}
int lcs(string &a, string &b)
{
    string result = "";
    int alen = a.length();
    int blen = b.length();
    vector<vector<int>> dp(alen + 1, vector<int>(blen + 1, 0));
    vector<vector<char>> plat(alen + 1, vector<char>(blen + 1, 0));
    for (int i = 1; i <= alen; i++)
    {
        for (int j = 1; j <= blen; j++)
        {
            if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1, plat[i][j] = '\\';
            else
            {
                if (dp[i - 1][j] >= dp[i][j - 1])
                    dp[i][j] = dp[i - 1][j], plat[i][j] = '|';
                else
                    dp[i][j] = dp[i][j - 1], plat[i][j] = '-';
            }
        }
    }

    print(plat, alen, blen);
    return dp.back().back();
}

int main()
{
    cout << lcs(a, b);
}

/*
            = 0                             if i=0 or j=0
dp[i,j]     = dp[i-1,j-1]+1                 if a[i]=b[j]
            = max(dp[i-1,j], dp[i, j-1])    if a[i]!=b[j]
 */

最长不下降子序列

不下降子序列就是说：从一个数组当中选出若干个元素，按照下标顺序排列，该序列要求非降序排列。

例如有数组：

int a[] = {1, 2, 3, -9, 3, 9, 0, 11};

那么不下降子序列可以是：

1 2 3 3 9 11
1 2 3
...

求这些序列的最大长度。

我们令 dp[i] 表示：以 a[i] 结尾的，最长不下降子序列的长度。

那么对于 dp[i]，可以有以下状态转移方程：

dp[0] = 1
dp[i] = 1
      = max(1, max(dp[j]+1)), 0<=j<=(i-1) and a[i]>=a[j]

（其实这里的状态转移方程比代码还难理解，还是看代码好 = =）

代码：

int solve(int a[], int len)
{
    vector<int> dp(len, 0);
    dp[0]=1;
    for (int i=1;i<len;i++)
    {
        dp[i] = 1;
        for (int j=0;j<i;j++)
        {
            if (a[i]>=a[j])
                dp[i]=max(dp[i], dp[j]+1);
        }
    }
    int val = -1;
    for (auto x:dp)
        val=max(val,x);
    return val;
}
int main()
{
    int a[] = {1, 2, 3, -9, 3, 9, 0, 11};
    cout << solve(a, 8);
}

最大连续子序列之和

这又是一道最XX的题目。

给定 A[1,...,n] ，求 i 和 j , 1<=i<=j<=n，使得 sum(A[i,...,j]) 最大，输出这个最大和。

比如

-2 11 -4 13 -5 2

最大的、连续的子序列就是：

11 -4 13

最大和是 20 。

正常的思路是穷举每一个左端点和右端点，但是这样的复杂度是 O(n*n)，其次每次对区间求和又需要 O(n) 的复杂度，只要数据量大，这种方法是不明智的。

来看一下DP的解法。

状态定义：

dp[i]: 以 a[i] 结尾的，最大连续子序列的和。

在这种情况下，在 i 位置，要么只取 a[i]，要么取 a[i] 加上“前面”的。

转移方程：

dp[0] = a[0]
dp[i] = max(a[i], dp[i-1]+a[i])

代码如下：

int solve(int a[], int len)
{
    vector<int> dp(len, 0);
    dp[0] = a[0];
    for (int i=1;i<len;i++)
    {
        dp[i]=max(a[i], dp[i-1]+a[i]);
    }
    int val = -1;
    for (auto x:dp)
        val = max(val, x);
    return val;
}
int main()
{
    int a[] = {-2, 11, -4, 13, -5, -2};
    cout << solve(a, 6) << endl;
}
/*
常见错误：
dp[i]是[0,i]的最大连续子序列之和
dp[i+1] = max(dp[i], dp[i]+a[i])
(这么定义没法保证连续)
正解：
dp[i]表示必须以a[i]结尾的连续序列最大和，为什么“必须”？（因为要求连续）
那么：
dp[i] = max(a[i], dp[i-1]+a[i])
 */

最长回文子串

子串要求是连续的。

求出字符串S的所有子串中，最长的子串。

还是直接说怎么用DP求解。

定义状态：

dp[i,j]表示：S[i,...,j] 是否为回文串。

边界条件：

dp[i,i] = true              //只有一个字符的字符串
dp[i,i+1] = (s[i]==s[i+1])

状态转移方程：

dp[i,j] = dp[i+1,j-1] && (s[i]==s[j])

细心的你可能会发现，这次的 “填表” 不能从前往后填了，因为 dp[i, j] 依赖于它的左下角的元素。这次需要从 “左上” 到 “右下” 这样斜着填表。（先算左下的，后算右上的）

图解说明一下为什么斜着填，假设 s = "abba", len = 4

dp数组初始状态：
  a b b a
a 1 
b 0 1 
b 0 0 1 
a 0 0 0 1

执行s[i]==s[i+1]:
  a b b a
a 1 0 
b 0 1 1 
b 0 0 1 0
a 0 0 0 1
==>
  a b b a
a 1 0 0 
b 0 1 1 0
b 0 0 1 0
a 0 0 0 1
==>
  a b b a
a 1 0 0 1
b 0 1 1 0
b 0 0 1 0
a 0 0 0 1

代码：

int solve(string &s)
{
    int len = s.length();
    if (len == 0 || len == 1)
        return len;
    if (len == 2)
        return (s[0] == s[1]) + 1;
    vector<vector<bool>> dp(len, vector<bool>(len, 0));
    int maxlen = 1;
    for (int i = 0; i <= len - 2; i++)
    {
        dp[i][i] = 1, dp[i][i + 1] = (s[i] == s[i + 1]);
        if (dp[i][i + 1])
            maxlen = 2;
    }
    dp[len - 1][len - 1] = 1;
    int i = 0;
    int j = 2;
    int ti, tj;
    do
    {
        ti = i, tj = j;
        while (i < len && j < len)
        {
            dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j]);
            if (dp[i][j] == true)
                maxlen = max(maxlen, j - i + 1);
            i++, j++;
        }
        i = 0, j = tj + 1;
    } while (!(j == len));
    return maxlen;
}
int main()
{
    string s[] = {"PATZJUJZTACCBCC", "", "1", "12", "22", "232", "2332"};
    for (int i = 0; i < 7; i++)
        cout << solve(s[i]) << endl;
}

/*
dp[i][j]表示str[i,j]是否为一个回文串，若是则1，若否则0
那么：
        = 1                         if i=j
dp[i,j] = (s[i]==s[j])              if i+1=j
        = dp[i+1,j-1]&&s[i]==s[j]   other
 */

数塔问题

给定如下的树塔：

level = 5
        5
       /  \
      8    3
     /  \ /  \
    12   7   16
   /  \/   \/  \    
  4   10   11   6
 / \ /  \ /  \ / \
9   5    3    9   4

第 i 层有 i 个数字, 从第 1 层到第 n 层,每次只能向下走一个数字, 求解所有路径中, 和最大是多少?

首先，我们使用一个二维数组去存储这个树塔，那么对于某个节点 a[i,j] ，它的左右子树如下：

a[i][j]
   |      \
a[i+1][j]  a[i+1][j+1]

定义状态:

dp[i,j] 表示从(i,j)出发，到达底层的所有路径中得到的最大和

显然，边界条件为：

dp[level-1][j] = a[level-1][j], 0<=j<level

状态转移函数：

dp[i,j] = a[i,j] + max(dp[i+1,j], dp[i+1,j+1]), 0<=i<levl-1

显然，填表的顺序是自底向上。

完整代码:

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#define MAXR 100
#define MAXC 100
using namespace std;
int a[MAXR][MAXC] = {{0}};
int solve(int level)
{
    vector<vector<int>> dp(level + 1, vector<int>(level + 1, 0));
    auto &v = dp.back();
    for (int j = 1; j <= level; j++)
        v[j] = a[level][j];
    for (int i = level - 1; i >= 1; i--)
    {
        for (int j = 1; j <= i; j++)
        {
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];
        }
    }
    for (int i = 1; i <= level; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            cout << setw(3) << dp[i][j];
        }
        cout << endl;
    }
    return dp[1][1];
}
void print(int level)
{
    for (int i = 1; i <= level; i++)
    {
        for (int j = 1; j <= i; j++)
            cout << setw(4) << a[i][j];
        cout << endl;
    }
}
int main()
{
    int level;
    cin >> level;
    for (int i = 1; i <= level; i++)
    {
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
    }
    cout << solve(level);
}

/*
        a[i][j]
       /    \
a[i+1][j]    a[i+1][j+1]


dp[i,j] 表示从(i,j)出发，到达底层的所有路径中得到的最大和
dp[1,1] = max(dp[2,1], dp[2,2])+a[1,1]
dp[i,j] = max(dp[i+1,j], dp[i+1,i+1])+a[i,j]
...
dp[r,c] = a[r,c]
 */

/*
Sample1:
5
5
8 3
12 7 16
4 10 11 6
9 5 3 9 4
 */

0/1背包问题

给定背包容量 C ，物品体积 volume[n]，物品价值 value[n]，每个物品只有一个。

求：在背包容量允许的情况下，装入背包物品的最大价值。

定义状态：

dp[i,j] 表示: 在背包容量为 j 的, 供选择物品为前 i 项, 装入背包的最大价值。

状态转移方程：

dp[i,j] = 0             if i=0 or j=0
        = dp[i-1,j]      if j < volume[i]
        = max(dp[i-1,j], dp[i-1,j-volume[i]] + value[i])    if j > volume[i]

完整代码：

#include <iostream>
#include <vector>
#include "leetcode.h"
using namespace std;
const int items = 4;
const int C = 9;
int volume[items + 1] = {-1, 2, 3, 4, 5};
int values[items + 1] = {-1, 3, 4, 5, 7};
vector<vector<int>> dp(items + 1, vector<int>(C + 1, 0));
int solve()
{
    for (int i = 1; i <= items; i++)
    {
        for (int j = 1; j <= C; j++)
        {
            if (j < volume[i])
                dp[i][j] = dp[i - 1][j];
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - volume[i]] + values[i]);
            }
        }
    }
    printvv(dp);
    return dp.back().back();
}
int main()
{

    cout << solve() << endl;
}

矩阵链相乘

如果两个矩阵可以相乘，那么必然满足:

M1[a,b]  
M2[b,c]

此外, M1与M2相乘, 所计算的乘法次数为: a*b*c。所得到的矩阵为 M3[a,c] 。

给定矩阵:

M1 2*10
M2 10*2
M3 2*10

计算：(M1M2)M3，乘法次数为：2*2*10+2*10*2 = 80。

计算：M1(M2M3)，乘法次数为：10*10*2+2*10*10 = 400。

在这里，我们想找到一种计算顺序，使得计算：

M1 M2 M3 ... Mn

的乘法次数达到最小。

首先，由于矩阵相乘必须满足：M1的列数等于M2的行数。

我们采用下面的数据结构去存储 n 个矩阵的行数与列数。

int nums[N+1]
nums[i]   表示 Mi 的行数,
nums[i+1] 表示 Mi 的列数.
nums[n]   表示 M(n-1) 的列数

然后，定义问题的状态：

dp[i,j] 表示 Mi ... Mj 的最小乘法次数

边界条件：

dp[i,i] = 0

下面推导状态转移方程，考虑整数 k (i<k<=j)，将 M[i,j] 的乘法拆分为三步:

计算 A = M[i,k-1] ，A的行列分别为：nums[i], nums[k]
计算 B = M[k,j]，B的行列分别为：nums[k], nums[j+1]
计算 A*B

由此可知，M[i,j]的乘法次数为：

[i,k-1] + [k,j] + nums[i] * nums[j+1] * nums[k]

因此，状态转移方程为：

dp[i,j] = min(dp[i,k] + dp[k,j] + nums[i] * nums[j+1] * nums[k]),   i<k<=j

看到这里，可能有点头大，不知道怎么去填 dp 表。其实是按“斜线”的顺序填入，与 最长回文子串 类似。

下面来简单看一下过程，假设有五个矩阵（ M0 M1 M2 M3 M4 ）相乘，其行列存储如下：

int nums[N + 1] = {5, 10, 4, 6, 10, 2};

边界条件初始化：

M 0 1 2 3 4
0 0
1 * 0
2 * * 0
3 * * * 0
4 * * * * 0
==>
  M  0  1   2   3   4
  0  0 200 320  ？
  1  *   # ### 640 
  2  *   *   # 240 ###
  3  *   *   *   0 ###
  4  *   *   *   *   #

以上述 dp[0,3] 为例，说明递推过程：

dp[0,3] = min
         (
            dp[0,0] + dp[1,3] + ...
            dp[0,1] + dp[2,3] + ...
            dp[0,2] + dp[3,3] + ...
         )

其中，... 代表三个 nums[i] 相乘的常数项，可自行对照递推式代入。在这里，需要特别注意 dp[i,j]的依赖项（实际上是“同行”与“同列” 的所有元素）。

完整代码：

#include "leetcode.h"
#include <cmath>
#define N 5
#define MAXINT 9999
int nums[N + 1] = {5, 10, 4, 6, 10, 2};
vector<vector<int>> dp(N, vector<int>(N, MAXINT));
int solve()
{
    for (int i = 0; i < N; i++)
        dp[i][i] = 0;
    for (int d = 1; d < N; d++)
    {
        for (int i = 0; i < (N - d); i++)
        {
            int j = i + d;
            for (int k = i + 1; k <= j; k++)
            {
                dp[i][j] = min(dp[i][j], dp[i][k - 1] + dp[k][j] + nums[i] * nums[k] * nums[j + 1]);
            }
        }
    }
    for (auto &v : dp)
    {
        for (auto x : v)
        {
            cout << setw(4);
            if (x == MAXINT)
                cout << '*';
            else
            {
                cout << x;
            }
        }
        cout << endl;
    }
    return dp[0][N - 1];
}
int main()
{
    cout << solve() << endl;
}

/*
M0...M(n-1): nums[i]   表示 Mi 的行数,
             nums[i+1] 表示 Mi 的列数.
             nums[n]   表示 M(n-1) 的列数
 */
/*
    dp[i,j] 表示 Mi ... Mj 的最小乘法次数
    边界: dp[i,i] = 0;
    递推: dp[i,j] = min(dp[i,k-1]+dp[k,j] + a[i]*a[k]*a[j+1]), i<k<=j
    ==>
    dp[0,n-1] = min(dp[0, k-1] + dp[k,n-1] + a[0]*a[k]*a[n]), 0<k<=n-1
 */

总结

没总结，有空再补充。

内容总结

以上是互联网集市为您收集整理的【算法总结】动态规划 (Dynamic Programming)全部内容，希望文章能够帮你解决【算法总结】动态规划 (Dynamic Programming)所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/715906.html

来源：【匿名】

【上一篇】常见排序算法（7种）【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【【算法总结】动态规划 (Dynamic Programming)】教程文章相关的互联网学习教程文章

树，二叉树和算法总结【代码】【图】

一.思维导图二.概念笔记树的存储结构双亲表示法:当算法中需要在树结构中频繁地查找某结点的父结点时，使用双亲表示法最合适孩子表示法:适用于查找某结点的孩子结点孩子兄弟表示法:可以用孩子兄弟表示法将普通树转化为二叉树二叉树的性质性质一: 在二叉树的第k层上最多有2^(k-1)个结点性质二: 高度为k的二叉树至多有2^k-1个结点，最少有k个结点性质三: 对任何一棵二叉树T,如果其终端结点数为n0，度为2的结点数为n2,则n0 = n2 + ...

十大经典排序算法总结【代码】【图】

0、排序算法说明0.1 排序的定义对一序列对象根据某个关键字进行排序。0.2 术语说明稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；内排序：所有排序操作都在内存中完成；外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；时间复杂度：一个算法执行所耗费的时间。空间复杂度：运行完一个程序所需内存的大小。0....

Memcached 笔记与总结（6）PHP 实现 Memcached 的一致性哈希分布算法【代码】

首先创建一个接口，有 3 个方法：addServer：添加一个服务器到服务器列表中removeServer：从服务器列表中移除一个服务器lookup：在当前的服务器列表中找到合适的服务器存放数据interface distribute{//在当前的服务器列表中找到合适的服务器存放数据publicfunction lookup($key);//添加一个服务器到服务器列表中publicfunction addServer($server);//从服务器列表中删除一个服务器publicfunction removeServer($server); } 再定义一...

查找算法总结(一)—顺序、二分、二叉、红黑【图】

1.顺序查找在查找中我们一个一个顺序的遍历表中的所有键并使用equals（）方法来查找匹配的键。优点：对数组的结构没有特定的要求，可以使用数组或者链表实现，算法简单。缺点：当数组个数n较大时，效率低下。时间复杂度：查找命中时，最大时间复杂度是O(n)，最小时间复杂度是O(1),平均时间复杂度是O(n/2)；未命中时，总需要O(n)次比较。　　　　　　向一个空表中插入N个不同的件需要N2次比较。 2.基于有序数组的二分查找在查找时，...

PHP排序算法的复习和总结【代码】

对于PHP中对数组的元素进行排序，这个是很经常用到的，之前的项目中也有，而且对于几种排序我们都是用的是asort arsort 等PHP原生函数，没有自己去实现，所以就对一下的几个函数进行总结，这个会不断的进行补充，自己也可以好好的复习和总结。直接上代码吧！ 1 <?php2/* 3 * 插入排序（一维数组）4 * 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当的位置，使数列依然有序；直到待排序的数据元素全部插入完成...

分治算法小总结 x【代码】

其实这个题用冒泡排序做的，但用归并排序也能做出来（分析一下此题与逆序对是有相同之处的）由于两者的代码完全一样，就只放一个啦 ~\(≧▽≦)/~啦啦啦1.洛谷 P1116 车厢重组题目描述在一个旧式的火车站旁边有一座桥，其桥面可以绕河中心的桥墩水平旋转。一个车站的职工发现桥的长度最多能容纳两节车厢，如果将桥旋转180度，则可以把相邻两节车厢的位置交换，用这种方法可以重新排列车厢的顺序。于是他就负责用这座桥将进站的车厢...

大数据时代：基于微软案例数据库数据挖掘知识点总结（Microsoft 顺序分析和聚类分析算法）【图】

原文:（原创）大数据时代：基于微软案例数据库数据挖掘知识点总结（Microsoft 顺序分析和聚类分析算法）前言本篇文章继续我们的微软挖掘系列算法总结，前几篇文章已经将相关的主要算法做了详细的介绍，我为了展示方便，特地的整理了一个目录提纲篇：大数据时代：深入浅出微软数据挖掘算法总结连载，有兴趣的童鞋可以点击查阅，本篇我们将要总结的算法为：Microsoft顺序分析和聚类分析算法，此算法为上一篇中的关联规则分析算法的一...

几种常见模式识别算法整理和总结

这学期选了门模式识别的课。发现最常见的一种情况就是，书上写的老师ppt上写的都看不懂，然后绕了一大圈去自己查资料理解，回头看看发现，Ah-ha，原来本质的原理那么简单，自己一開始仅仅只是被那些看似formidable的细节吓到了。所以在这里把自己所学的一些点记录下来，供备忘，也供參考。 1. K-Nearest NeighborK-NN能够说是一种最直接的用来分类未知数据的方法。基本通过以下这张图跟文字说明就能够明确K-NN是干什么的简单来说...

paxos算法学习总结【图】

核心思想分布式系统架构下如何让整体尽快达成一致观点，也就是多个不同观点收敛到一个观点的过程。难点可能会发生少数节点故障，但绝不是大面积故障，不然系统也没法正常工作。由于存在单点故障，因此不可能将观点由某一台机器的统一。共享内存达到一致性的方案不可取。因此，只能是点对点通信。一些概念算法中有三个角色Proposor，Acceptor，Learner算法有两个阶段，一是预提案，二是正式提案。正式提案的内容也就是观点，预提案不...

C++算法之——常用算法总结

http://blog.sina.com.cn/s/blog_61bebe480100v7c7.html 基本的C++算法分为三类：排序算法、树算法、图算法算法思想有三种：递推、分治、动态规划以及贪心算法。本文将简要介绍上面三类算法，介绍时穿插介绍算法思想。一、排序算法 1、基本O(n^2)排序算法：（对基本排序算法的时间复杂度分析主要考虑比较次数、数据交换次数）冒泡排序：针对数组、本地排序、需要交换数据。O(1)额外空间选择排序：一般针对数组、本地排序、需...

回溯算法的一个总结【图】

回溯算法的模板：result = [] def backtrack(路径, 选择列表): ????if 满足结束条件:{ ????????result.add(路径) ????????return ? ? }?? ? //每个for代表的其实就是一位，由这个for引出的下一个backtrack就是这位的下一位????for 选择 in 选择列表:{ ????????做选择????????backtrack(路径, 选择列表) ????????撤销选择? ? }?问题一：子集给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能...

基于C语言的算法总结(不定时更新)【代码】

这篇博客我准备写一些我见过的算法，虽然现在我见过的还很少，但我相信会越来越多，方便日后自己查阅好了开始了求解最大子序列和的最有效的算法 1int MaxSubsequenceSum(constint A[], int N)2{3int ThisSum, MaxSum, j;4// 定义本次循环的和与最大和为0 5 ThisSum = MaxSum = 0; 6// 循环求和 7for (j = 0; j < N; j++)8 {9 ThisSum += A[j]; 10// 判断本次的和与最大和的大小，如果本次和比最大和大，把本次和的值...

排序算法总结【代码】

本文将给出六大经典排序的实现。简单排序算法：冒泡，插入，选择改进排序算法：快排，归并，堆排以下排序用到的交换函数：void swap(int &A, int &B) {int temp = A; A = B; B = temp; }1. 冒泡排序2个相邻的元素相互比较，不满足顺序则交换；每遍历一次数组，使一个元素处于最终位置。时间复杂度O(n2)/**/ 空间复杂度O(1)/**/void BubbleSort(int nums[], intleft, intright) {if (nums == NULL || right-left+1 <= 0)retur...

排序算法总结：一、基数排序【代码】

基数排序(Radix sort)是一种非比较型的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序也分为LSD（Least significant digital）和MSD（Most significant digital）两种方式，LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。以LSD为例，假设原来有一串数值如下所示：　　73, 22, 93, 43, 55, 14, 28, 65, 39, 81　　首先根据个位数的数值，在走访数值时将它们分配至编...

机器学习算法总结（二）

SVM上：这个算法应该是机器学习这门课里最重要的部分了。首先是SVM的思想：找到超平面，将两类中距离最近的点分的越开越好（直至二者相等）。然后是函数间隔和几何间隔的定义，二者之间的区别。接着是超平面模型的建立，看看它是如何将问题转化为凸优化问题的。 SVM第一个难点：拉格朗日对偶。由KKT条件可知，起作用的约束都在边界上，这个会用来解释支持向量。由KKT条件知，在S...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 【算法总结】动态规划 (Dynamic Programming)

【算法总结】动态规划 (Dynamic Programming)

内容导读

内容图文

[算法总结] 动态规划

前言

最长公共子序列

最长不下降子序列

最大连续子序列之和

最长回文子串

数塔问题

0/1背包问题

矩阵链相乘

总结

内容总结

内容备注

内容手机端

【【算法总结】动态规划 (Dynamic Programming)】教程文章相关的互联网学习教程文章

树，二叉树和算法总结【代码】【图】

十大经典排序算法总结【代码】【图】

Memcached 笔记与总结（6）PHP 实现 Memcached 的一致性哈希分布算法【代码】

查找算法总结(一)—顺序、二分、二叉、红黑【图】

PHP排序算法的复习和总结【代码】

分治算法小总结 x【代码】

大数据时代：基于微软案例数据库数据挖掘知识点总结（Microsoft 顺序分析和聚类分析算法）【图】

几种常见模式识别算法整理和总结

paxos算法学习总结【图】

C++算法之——常用算法总结

回溯算法的一个总结【图】

基于C语言的算法总结(不定时更新)【代码】

排序算法总结【代码】

排序算法总结：一、基数排序【代码】

机器学习算法总结（二）

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程