1.6日集训总结

· · 个人记录

DP

如果你的亲戚没学过计算机

A：dp是个啥？

Q：是动态规划。

A：由什么推来的？

Q：递归。

A：用什么优化？

Q：记忆化递归。

此时你应该得心应手，临危不惧

但......

A：它有什么优缺点，要有什么步骤，什么前提......

局势发展到这就不可控了

所以今天就带大家了解一下

递归 记忆化递归 DP

1.啥是递归？

递归可以拆分成一系列的子问题

递归具有最小子问题

不怎么华丽的分割线

来看一道题

斐波那契数列

做这道题我们拿出吃蟹四件套

啊，不是。是递归四件套。

1：定义递归函数 dfs（x）表示第x位的斐波那契数列

2：递归函数的最小子问题

①：第1位是0

②：第2位是1

3：写出表达式 f(x)=f(x-1)+f[x-2]

4：确定此无后效性

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int dfs(int x)
{
    //边界条件考虑
    if(x==1) return 1;
    if(x==2) return 1;
    return dfs(x-1)+dfs(x-2);//拆分子问题
}
signed main()
{
    cin>>n;
    cout<<dfs(n);//递归
    return 0;
}

但会TLE

为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么 为什么？

给大家画个图：

光是2就出现了5次，so 诞生了记忆化搜索

记忆化搜索

还是那道题 我们用一个数组把每一项存起来，有东西就存，没东西就算。

码子

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,f[1000005];
int dfs(int x)
{
    //边界条件考虑
    if(x==1) return 1;
    if(x==2) return 1;
        if(f[x]!=0)
            return f[x];
    return f[x]=dfs(x-1)+dfs(x-2);//拆分子问题
}
signed main()
{
    cin>>n;
    cout<<dfs(n);//递归
    return 0;
}

dp

递推条件：

① 问题可以拆分成一系列的子问题。

②最小子问题可以直接得到答案。

③具有重叠子问题。

④具有无后效性

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n,dp[1000005];
signed main()
{
    cin>>n;
    dp[1]=1;
    dp[2]=1;
    for(int i=3;i<=n;i++)
        dp[i]=(dp[i-1]+dp[i-2])%1000;
    cout<<dp[n]<<endl;
    return 0;
}