房地产的设计网站建设,网站建设后台管理实训报告,建设合同网上备案上哪个网站,网络前端工程师题目描述
数字三角形
输入输出样例
输入样例#1#xff1a;
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5输出样例#1#xff1a;
30思路#xff1a;
这题可能看到的第一眼——直接贪心然后一层一层判断呀#xff01;#xff01;#xff01;不过很快又会发现#xff0c;额___好…题目描述
数字三角形
输入输出样例
输入样例#1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出样例#1
30思路
这题可能看到的第一眼——直接贪心然后一层一层判断呀不过很快又会发现额___好像不行。因为可能当前选的是一个大的但是后面全都是小的 所以这时我们就需要用到动态规划了 动态规划基础知识详见 动态规划基础超详细
这题我们从上到下行不通那我们就要思考从下到上进行操作
首先需要知道状态转移方程 从图中可知当前这这个可以由左下角的数与右下角的数的最大值加上自己本来的数 所以状态转移方程为
dp[i][j]max(dp[i1][j],dp[i1][j1])a[i][j];然后我们需要知道DP的初值那这题很明显就是输入的最后一行也就是
for(int i1;in;i) dp[n][i]a[n][i];AC代码
最后呈上完整代码
#includebits/stdc.h
using namespace std;
int n,a[101][101],dp[101][101];
int main(){cinn;for(int i1;in;i)for(int j1;ji;j) cina[i][j];for(int i1;in;i) dp[n][i]a[n][i];for(int in-1;i1;i--){for(int j1;ji;j){dp[i][j]max(dp[i1][j],dp[i1][j1])a[i][j];}}coutdp[1][1];return 0;
}
