2022-3-19 ccpc 刷题心得

5月3日ccpc省赛还有13天左右，决定先刷动态规划的题，之后有时间就刷dfs和bfs。

今天刷了4题动态规划，都是比较简单的。

DP1 斐波那契数列

#include<bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {

  int f[41]={0},n=0;

  f[1]=1,f[2]=1;

  cin>>n;

  if(n==1||n==2)

  {

    cout<<1;

    return 0;

  }

  else

  {

    for (int i = 3; i <= n; i++)

    {

      f[i]=f[i-1]+f[i-2];

    }

    cout<<f[n];

  }

  return 0;

}

基础中的基础。

DP2 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：$0\le n\le 40$

要求：时间复杂度：O(n)，空间复杂度： O(1)

code：

#include<bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {

  int f[41]={1},n=0;

  f[1]=1,f[2]=2;

  cin>>n;

  if(n==1)

  {

    cout<<1;

    return 0;

  }

  else if(n==2)

  {

    cout<<2;

    return 0;

  }

  else

  {

    for (int i = 3; i <= n; i++)

    {

      f[i]=f[i-1]+f[i-2];

    }

    cout<<f[n];

  }

  return 0;

}

这让我想起少年班的那个神棍。

和斐波那契数列一样只不过发f（2）= 2

DP3 跳台阶扩展问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。

数据范围：$1\le n\le 20$
进阶：空间复杂度 O(1) ， 时间复杂度 O(1)

code：

#include<bits/stdc++.h>

using namespace std;

//an=a₁*qⁿ⁻¹

int main(int argc, char const *argv[]) {

  int n=0;

  cin>>n;

  cout<<pow(2,n-1);

  return 0;

}

考虑    f(n)=f(n-1)+f(n-2)+....+f(1)

            且f(n-1)= f(n-2)+.....+f(1)

所以f（n）= 2f（n-1）

所以可以用动态规划来解

但题目要求时间复杂度为O(1)

所以仔细思考后 即可用等差公式 an=a₁*qⁿ⁻¹ 其中 q=2，a₁=1

所以结果可为 pow(2,n-1)

我想起那个p=np？的难题

DP4 最小花费爬楼梯

给定一个整数数组 $cost$ ，其中 $cost[i]$ 是从楼梯第$i$个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 $1\le n\le 10$ ，数组中的值满足 $1\le cost\le 10$

code：

#include<bits/stdc++.h>

using namespace std;

int main(int argc, char const *argv[]) {

  int n;

  int cost[100000]={0};

  int pay[100000]={0};

  cin>>n;

  for (int i = 0; i < n; i++) {

    cin>>cost[i];

  }

  if(n==1||n==0)

  {

    cout<<0;

  }

  pay[1]=cost[1],pay[0]=cost[0];

  for (int i = 2; i <= n; i++) {

    //if(pay[i-1]!=pay[i-2])

      pay[i]=min(pay[i-2],pay[i-1])+cost[i];

    // else

    //   pay[i]=

  }

  // for (int i = 0; i <= n; i++) {

  //   cout<<i<<":"<<pay[i]<<endl;

  // }

  cout<<pay[n]-cost[n];

  return 0;

}

下次写这种题目主要每个函数，数组，变量的定义都要十分清楚，最好写纸上或写上备注！

这题的思路主要是 当到L（n）， n》1时考虑最后一步还是两步，这用min（）来区别。

最后到n层楼的代价，则是 从楼底到跨出n层楼所需的代价减去只跨出n层楼的代价即可。