Mod笔记不得不在没更数组的时候更动态规划了

老师让我们做笔记，所以我的Mod笔谈现在更新了！！！

动态规划没有太多固定的代码模板，所以这里只有一个题目答案(false)

动规的特点

1.无后效性 不会回头，只能往前走，方便填表

2.最优子结构 可以分成一个个子结构，一个个解除了就能获得答案

3.重叠子问题 子问题会重叠，相互之间有关联，就像这样

怎么这么像我家男神

———————————————————————————————————————————————————— 那么怎么做动态规划的题目呢？

第一步，看一眼题目，看看能不能用动态规划，只要不符合上面的特点，就不是动规题目

第二步，看看要几个几维数组，设出来

int a[10005],f[10005];

第三步，写状态转移方程，说白了不就是填表吗 要具体题目具体分析

斐波那契数列

f[i]=f[i-1]+a[i]

最大连续子序列的和

f[i]=max(f[i-1]+a[i],a[i]);

第四步，设置初始值 给动态规划数组来个初始值

第五步，找答案 for循环找答案吧

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

下面给大家露一手吧，送大家一个求最大连续子序列的和

一、看看能不能用动态规划 //都是动态规划题目了，肯定能用啊！

二、设置几个一维数组

int n,a[100005],f[10005],ans;

三、写出状态转移方程

f[i]=max(f[i-1]+a[i],a[i]);

四、设置初始值

f[1]=a[1];

五、那必须是for循环找答案啊

for(int i=1;i<=n;i++){
  ans=max(f[i],ans);
}

接下来是求最大连续子序列的和的题解(false)

#include<iostream>
using namespae std;
int n,a[100005],f[100005],ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    f[1]=a[1];
    以下为VIP内容
    cout<<ans;
    return 0;
}