投稿
  1. 首页
  2. C

动态规划入门

code • 2022-4-19 • C • 阅读 57

动态规划入门,第1张

  • 一、状态转移（递推）
    • 基础入门第一题：斐波那契数列
    • 递推其实是最简单的状态转移
    • 然后再是斐波那契数列的简单应用---爬楼梯
    • 使用最小花费爬楼梯
    • 虽然学到这里，并没有什么卵用，但是我们可以从以上的题目总结出我们刷动态规划的大致流程。

    • 1、设计状态
    • 2、写出状态转移方程
    • 3、设定初始状态
    • 4、执行状态转移
    • 5、返回最终的解
    • 接下来我们做一下进阶题，找找感觉：最大子数组和
  • 二、映射（线性dp）
    • 打家劫舍
    • 线性dp：是因为状态数与时间复杂度呈线性关系O(n)
    • 状态转移复杂度O(1)--时间复杂度是与n无关的
  • 三、前缀最值
    • 买卖股票的最佳时期
    • 后缀最值
    • 最大元素替换
    • 最佳观光组合
    • 接雨水

怎么说最近刷到了一个up主，然后他讲题目的方式蛮搞笑的，我就被他给整笑了哈哈哈哈，然后看了一下他的其他视频，然后就来记录一下好了！
（1）
（2）
（3）

一、状态转移（递推）

什么是动态规划？什么是状态转移？什么是空间换时间？

基础入门第一题：斐波那契数列


这里的n不能很大，不然会超过int整数型的最大范围。


这是基础的递推公式。


f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i]=f[i-1]+f[i-2] f[i]=f[i−1]+f[i−2]
初始化第一项和第二项，然后开始用公式来递推。

递推其实是最简单的状态转移 然后再是斐波那契数列的简单应用—爬楼梯


然后这里的递推公式也是
f [ i ] = f [ i − 1 ] + f [ i − 2 ] f[i]=f[i-1]+f[i-2] f[i]=f[i−1]+f[i−2]，也可以叫他状态转移方程。

使用最小花费爬楼梯



这道题目和爬楼梯那道题很相似，我们只不过是从计算方案数转化为了计算最小值。


f [ i ] f[i] f[i]表示爬到第i层的最小花费数。

int n;
int f[1001]={0,0};
for(int i=2;i<n;i++)
f[i]=min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
虽然学到这里，并没有什么卵用，但是我们可以从以上的题目总结出我们刷动态规划的大致流程。

1、设计状态 2、写出状态转移方程 3、设定初始状态 4、执行状态转移 5、返回最终的解 接下来我们做一下进阶题，找找感觉：最大子数组和 



#include

using namespace std;

int main()
{
    int dp[100001];
    int maxv=nums[0];
    dp[0]=nums[0];
    for(int i=1;i<n;i++)
    {
        dp[i]=max(dp[i-1]+nums[i],nums[i]);
        maxv=max(maxv.dp[i]);
    }
    printf("%d",maxv);   
    
    return 0;
}
二、映射（线性dp）

什么是动态规划？什么是线性dp？什么是O(1)?
来吧，来一个中等题压压惊

打家劫舍

规则：如果第i个数取，那么第i+1个或者是第i-1个不能取。


d p [ i ] dp[i] dp[i]表示前i个整数通过某种选取方案能够获得的最大值。


初始状态： d p [ 0 ] = n u m s [ 0 ] dp[0]=nums[0] dp[0]=nums[0] d p [ 1 ] = m a x ( d p [ 0 ] , d p [ 1 ] ) dp[1]=max(dp[0],dp[1]) dp[1]=max(dp[0],dp[1])
咱们的转移方程为
d p [ i ] = m a x ( d p [ i − 1 ] , d p [ i − 2 ] + n u m s [ i ] ) dp[i]=max(dp[i-1],dp[i-2]+nums[i]) dp[i]=max(dp[i−1],dp[i−2]+nums[i])
第i个数不取 第i个数取

#include

using namespace std;

int main()
{
    int dp[110];
   dp[0]=nums[0];
   for(int i=1;i<n;i++)
   {
       if(i==1)//为了防止数组越界
        dp[1]=max(nums[0],nums[1]);
       else dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
   }
   cout<<dp[n-1]<<endl;
    return 0;
}
线性dp：是因为状态数与时间复杂度呈线性关系O(n) 状态转移复杂度O(1)–时间复杂度是与n无关的




由于本题的数字不大，n<=10000，所以我们要合理安排。


所以我们可以把数字映射到数组里。

有点***打家劫舍***那道题的味道。

#include

using namespace std;
int sum[10010],val[10010],nums[10010];
int f(int* nums,int n)//“打家劫舍”的代码
{
    int i;
    int dp[10010];
    dp[0]=nums[0];
    for(int i=1;i<n;i++)
    {
        if(i==1)
            dp[1]=max(nums[0],nums[1]);
        else dp[i]=max(dp[i-1],dp[i-2]+nums[i]);
    }
    return dp[n-1];
}


int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>nums[i];
   memset(sum,0,sizeof sum);
   for(int i=0;i<n;i++)
    sum[nums[i]]++;
   for(int i=0;i<=1000;i++)
    val[i]=i*sum[i];//映射，表示选取i这个数以后能够获得的点数
   cout<<f(val,10001);
    return 0;
}
三、前缀最值 买卖股票的最佳时期





我们用dp[i]表示前i个元素的最小值
状态转移方程
d p [ i ] = m i n ( d p [ i − 1 ] , n u m s [ i ] ) dp[i]=min(dp[i-1],nums[i]) dp[i]=min(dp[i−1],nums[i])
初始状态
d p [ 0 ] = n u m s [ 0 ] dp[0]=nums[0] dp[0]=nums[0]

#include

using namespace std;
const int N=10010;
int preva[N],a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(i==0)
            preva[0]=a[0];
        else preva[i]=min(preva[i-1],a[i]);
    }
    for(int i=1;i<n;i++)
        ans=max(ans,a[i]-preva[i]);
    cout<<ans;
    return 0;
}
后缀最值 最大元素替换


我们用postmax[i]表示从i~n-1里面的最大元素
状态转移方程
p o s t m a x [ i ] = m a x ( p o s t m a x [ i + 1 ] , n u m s [ i ] ) postmax[i]=max(postmax[i+1],nums[i]) postmax[i]=max(postmax[i+1],nums[i])
初始状态
p o s t m a x [ n − 1 ] = n u m s [ n − 1 ] postmax[n-1]=nums[n-1] postmax[n−1]=nums[n−1]

#include

using namespace std;
const int N=10010;
int postmax[N],a[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    int ans=0;
    for(int i=n-1;i>=0;i--)
    {
        if(i==n-1)
            postmax[i]=a[i];
        else postmax[i]=max(postmax[i+1],a[i]);
    }
    for(int i=0;i<n;i++)
      if(i==n-1)
      a[i]=-1;
    else a[i]=postmax[i+1];
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    return 0;
}
最佳观光组合



首先我们根据题意可知
一对景点的评分: n u m s [ i ] + n u m s [ j ] + i − j nums[i]+nums[j]+i-j nums[i]+nums[j]+i−j
然后我们在把他划分一下， ( n u m s [ i ] + i ) + ( n u m s [ j ] − j ) (nums[i]+i)+(nums[j]-j) (nums[i]+i)+(nums[j]−j)
我们会发现前面的是定值，后面的是求前缀最大值。

他们两个相互之间独立。

#include

using namespace std;
const int N=10010;
int premax[N],a[N],nums[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>nums[i];
        a[i]=nums[i]+i;
    }
    int ans=0;
    for(int i=0; i<n; i++)
    {
        if(i==0)
            premax[i]=a[i];
        else premax[i]=max(premax[i-1],a[i]);
    }
    for(int j=1; j<n; j++)
        ans=max(ans,premax[j-1]+nums[j]-j);
    cout<<ans<<endl;
    return 0;
}
接雨水


他其实也就是前缀最值加上后缀最值
题目分析：min(左边最高，右边最高）-自己高度

#include

using namespace std;
const int N=10010;
int premax[N],a[N],postmax[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    int ans=0;
    for(int i=0; i<n; i++)
    {
        if(i==0)
            premax[i]=a[i];
        else premax[i]=max(premax[i-1],a[i]);
    }
    for(int i=n-1;i>=0;i--)
    {
        if(i==n-1)
            postmax[i]=a[i];
        else postmax[i]=max(postmax[i+1],a[i]);
    }
    for(int i=1; i<n; i++)
        ans+=min(premax[i],postmax[i])-a[i];
    cout<<ans<<endl;
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/674350.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-19
下一篇 2022-04-19

发表评论

登录后才能评论

评论列表（0条）

保存