专栏文章

1.6日集训总结

llyxqqq1
个人记录参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqkt7c5
此快照首次捕获于
2025/12/04 06:26
3 个月前
此快照最后确认于
2025/12/04 06:26
3 个月前
查看原文

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：确定此无后效性

代码

CPP
#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 诞生了记忆化搜索

记忆化搜索

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

码子

CPP
#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

递推条件：

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

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

③具有重叠子问题。

④具有无后效性

  • 定义状态 dp[i]表示斐波那契数列第i项

  • 确定答案 求dp[n]

  • 求状态转移方程 dp[x]=dp[x-1]+dp[x-2]

  • 边界条件 第一和第二项没法求

代码也码上

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...