网站SEO优化托管,谷歌搜索入口手机版,wordpress带视频,企点客户端线性DP代码分析1 定义初始状态2 利用循环和状态转移方程#xff0c;填充状态细节剖析#xff1a;1 问题求什么#xff0c;状态就尽量定义成什么#xff0c;有了状态#xff0c;再去尽力套状态转移方程2 动态规划的时间复杂度等于#xff1a;状态数 X 状态转移 的消耗3 状…线性DP代码分析1 定义初始状态2 利用循环和状态转移方程填充状态细节剖析1 问题求什么状态就尽量定义成什么有了状态再去尽力套状态转移方程2 动态规划的时间复杂度等于状态数 X 状态转移 的消耗3 状态转移方程中的i变量导致数组下标越界从而确定那些状态是初始状态4 状态转移的过程一定是单向的把每个状态理解成一个节点状态转移理解成边动态规划的求解就是在一个有向无环图上进行递推计算。5 因为动态规划的状态图是一个有向无环图所以一般会和拓扑排序联系起来代码练习 1 对应蓝桥云课 接龙序列 代码见下
#include iostream
#include string
using namespace std;int dp[10];int main()
{int n;int m 0;cin n;for(int i0; in; i){string A;cin A;int l A[0] - 0;int r A[A.size()-1] - 0;dp[r] max(dp[l] 1, dp[r]);m max(m, dp[r]);}cout n - m endl;// 请在此输入您的代码return 0;
}代码练习 2 对应蓝桥云课 数组切分 代码见下
#include iostream
using namespace std;#define maxn 10001
#define mod 1000000007
int dp[maxn];
int a[maxn];int main()
{int n;cin n;for(int i1; in; i){cin a[i];}dp[0] 1;for(int i1; in; i){int nmax 0;int nmin 10000000;for(int j i; j1; --j){nmax max(nmax, a[j]);nmin min(nmin, a[j]);if(nmax - nmin i-j){dp[i] dp[j-1];if(dp[i] mod){dp[i] - mod;}}}}cout dp[n] endl;// 请在此输入您的代码return 0;
}对应蓝桥云课最大魅力值代码见下
#include iostream
using namespace std;#define maxn 101
#define inf -10000000
int dp[maxn][maxn];
int a[maxn];int main()
{int n;cin n;for(int i1; in; i){cin a[i];}for(int i0; in; i){for(int j0; jn; j){dp[i][j] inf;}}dp[0][0] 0;dp[1][0] 0;dp[1][1] a[1];for(int i2; in; i){dp[i][0] 0;for(int j1; j n; j){dp[i][j] max(a[i] dp[i-2][j-1], dp[i-1][j]);}}cout dp[n][n/2] endl;// 请在此输入您的代码return 0;
}
