动态规划算法刷题笔记【线性dp】

递推

斐波那契(Fibonacii)数列的递推公式:F(n) = F(n -1) + F(n - 2)

错排问题:F(n) = (n-1) * [F(n-1)+F(n-2)]

解释

例题

一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法

思路

  • 要想跳到第10级台阶,要么是先跳到第9级,然后再跳1级台阶上去;要么是先跳到第8级,然后一次迈2级台阶上去。
  • 同理,要想跳到第9级台阶,要么是先跳到第8级,然后再跳1级台阶上去;要么是先跳到第7级,然后一次迈2级台阶上去。
  • 要想跳到第8级台阶,要么是先跳到第7级,然后再跳1级台阶上去;要么是先跳到第6级,然后一次迈2级台阶上去。

f(10) = f(9)+f(8)
f (9) = f(8) + f(7)
f (8) = f(7) + f(6)

f(3) = f(2) + f(1)

即通用公式为: f(n) = f(n-1) + f(n-2)

动态规划

  • 根据一类多阶段问题的特点,把多阶段决策问题变换为一系列互相联系的单阶段问题,然后逐个加以解决
  • 最优化原理,动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应与一个值,找到具有最优值的解
  • 用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划的基本思路。

基本思路

  1. 穷举分析:当台阶数是1的时候,有一种跳法,f(1) =1;当只有2级台阶时,有两种跳法,第一种是直接跳两级,第二种是先跳一级,然后再跳一级。即f(2) = 2;当台阶是3级时,想跳到第3级台阶,要么是先跳到第2级,然后再跳1级台阶上去,要么是先跳到第 1级,然后一次迈 2 级台阶上去。所以f(3) = f(2) + f(1) =3;当台阶是4级时,想跳到第3级台阶,要么是先跳到第3级,然后再跳1级台阶上去,要么是先跳到第 2级,然后一次迈 2 级台阶上去。所以f(4) = f(3) + f(2) =5;当台阶是5级时…
  2. 确定边界:通过穷举分析,我们发现,当台阶数是1的时候或者2的时候,可以明确知道青蛙跳法。f(1) =1,f(2) = 2,当台阶n>=3时,已经呈现出规律f(3) = f(2) + f(1) =3,因此f(1) =1,f(2) = 2就是青蛙跳阶的边界。
  3. 找规律,确定最优子结构:n>=3时,已经呈现出规律 f(n) = f(n-1) + f(n-2) ,因此,f(n-1)和f(n-2) 称为 f(n) 的最优子结构。一道动态规划问题,其实就是一个递推问题。假设当前决策结果是f(n),则最优子结构就是要让 f(n-k) 最优,最优子结构性质就是能让转移到n的状态是最优的,并且与后面的决策没有关系,即让后面的决策安心地使用前面的局部最优解的一种性质当前在哪,可能从哪里来
  4. 写出状态转移方程:穷举分析,确定边界,最优子结构,我们就可以得出状态转移方程

需满足的条件

  • 最优化原理:一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策如何,其今后的各个策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略。也就是说一个最优策略的子策略,也是最优的。
  • 无后效性:如果某阶段状态给定后,则在这个阶段以后过程的发展不受这个阶段以前各个状态的影响

动态规划与贪心的区别

区别
网上找的,比较好理解的

  • 贪心算法的思路和动态规划有点不一样(个人觉得贪心算法会更简单一点)
  • 动态规划需要枚举每一种最优解的情况(具体就如链接中的最后的凑钱问题:4+1+1、3+3)

最长上升子序列LIS

在这里插入图片描述

子序列不一定是连续的

[NOIP1999]拦截导弹

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入描述

1行,若干个整数(个数≤100000)

输出描述

2行,每行一个整数,第一个数字表示这套系统最多能拦截多少导弹,第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

示例一
输入

389 207 155 300 299 170 158 65

输出

6
2

思路

  • 题目中给出的 不能高于 ,易知:最长不上升序列
  • 题目问的 最少要配备多少套导弹拦截系统 :即遇到后面的比前面的大的时候(也就是不满足不上升序列),就需要加一套系统
  • 比较基础这道题,难度低,套模板

题解

#include<bits/stdc++.h>
using namespace std;
int n=1,a[100005],dp1[100005],dp2[100005],ans1=-1,ans2=-1;
int main(){while(cin>>a[n]) ++n;for(int i=1;i<n;++i){dp1[i]=1,dp2[i]=1;for(int j=1;j<i;++j){if(a[i]<=a[j]) dp1[i]=max(dp1[i],dp1[j]+1); //状态转移方程else dp2[i]=max(dp2[i],dp2[j]+1);}ans1=max(dp1[i],ans1);ans2=max(dp2[i],ans2);}printf("%d\n%d",ans1,ans2);
}

状态转移方程:dp1[i] 表示的是第 i 个位置能达到的最长不上升子序列dp数组一般都是取右端点或者是终点;dp2[i] 表示的是第 i 个位置能达到的最长上升子序列

最长公共子序列LCS

在这里插入图片描述
在这里插入图片描述

[蓝桥杯 2019 国 C] 最长子序列

我们称一个字符串 S S S 包含字符串 T T T 是指 T T T S S S 的一个子序列,即可以从字符串 S S S 中抽出若干个字符,它们按原来的顺序组合成一个新的字符串与 T T T 完全一样。给定两个字符串 S S S T T T,请问 T T T 中从第一个字符开始最长连续多少个字符被 S S S 包含?

输入格式

输入两行,每行一个字符串。第一行的字符串为 S S S,第二行的字符串为 T T T。两个字符串均非空而且只包含大写英文字母。

输出格式

输出一个整数,表示答案。

样例输入 #1

ABCDEABCD
AABZ

样例输出 #1

3

提示

对于 20 % 20\% 20% 的评测用例, 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 20 1 \le |T| \le |S| \le 20 1TS20

对于 40 % 40\% 40% 的评测用例, 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 100 1 \le |T| \le |S| \le 100 1TS100

对于所有评测用例, 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 1000 1 \le |T| \le |S| \le 1000 1TS1000

蓝桥杯 2019 年国赛 C 组 F 题。

思路

  • 大体类似最长公共子序列:状态—— d p [ i ] dp[i] dp[i]表示T字符串 i i i位置最长连续序列,状态转移—— d p [ i ] = d p [ i − 1 ] + 1 dp[i]=dp[i-1]+1 dp[i]=dp[i1]+1(字符相等的情况),初始条件—— d p [ 0 ] = 0 dp[0]=0 dp[0]=0
  • 遍历T字串,以每个T字串的字符和S中的字符相比,如果相等就同向后一个位置,如果不等就让S字符串向后一个位置。时间复杂度 O ( n 2 ) O(n^2) O(n2)
  • 别人的题解:

题解

#include<bits/stdc++.h>
using namespace std;
int main(){string s1, s2;cin >> s1 >> s2;int len = 0;for(int i = 0, j = 0; i < s1.size(); i++){if(s1[i] == s2[j]){j++;len++;}}cout << len;
}  

[HAOI2010]最长公共子序列

字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。
令给定的字符序列 X = “ x 0 , x 1 , … , x m − 1 ” X=“x_0,x_1,…,x_m-1” X=x0x1xm1”,序列Y= “ y 0 , y 1 , … , y k − 1 ” “y_0,y_1,…,y_k-1” y0y1yk1”是X的子序列,存在X的一个严格递增下标序列 < i 0 , i 1 , … , i k − 1 > < i_0,i_1,…,i_k-1 > <i0i1ik1> ,使得对所有的 j = 0 , 1 , … , k − 1 j=0,1,…,k-1 j=01k1,有 x i j = y j x_{i_j} = y_j xij=yj。例如, X = “ A B C B D A B ” X=“ABCBDAB” X=ABCBDAB Y = “ B C D B ” Y=“BCDB” Y=BCDB X X X的一个子序列。对给定的两个字符序列,求出他们最长的公共子序列长度,以及最长公共子序列个数。

输入描述

第1行为第1个字符序列,都是大写字母组成,以”.”结束。长度小于5000。
第2行为第2个字符序列,都是大写字母组成,以”.”结束,长度小于5000。

输出描述

第1行输出上述两个最长公共子序列的长度。
第2行输出所有可能出现的最长公共子序列个数,答案可能很大,只要将答案对100,000,000求余即可。

示例一
输入

ABCBDAB.
BACBBD.

输出

4
7

思路

  • 第一问很简单了,就是模板
  • 第2问的分析:要求长度为 d p ( i , j ) dp(i, j) dp(i,j) L C S LCS LCS 的个数,只需要知道长度为 d p ( i , j ) dp(i, j) dp(i,j) 转移来源的 L C S LCS LCS 的个数,我们就可以推出最终的答案
  • 但是如果开2个二维数组 [ 5005 ] [ 5005 ] [5005][5005] [5005][5005]会出现 M L E MLE MLE,占用空间过大的情况,所以要用滚动数组来优化

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e3 + 10, mod = 1e8;
int n, m, k;
char ch, a[maxn], b[maxn];
ll f[2][maxn], g[2][maxn];
int main(){for (int i = 1; (ch = getchar()) != '.'; a[i] = ch, n = i, i++) ;getchar();for (int i = 1; (ch = getchar()) != '.'; b[i] = ch, m = i, i++) ;for (int i = 0; i <= m; i++) g[0][i] = 1; g[1][0] = 1;for (int i = 1; i <= n; i++, k ^= 1){for (int j = 1; j <= m; j++){g[k ^ 1][j] = 0;f[k ^ 1][j] = (a[i] == b[j]) ? f[k][j - 1] + 1 : max(f[k][j], f[k ^ 1][j - 1]);if (a[i] == b[j]) g[k ^ 1][j] += g[k][j - 1];if (f[k ^ 1][j] == f[k ^ 1][j - 1]) g[k ^ 1][j] += g[k ^ 1][j - 1];if (f[k ^ 1][j] == f[k][j]) g[k ^ 1][j] += g[k][j];if (f[k ^ 1][j] == f[k][j - 1]) g[k ^ 1][j] -= g[k][j - 1];g[k ^ 1][j] %= mod;}}printf("%lld\n%lld\n", f[k][m], g[k][m]);return 0;
}

字符串编辑距离

表示2个字符串之间,由一个字符串转化到另一个字符串所需的最少操作次数。也就是说,编辑距离越小,2个字符串的相似度越大。

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

数字三角形

这种类型的题,能清楚地发现贪心与动态规划的区别

[USACO1.5][IOI1994]数字三角形 Number Triangles

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

        7 3   8 8   1   0 2   7   4   4 
4   5   2   6   5 

在上面的样例中,从 7 → 3 → 8 → 7 → 5 7 \to 3 \to 8 \to 7 \to 5 73875 的路径产生了最大

输入格式

第一个行一个正整数 r r r ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式

单独的一行,包含那个可能得到的最大的和。

样例输入 #1

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出 #1

30

提示

【数据范围】
对于 100 % 100\% 100% 的数据, 1 ≤ r ≤ 1000 1\le r \le 1000 1r1000,所有输入在 [ 0 , 100 ] [0,100] [0,100] 范围内。

思路

  • 如果不是因为在学动态规划,那么在思考的时候可能也会想到搜索,但是对于这类题,搜索会TLE
  • 如果是贪心的话(从上往下),在样例中,会走 7 → 8 → 1 → 7 → 5 7 \to 8 \to 1 \to 7 \to 5 78175,但是没有题目中给出的路径和大。说明:贪心保证的是每一步的最优,但是并非总体最优。所以选择贪心算法的时候,应该要考虑每一步最优所达到的总体解是否会出现较明显的漏洞
  • (补充)从下往上,贪心的方法也可以。从倒数第2排开始,最左边是2,那么它往下会选择5,就将其置换为2+5=7。以此类推,倒数第3排最左边是8,其下方2个是7和12。所以8置换成20。推到第1排:7下方是23和21,选择23。得到答案30这种方法相当于做了个前缀和,考虑了路径,也可以理解为动态规划的方法吧

题解

#include<bits/stdc++.h>
using namespace std;
int n,a[1005][1005];
int main(){scanf("%d",&n);for(int i=1;i<=n;++i)for(int j=1;j<=i;++j) scanf("%d",&a[i][j]);for(int i=n-1;i>=1;--i){for(int j=1;j<=i;++j) a[i][j]+=max(a[i+1][j],a[i+1][j+1]);}printf("%d",a[1][1]);
}

其他

[蓝桥杯 2020 省 AB3] 画中漂流

在梦境中,你踏上了一只木䇝,在江上漂流。

根据对当地的了解,你知道在你下游 D D D 米处有一个峡谷,如果你向下游前进大于等于 D D D 米则必死无疑。

现在你打响了急救电话, T T T 秒后救援队会到达并将你救上岸。水流速度是 1 m / s 1 \mathrm{~m} / \mathrm{s} 1 m/s,你现在有 M M M 点体力。每消耗一点体力,你可以划一秒桨使船向上游前 进 1 m 1 \mathrm{~m} 1 m,否则会向下游前进 1 m 1 \mathrm{~m} 1 m (水流)。 M M M 点体力需在救援队赶来前花光。因为江面太宽了,凭借你自己的力量不可能上岸。

请问,有多少种划桨的方案可以让你得救。

两个划桨方案不同是指:存在某一秒钟,一个方案划桨,另一个方案不划。

输入格式

输入一行包含三个整数 D D D T T T M M M

输出格式

输出一个整数,表示可以让你得救的总方案数,答案可能很大,请输出方案数除以 1000000007 1000000007 1000000007(即 1 0 9 + 7 10^9+7 109+7)的余数。

样例输入 #1

1 6 3

样例输出 #1

5

提示

对于 50 % 50 \% 50% 的评测用例, 1 ≤ T ≤ 350 1 \leq T \leq 350 1T350

对于所有评测用例, 1 ≤ T ≤ 3000 , 1 ≤ D ≤ T , 1 ≤ M ≤ 1500 1 \leq T \leq 3000,1 \leq D \leq T,1 \leq M \leq 1500 1T3000,1DT1M1500

蓝桥杯 2020 第三轮省赛 AB 组 I 题。

思路

  • 可能是对动态规划的知识掌握得本就不太好,刚看到这道题都没什么想法,后面根据chatgpt提供的总结才想到了一些:状态为当前剩余体力和峡谷的距离,方案数用递归来计算。当前状态由消耗了一点体力和没消耗体力转移而来。但是我的想法解决不了如果在一开始就耗尽体力远离峡谷,最后离峡谷的距离比D大的情况感觉应该是不难的题目,但是仍然解决不了
  • 看到别人的思路:和我类似有点相关,但是别人并不把和峡谷距离作为状态,而是作为边界条件难受,感觉自己连基本的变通都不会😩😩😩

题解

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int d, t, m;
long long dp[3005][1505];
int main() {memset(dp, 0, sizeof(dp));cin >> d >> t >> m;dp[0][0] = 1;for(int i = 1; i <= t; i++) {for(int j = 0; j <= m; j++) {int dis = j + d - (i - j);if(dis > 0) {dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;if(j - 1 >= 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;}}}	cout << dp[t][m];
}

[蓝桥杯 2020 省 AB1] 走方格

在平面上有一些二维的点阵。

这些点的编号就像二维数组的编号一样,从上到下依次为第 1 1 1 至第 n n n 行,从左到右依次为第 1 1 1 至第 m m m 列,每一个点可以用行号和列号来表示。

现在有个人站在第 1 1 1 行第 1 1 1 列,要走到第 n n n 行第 m m m 列。只能向右或者向下走。

注意,如果行号和列数都是偶数,不能走入这一格中。

问有多少种方案。

输入格式

输入一行包含两个整数 n n n m m m

输出格式

输出一个整数,表示答案。

样例输入 #1

3 4

样例输出 #1

2

提示

1 ≤ n , m ≤ 30 1\le n,m\le30 1n,m30

蓝桥杯 2020 第一轮省赛 A 组 G 题(B 组 H 题)。

思路

  • 刚开始看,第一反应是 d f s dfs dfs,但是题目要求的是方案数,那么就思考动态规划。这道题以动态规划的思路思考,总算是能思考出一套解法了:状态—— d p [ i ] [ j ] = 到 [ i ] [ j ] dp[i][j]=到[i][j] dp[i][j]=[i][j]的方案数,状态转移—— d p [ i ] [ j ] = d p [ i − 1 ] [ j ] + d p [ i ] [ j − 1 ] dp[i][j]=dp[i-1][j]+dp[i][j-1] dp[i][j]=dp[i1][j]+dp[i][j1]得到(题目给出了限制,所在位置为双偶数的不能走,那么在这里加上特判),边界和起始——第一行第一列的每一个元素都为 1 1 1(因为只能从右边或者上方得到), d p [ n ] [ m ] dp[n][m] dp[n][m]为最终结果。
  • 别人的题解:基本跟我一样,就是特判那里,他们变成了dp[i][j]=0。这个更好,减少了特判,并且能达到相同的效果

题解

完全自己写的题解,虽然非常简单这道题,但是终于能自己独立写出来了🥳🥳🥳

#include<bits/stdc++.h>
using namespace std;
int dp[35][35],n,m;
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) dp[i][1]=1;for(int i=1;i<=m;++i) dp[1][i]=1;for(int i=2;i<=n;++i){for(int j=2;j<=m;++j){if(i%2==0&&j%2==0) dp[i][j]=0;else dp[i][j]=dp[i-1][j]+dp[i][j-1];}}printf("%d",dp[n][m]);
}

[蓝桥杯 2022 省 B] 积木画

小明最近迷上了积木画,有这么两种类型的积木,分别为 I I I 型(大小为 2 2 2 个单位面积) 和 L L L 型 (大小为 3 3 3 个单位面积):

I 型积木

同时,小明有一块面积大小为 2 × N 2 \times N 2×N 的画布,画布由 2 × N 2 \times N 2×N 1 × 1 1 \times 1 1×1 区域构成。小明需要用以上两种积木将画布拼满,他想知道总共有多少种不同的方式? 积木可以任意旋转,且画布的方向固定。

输入格式

输入一个整数 N N N,表示画布大小。

输出格式

输出一个整数表示答案。由于答案可能很大,所以输出其对 1000000007 1000000007 1000000007(即 1 0 9 + 7 10^9+7 109+7)取模后的值。

样例输入 #1

3

样例输出 #1

5

提示

【样例说明】

五种情况如下图所示, 颜色只是为了标识不同的积木:

【评测用例规模与约定】

对于所有测试用例, 1 ≤ N ≤ 1 0 7 1 \leq N \leq 10^7 1N107

蓝桥杯 2022 省赛 B 组 G 题。

思路

  • 我想的是:状态—— d p [ i ] [ j ] dp[i][j] dp[i][j]表示到(i,j)的方案数,状态转移——由横向纵向 I I I ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) (dp[i-1][j],dp[i][j-1]) dp[i1][j],dp[i][j1] L L L型积木( d p [ i − 1 ] [ j − 1 ] dp[i-1][j-1] dp[i1][j1]L型的底角在右下方 d p [ i − 1 ] [ j − 2 ] , d p [ i + 1 ] [ j − 1 ] dp[i-1][j-2],dp[i+1][j-1] dp[i1][j2]dp[i+1][j1], )我的方法还是行不通,因为第一行无法解决
  • 看了别人的思路:思路

题解

#include<bits/stdc++.h>
using namespace std;
long long dp[10000010]={0},n,mod=1e9+7;
int main()
{scanf("%lld",&n);dp[0]=1,dp[1]=1,dp[2]=2;for(register int i=3;i<=n;i++) dp[i]=dp[i-1]*2+dp[i-3],dp[i]%=mod;printf("%lld",dp[n]);return 0;
}

[蓝桥杯 2017 国 B] 对局匹配

小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分,代表他的围棋水平。

小明发现网站的自动对局系统在匹配对手时,只会将积分差恰好是 K K K 的两名用户匹配在一起。如果两人分差小于或大于 K K K,系统都不会将他们匹配。

现在小明知道这个网站总共有 N N N 名用户,以及他们的积分分别是 A 1 , A 2 , ⋯ A N A_1,A_2, \cdots A_N A1,A2,AN

小明想了解最多可能有多少名用户同时在线寻找对手,但是系统却一场对局都匹配不起来(任意两名用户积分差不等于 K K K)?

输入格式

第一行包含两个个整数 N N N K K K

第二行包含 N N N 个整数 A 1 , A 2 , ⋯ , A N A_1,A_2, \cdots, A_N A1,A2,,AN

输出格式

一个整数,代表答案。

样例输入 #1

10 0
1 4 2 8 5 7 1 4 2 8

样例输出 #1

6

样例输入 #2

10 1
2 1 1 1 1 4 4 3 4 4

样例输出 #2

8

提示

对于 30 % 30\% 30% 的数据, 1 ≤ N ≤ 10 1 \le N \le 10 1N10

对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 1 0 5 1 \le N\le 10^5 1N105 0 ≤ K , A i ≤ 1 0 5 0\le K,A_i \le 10^5 0K,Ai105

时限 1 秒, 256M。蓝桥杯 2017 年第八届国赛

思路

  • 我的思路:首先对 A 1 , A 2 , ⋯ , A N A_1,A_2, \cdots, A_N A1,A2,,AN排序。状态—— f [ i ] : i f[i]:i f[i]i这个位置有多少个可以匹配不到的,状态转移—— f [ j ] f[j] f[j]会因为之前遍历过的积分而产生改变,结果用 a n s ans ans在遍历的时候就不断更新

题解

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef long long ll;
int n, k, mx, mn = N, x;
ll dp[N][2], ans, c[N];
int main(){cin>>n>>k;for(int i = 1;i <= n;i ++) cin>>x, c[x] ++, mx = max(x, mx), mn = min(x, mn);if(k == 0) {for(int i = mn;i <= mx;i ++) ans += bool(c[i]);cout << ans << endl;}for(int i = mn;i <= min(mn+k-1, mx);i ++) dp[i][0] = 0LL, dp[i][1] = c[i]; for(int i = min(mn+k-1, mx) + 1;i <= mx;i ++) {dp[i][0] = max(dp[i-k][0], dp[i-k][1]); if(c[i]) dp[i][1] = dp[i-k][0] + c[i]; else dp[i][1] = max(dp[i-k][0], dp[i-k][1]); } for(int i = max(mx-k+1, mn);i <= mx;i ++) ans += max(dp[i][0], dp[i][1]); cout << ans << endl;
}

总结

来自chatgpt,对我有启发

  1. 确定问题的状态:首先要明确问题的状态是什么,状态是描述问题不同阶段的情况,状态转移是从一个状态到另一个状态的过程。状态可以用一个或多个变量来表示,通常用数组或矩阵来存储状态
  2. 定义状态转移方程:状态转移方程是描述问题状态之间的转移规则,通常用递推公式来表示。在设计状态转移方程时,需要考虑当前状态如何转移得到下一个状态,这个过程通常需要根据问题的具体情况进行分析。有时候根据题目意思仍不能确定状态转移方程时,可以先写出前几个状态,然后根据数学规律推导出状态转移方程([蓝桥杯 2022 省 B] 积木画)
  3. 确定边界条件和初始状态:边界条件是指问题状态的一些特殊情况,需要特殊处理。初始状态是指问题的最小规模,通常需要设置一个初始状态来进行递推计算。
  4. 确定最终状态和答案:最终状态是指问题的最终阶段,答案是根据最终状态得到的问题的解。
  5. 编写代码实现:根据上述步骤,实现动态规划算法的代码。
  6. 在设计动态规划算法时,还需要注意以下几点:
    1. 尽量将问题划分成多个子问题,对每个子问题进行独立求解。
    2. 尽量将重复计算的部分存储起来,避免重复计算。
    3. 在实现时,可以使用滚动数组等技巧来优化空间复杂度。
    4. 在实现时,需要注意边界条件和数组下标的范围。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/14645.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基础数论算法刷题笔记

理论 最小公倍数、最大公约数 (ab)%n (a%nb%n)%n (ab)%n (a%nb%n)%n a≡2(mod n) —— a%n2 lcm——最小公倍数 gcd——最大公约数 lcm(a,b) a*b / gcd(a,b) 最小公倍数两数的乘积除以最大公约数 但是写程序时应该是 a /gcd(a,b) *b 因为a*b可能会超出数据范围 例子&…

LLM - 搭建 DrugGPT 结合药物化学分子知识的 ChatGPT 系统

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://blog.csdn.net/caroline_wendy/article/details/131384199 论文&#xff1a;DrugChat: Towards Enabling ChatGPT-Like Capabilities on Drug Molecule Graphs DrugChat&#xff0c;基…

两句话就搞死chatgpt

事情是这样的&#xff0c;我在看一本书--思维风暴&#xff0c;看到一篇发散思维的内容&#xff0c;就想考考chatgpt,结果第一句话发过去&#xff0c;chatGPT就直接报错&#xff0c;刷新了下页面&#xff0c;接着继续问&#xff0c;等了不多见&#xff0c;chatgpt慢慢吐字&#…

人人都是ChatGPT prompt 工程师

关于 Prompt ​ 解释这个词之前&#xff0c;首先需要解释 prompt 这个词&#xff1a; 简单的理解它是给 AI 模型的指令。 它可以是一个问题、一段文字描述&#xff0c;甚至可以是带有一堆参数的文字描述。AI 模型会基于 prompt 所提供的信息&#xff0c;生成对应的文本&…

ChatGPT总结的“商汤日日新大模型”,亮点在文末!!!

关注并星标 从此不迷路 计算机视觉研究院 公众号ID&#xff5c;ComputerVisionGzq 学习群&#xff5c;扫码在主页获取加入方式 计算机视觉研究院专栏 作者&#xff1a;Edison_G “我们正处于临界点。”在商汤科技董事长兼首席执行官徐立说出这句话后一个月&#xff0c;商汤科技…

装X型学习动机体系:我对成就目标定向理论(装逼)的研究,怎么让自己充满动力,这个我期待太久了

装X型学习动机体系&#xff1a;我对成就目标定向理论&#xff08;装逼&#xff09;的研究&#xff0c;怎么让自己充满动力&#xff0c;这个我期待太久了 本质篇&#xff1a;生命的本质是&#xff0c;渴望被看见动力篇&#xff1a;积极响应挑战&#xff0c;自恋克服惰性费曼学习…

40岁,刚被裁,想说点啥。

因公众号更改推送规则&#xff0c;请点“在看”并加“星标”第一时间获取精彩技术分享 点击关注#互联网架构师公众号&#xff0c;领取架构师全套资料 都在这里 0、2T架构师学习资料干货分 上一篇&#xff1a;ChatGPT研究框架&#xff08;80页PPT&#xff0c;附下载&#xff09;…

Go是一门面向对象编程语言吗

Go语言已经开源13年了[1]&#xff0c;在近期TIOBE[2]发布的2023年3月份的编程语言排行榜中&#xff0c;Go再次冲入前十&#xff0c;相较于Go在2022年底的排名[3]提升了2个位次&#xff1a; 《Go语言第一课》专栏[4]中关于Go在这两年开始飞起的“预言”也正在逐步成为现实^_^&am…

如何写出高质量的文章:从战略到战术

作者&#xff1a;明明如月学长&#xff0c; CSDN 博客专家&#xff0c;蚂蚁集团高级 Java 工程师&#xff0c;《性能优化方法论》作者、《解锁大厂思维&#xff1a;剖析《阿里巴巴Java开发手册》》、《再学经典&#xff1a;《EffectiveJava》独家解析》专栏作者。 热门文章推荐…

原力计划来了【协作共赢 成就未来】

catalogue &#x1f31f; 写在前面&#x1f31f; 新星计划持续上新&#x1f31f; 原力计划方向&#x1f31f; 原力计划拥抱优质&#x1f31f; AIGC&#x1f31f; 参加新星计划还是原力计划&#x1f31f; 创作成就未来&#x1f31f; 写在最后 &#x1f31f; 写在前面 哈喽&…

博弈论——选举/投票(voting)

文章目录 前言一、相对多数投票法&#xff08;Plurality Voting&#xff09;二、孔多塞准则&#xff08;The Condorcet Criterion&#xff09;三&#xff0c; 谷轮法&#xff08;Copeland method四&#xff0c;波达计数法&#xff08;Borda Count&#xff09;五&#xff0c;选举…

Java 设计模式(java design patterns)

什么是设计模式&#xff1f; 前辈们&#xff0c;在长期开发中为了解决某种重复出现的问题&#xff0c;经过长期的总结&#xff0c;代码结构优化&#xff0c;最终确定一套解决办法。 为什么学习设计模式&#xff1f; 对程序设是有帮助的&#xff0c;提高代码额可重用性&#…

叫ChatGPT用html+css+js写一个圣诞节代码,看看什么样子?

最近ChatGPT这么火&#xff0c;那就让他给我写点代码吧。 如何注册一个账号&#xff0c;参考&#xff1a;注册ChatGPT详细指南 注册不了的小伙伴们&#xff0c;咱们评论区见&#xff0c;问一个最想问的问题&#xff0c;看到就给你回复&#xff01; 我已经注册好了&#xff0c;…

前端实现六一儿童节祝福语分享,烟花特效助您表心意

部分数据来源&#xff1a;ChatGPT <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><title>六一儿童节祝福</title><style>body {background-image: url(https://picsum.photos/1920/1080);backgr…

chatgpt赋能python:10个好玩的Python代码-让编程更有趣!

10个好玩的Python代码- 让编程更有趣&#xff01; 作为一名有10年Python编程经验的工程师&#xff0c;我深刻理解到编程可以是一件令人兴奋和有趣的事情。Python是流行且多才多艺的编程语言&#xff0c;具有简洁易懂的语法和丰富的库&#xff0c;可以帮助开发人员快速轻松地实…

大型语言模型与文本摘要

大型语言模型与文本摘要 基于大型语言模型的抽取式摘要基于大型语言模型的零样本跨语言摘要基于大型语言模型的问答式摘要通过摘要任务评估大型语言模型的事实一致性基于大型语言模型的摘要事实一致性评估器未来方向大型语言模型的自我偏好基于大型语言模型生成提示基于大型语言…

ChatGPT玩起来真是上头,AI广泛应用元年体验AI之美

概述 ChatGPT是由人工智能研究实验室OpenAI在2022年11月30日发布的全新聊天机器人模型&#xff0c;一款人工智能技术驱动的自然语言处理工具。它能够通过学习和理解人类的语言来进行对话&#xff0c;还能根据聊天的上下文进行互动&#xff0c;真正像人类一样来聊天交流&#xf…

推荐一款idea神级代码插件【Bito-ChatGPT】而且免费!- 第9篇

历史文章&#xff08;文章累计460&#xff09; 《国内最全的Spring Boot系列之一》 《国内最全的Spring Boot系列之二》 《国内最全的Spring Boot系列之三》 《国内最全的Spring Boot系列之四》 《国内最全的Spring Boot系列之五》 《国内最全的Spring Boot系列之六》 文…

ChatGPT - 获取简短的书籍摘要的Prompt

文章目录 Prompt例子 Prompt “总结[书籍名称]&#xff0c;并给我列出最重要的学习和观点。”例子

小米AX6000开启SSH后的高级用法

买的是RA72版本的AX6000,售价599,高通的CPU。 看看高颜值和唬人的外观,图示如下: 关于AX6000开启SSH的方法有很多介绍的,这里关键讲几点: 先升级RA72对应的固件,降级到41版本。 附上:miwifi_ra72_firmware_59812_1.0.41.bin 版本固件地址: http://cdn.cnbj1.fds.a…