电子产品网站建设,硬件开发软件有哪些,苏州互联网企业,申请网站空间有哪几种方式DP#xff08;动态规划#xff09;全称Dynamic Programming#xff0c;是运筹学的一个分支#xff0c;是一种将复杂问题分解成很多重叠的子问题、并通过子问题的解得到整个问题的解的算法。
在动态规划中有一些概念#xff1a; n1e3 [][] #xff0c;n100 [][][…DP动态规划全称Dynamic Programming是运筹学的一个分支是一种将复杂问题分解成很多重叠的子问题、并通过子问题的解得到整个问题的解的算法。
在动态规划中有一些概念 n1e3 [][] n100 [][][] 状态就是形如dp[i][j val的取值其中ij为下标也是用于描述、确定状态所需的变量val为状态值。 状态转移状态与状态之间的转移关系一般可以表示为一个数学表达式转移方向决定了迭代或递归方向。 最终状态也就是题目所求的状态最后的答案
1.确定状态一般为“到第i个为止xx为jxx为k的方案数/最小代价/最大价值”可以根据数据范围和复杂度来推理。 2.确定状态转移方程即从已知状态得到新状态的方法并确保按照这个方向一定可以正确地得到最终状态。 根据状态转移的方向来决定使用选代法还是递归法记忆化。 3.确定最终状态并输出。
数字三角形
蓝桥杯数字三角形 思路可以用 dp也可以用动态规划计算最大和再判断向下和向右操作不大于 1。
动态规划 O(n^3)
#includebits/stdc.h
using namespace std;
const int N 1e2 5;
int n,a[N][N],dp[N][N][N];int main(){memset(dp,-0x3f,sizeof(dp));cinn;for(int i1;in;i)for(int j1;ji;j)cina[i][j];dp[1][1][0] a[1][1];for(int i2;in;i)for(int j1;ji;j){for(int k0;kn-1;k){if(!k)dp[i][j][k] dp[i-1][j-1][k] a[i][j];else dp[i][j][k] max(dp[i-1][j-1][k],dp[i-1][j][k-1]) a[i][j];}}int ans0;if((n-1)1) for(int j1;jn;j) ans max(ans,max(dp[n][j][(n-1)/21],dp[n][j][(n-1)/2]));else for(int j1;jn;j) ans max(ans,dp[n][j][(n-1)/2]);coutans\n;return 0;
}思路由于最后的位置是有规律的所以直接用[][]就行。
#includebits/stdc.h
using namespace std;
const int N 1e2 5;
int n,a[N][N],dp[N][N];int main(){cinn;for(int i1;in;i)for(int j1;ji;j)cina[i][j];dp[1][1] a[1][1];for(int i2;in;i)for(int j1;ji;j)dp[i][j] max(dp[i-1][j-1],dp[i-1][j]) a[i][j];if((n-1)1)coutmax(dp[n][(n-1)/21],dp[n][(n-1)/211]);else coutdp[n][(n-1)/21];return 0;
}思路用 DFS,代码结果不对不知道为什么
#includebits/stdc.h
using namespace std;
const int N 1e210;
int a[N][N],res[N][N],n;int dfs(int i,int j){if(res[i][j])return res[i][j];if(in){if(n%20(j(n-1)/21||j(n-1)/211))return a[i][j];if(n%21j(n-1)/21)return a[i][j];return -10000000;}return res[i][j] max(dfs(i1,j),dfs(i1,j1))a[i][j];
}int main( ){cinn;for(int i1;in;i)for(int j1;ji;j)cinres[i][j];coutdfs(1,1)\n;return 0;
}
