邢台做wap网站的公司,app推广多少钱一单,广东网站设计网站,h5 网站开发流程目录 介绍#xff1a;
题目一: 题目二#xff1a; 题目三#xff1a; 题目四#xff1a; 题目五#xff1a; 题目六#xff1a; 题目七#xff1a; 题目八#xff1a;
题目九#xff1a; 介绍#xff1a; 动态规划是一种算法设计技术#xff0c;用于解决具有重叠…目录 介绍
题目一: 题目二 题目三 题目四 题目五 题目六 题目七 题目八
题目九 介绍 动态规划是一种算法设计技术用于解决具有重叠子问题和最优子结构特征的问题。它通过将大问题拆分成小问题并保存每个小问题的解以避免重复计算从而提高算法的效率。 在动态规划中问题可以通过子问题的最优解来构建整体问题的最优解。动态规划的核心思想是利用已解决的子问题的解来构建更大规模问题的解以此递推得到最优解。 动态规划通常包含以下三个步骤 1. 定义问题的状态将问题划分为若干个子问题并确定状态变量表示子问题的解。 2. 定义状态转移方程通过递推关系式将大问题的解表示为小问题的解。 3. 定义边界条件确定问题的初始状态即最小规模的子问题的解。通常是一些边界情况。 动态规划适用于那些具有重叠子问题和最优子结构特征的问题例如最长公共子序列、背包问题、最短路径等。通过利用动态规划我们可以将问题的时间复杂度从指数级别降低到多项式级别从而提高算法的效率。 题目一: #includeiostream
#includecstring
using namespace std;
int main()
{long long a[110][110];//第i行第j个可取的最大值int n;long long ans 0;cin n;memset(a, 0, sizeof(a));for (int i 1; i n; i){for (int j 1; j i; j){cin a[i][j];a[i][j] max(a[i - 1][j], a[i - 1][j - 1]);//正上方的和斜上角的取大的加ans max(ans, a[i][j]);}}cout ans;
} 题目二 #includeiostream
#includecstring
using namespace std;
int n;
int a[100100];
int f[100100];//以第j个结尾的最大子段和
int ans 0;
int main()
{cin n;for (int i 1; i n; i){cin a[i];}f[1] a[1];//第一个就为第一个的值for (int i 2; i n; i){f[i] max(f[i - 1] a[i], a[i]);//比较i-1子段和加上当前的数是否大于当前数ans max(ans, f[i]);}cout ans endl;} 题目三 #includeiostream
#includecstring
using namespace std;
int n;
int a[300][300];//i站到j站的租金
int f[300];//到j站的最少的租金
int main()
{cin n;for (int i 1; i n; i){for (int j i 1; j n; j){cin a[i][j];}}for (int i 1; i n; i){for (int j i 1; j n; j){if(i1)f[j]a[i][j];//每站初始为1直接到各个站elsef[j] min(f[j], f[i] a[i][j]);//选i为中转站不选继承选了则f[i]a[i][j]}}cout f[n] endl;
} 题目四 #includeiostream//求翻转字符串和原字符串的公共子序列
#includealgorithm
#includecstring
using namespace std;
string str, str1;
int dp[1001][1001];//表示到str字符串的第i个与str1字符串的第j个有的最长公共子序列
int main()
{memset(dp, 0, sizeof(dp));cin str;int len str.length();str1 str;reverse(str.begin(), str.end());//翻转for (int i 1; i len; i){for (int j 1; j len; j)if (str[i - 1] str1[j - 1])dp[i][j] max(dp[i][j], dp[i - 1][j - 1] 1);elsedp[i][j] max(dp[i - 1][j], dp[i][j - 1]);}printf(%d\n, len - dp[len][len]);
}题目五 #includeiostream
#includecstring
using namespace std;
struct node
{int w, step;
};
node dp[110][110];
int n, m, a[110][110];
int main()
{memset(dp, 0, sizeof(dp));cin n m;for (int i 1; i n; i)for (int j 1; j m; j){cin a[i][j];}for (int j 1; j m; j)//第一行{dp[1][j].w dp[1][j - 1].w a[1][j];dp[1][j].step 1;}for (int i 1; i n; i)//第一列{dp[i][1].w dp[i - 1][1].w a[i][1];dp[i][1].step 1;}for (int i 2; i n; i)for (int j 2; j m; j){if (dp[i - 1][j].w dp[i][j - 1].w)//上左{dp[i][j].w dp[i - 1][j].w a[i][j];dp[i][j].step dp[i - 1][j].step;}else if (dp[i - 1][j].w dp[i][j - 1].w)//上左{dp[i][j].w dp[i][j - 1].w a[i][j];dp[i][j].step dp[i][j - 1].step;}else//相等时{dp[i][j].w dp[i - 1][j].w a[i][j];dp[i][j].step dp[i][j - 1].step dp[i - 1][j].step;//两个步数相加}}cout dp[n][m].w dp[n][m].step endl;
} 题目六 #includeiostream
#includecstring
using namespace std;
int a[1010100], b[1010100],dp[1010100];
int n,tmp;
void prin(int k)
{if(kn-3)//大于n-3 即可以直接跳到终点{ coutkendl;return ;}elsecoutk ;prin(b[k]);
}
int main()
{memset(a, 0, sizeof(a));cin n;for (int i 0; i n; i){cin a[i];}for (int i n - 3; i 0; i--)//从后往前走{tmp a[i 1];//从后一格来b[i] i 1;if (tmp a[i 2])//后两格{b[i] i 2;tmp a[i 2];}if (tmp a[i 3])//后三格{b[i] i 3;tmp a[i 3];}a[i] tmp ;}cout a[0] endl;prin(0);
} 题目七 #includeiostream//最长公共子序列
#includecstring
using namespace std;
int dp[2010][2010];
int main()
{string s1, s2;cin s1 s2;memset(dp, 0, sizeof(dp));int len1 s1.size(), len2 s2.size();for (int j 1; j len2; j) dp[0][j] dp[0][j - 1] 1;for (int i 1; i len1; i) dp[i][0] dp[i - 1][0] 1;for (int i 1; i len1; i){for (int j 1; j len2; j){if (s1[i - 1] s2[j - 1])//两个字符相同不做操作dp[i][j] dp[i - 1][j - 1];else//不相同选择三种操作中操作数最小的dp[i][j] min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1;}//dp[i-1][j-1]表示替换dp[i-1][j]表示删除a[i]字符dp[i][j-1]表示在a[i]后插入}cout dp[len1][len2] endl;
} 题目八 #includeiostream
#includecstring
using namespace std;
int n;
int a[100100];
int f[100100];//以j结尾的最大递增序列
int ans 0;
int main()
{cin n;for (int i 1; i n; i){cin a[i];f[i] 1;//以i结尾的数的最大递增序列起始都是包含自己的一个}for (int i 1; i n; i){for (int j 1; j i; j)//从a[1]到a[i]的循环{if (a[i] a[j] f[j]1 f[i])//第i个大于第j个且 以j结尾的最大递增序列加上一个即a[i]这个数大于 原先以i结尾的最大递增子序列{f[i] f[j] 1;ans max(ans, f[i]);}}}cout ans endl;
}
题目九 #includeiostream//看成背包问题
using namespace std;
int v[21];
int dp[1000001];//表示装j有几种方法
int mod 1e9;
int main()
{int i, j, n, k;v[0]1;for (i 1; i 20; i)//初始化体积v[i]2*v[i-1];for (j 0; j 1000000; j) //每个j都至少有一种方法全为1dp[j] 1;for (i 1; i 20; i)//从第一件物品开始装每件物品有无限个for (j v[i]; j 1000000; j)dp[j] (dp[j] dp[j - v[i]]) % mod;cinn;while (n--){cin k;cout dp[k];if (n ! 0)cout ;}}
