算法中的动态规划

算法导论这本书是这样介绍这个算法的，动态规划与分治方法类似，都是通过组合子问题的解来来求解原问题的。再来了解一下什么是分治方法，以及这两者之间的差别，分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。而动态规划与之相反，动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题）。
态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。

AM1ng’s Algorithm Blog！

实验题目：单调递增最长子序列

算法描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

void solve()
{
   for(int i = 1; i <= n; ++i)
    F[i] = 1;
   for(int i = 1; i <= n; ++i)
   {
       for(int j = 1; j < i; ++j)
       {
           if(a[i] > a[j] && F[i] < F[j] + 1)
            F[i] = F[j] + 1;
       }
   }
   for(int i = 1; i <= n; ++i)
    if(F[i] > max_)
        max_ = F[i];
}

More info: 单调递增最长子序列

思路描述

1 各数组解释
int a[1024]; //原数组

int F[1024]; //在i处的长度

int n; //目标数组

2 算法思路
F[i]的含义为：在“可取元素为前i”且“取第i个元素”时最长递增序列的长度。

列出递归关系为： F[i] = max(F[k]) + 1, 1 <= k <= i - 1 && a[i] > a[k]

其实就是利用动态规划的一种思想

采用遍历数组序列，不断更新递增序列的长度以至于来找到最长单调递增序列。

3 复杂度分析
时间复杂度：遍历两个数组，双循环 T=O（n2）

空间复杂度：O（n）

动态规划的个人体会和思考

动态规划又叫做填表法，就是说动态规划就是个填表游戏。
1、自底向上：思想是逆向的，但也能正向解答。两者是相同的，只是求解顺序不一样。
2、状态转移方程：对于这个，我只能说，暴力怎么解，动态规划就怎么解。因为求解动态规划的顺序是先暴力递归——带备忘录的递归——动态规划。并且看博客多了的人会发现，其实递归的递归体就是动态规划的状态转移方程。不同的思考，得出的状态转移方程也不一样。
3、最优子问题：大问题分成小问题，小问题寻找最优解构成大问题的最优解。这一点不必太在意，因为求解的过程就是在求解小问题的最优解。

More info: 动态规划例题

See U next time！