归档：2021/10 - Hi AM1ng！

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

AM1ng’s Algorithm Blog！

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

算法描述

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！

实验题目：maximum number in a unimodal array（单峰数组中的最大数目）

算法描述

int biosearch( int a[],int left,int right)
{
    while(left<=right)//满足二分法的条件，同时可以用于判断二分法何时停止
    {
        int max=(left+right)/2; //二分法循环后缩小范围
        if(a[max]>a[max-1]&&a[max]>a[max+1])//max大于左右，即为峰值，符合目的
        {
            return max;

        }
        if(a[max]>a[max+1]&&a[max]<a[max-1])//max大于右边小于左边 最大值在right左边 从右往左缩小范围 更新右指针
        {
        right=max-1;
        }
    else{
        left = max+1;//同上理 最大值在left右边 从左往右缩小范围 更新左指针
        }
        
    }
    
}

分治法的个人体会和思考

分治法解释：面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

基本步骤：分解、求解子问题、合并。

思考：分治法很直观明了的让我们作为计算机系的学生去体会到了算法的意义和目的，联想到数据结构课上学的快排，二分法，堆排等算法，不难理解分治法其实早已穿插在以前的学习中。但是总的目的都是要对算法进行优化，寻找最优解，过程中要进行复杂度分析，不一定所有情况都必须用分治法或者分治法里是否还需要考虑最优解。

See U next time！