DP讲解 I

Jerry_zpl · 2024-09-21 21:19:38 · 个人记录

DP

• 边界条件需特殊考虑，如斐波那契额数列的特殊情况有dp_{ 1} 和 dp_{ 2}。要将 dp_{ 1} 和 dp_{ 2} 都赋值为 1。即 dp[1]=1,dp[2]=1;
• 答案为 dp[n]!

说了这么多，总得坐电梯吧！

D1180 上台阶

题目大意: 楼梯有 n (0<n<70) 阶台阶,上楼时可以一步上 1 阶,也可以一步上 2 阶,也可以一步上 3 阶，编程计算共有多少种不同的走法。

思路：还蛮简单的,我们可以画个图:
不难发现，走到第 x 个阶梯的方案数=走到第 x-1 个阶梯的方案数+走到第 x-2 个阶梯的方案数+走到第 x-3 个阶梯的方案数。所以，状态转移方程为:

然后要考虑的就是边界，走到第 1,2,3 层的方案数如果不特殊考虑，方案数就会为 0 。所以要特殊考虑，即:

注意：必须要预处理到第 x阶楼梯的方案数，否则时间复杂度为O(N T)，必超时！
CODE:

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dp[1000005];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  //边界条件考虑：
    dp[1]=1;
    dp[2]=2;
    dp[3]=4;
    for(int i=4;i<=1000000;i++) dp[i]=dp[i-1]+dp[i-2]+dp[i-3];//预处理前10000000层的方案数，套上转移方程就行了
    int n;
    while(cin>>n)//使用while(cin>>n)效果更好
    {
        if(n==0) break;
        cout<<dp[n]<<"\n";//答案为dp[n]
    }
    return 0;
}

P1115 最大子段和

题目大意：给出一个长度为 n 的序列 a ，选出其中连续且非空的一段使得这段和最大。

思路：

• 首先要知道，啥是子段。
  子段的定义：从数列 q 中取连续的一段数且非空，所形成的就是子段。
• 定义转移方程：dp[i] 是以第 i 个数作为结尾的所有子段的最大和
• 求状态转移方程\begin{cases} dp[i]=a[i]：自成子段 \\ dp[i]=dp[i-1]+a[i] ：跟前面的元素拼起来 \\比较2种方法看那种更好\end{cases}
• 边界条件，即考虑 dp[1] ,因为第 1 个的前面没有数。 dp[1]=a[1]
  CODE:

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int dp[1000005];//定义dp数组
int main()
{
    ios::sync_with_stdio(0);//关闭同步流
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[1]=a[1];
    for(int i=1;i<=n;i++) dp[i]=max(a[i],dp[i-1]+a[i]);//看自成子段的和多还是以第i个数为结尾的子段和多，直接套上转移方程
    int maxi=-1e9;//设为最小值
    for(int i=1;i<=n;i++) maxi=max(maxi,dp[i]);//只要求最大值，答案不一定是dp[n]
    cout<<maxi;//输出最大值
    return 0;
}

dp难死了qwq,qaq

THE END,QWQ!