挑战30天C艹基本入门（DAY5--动态规划）

#今天���动态规划可是c语言里面的重中之重，也是我们学习的路上迈不开的一个问题。

当时高中的时候就学的不明不白地，今天复习一波，才感觉终于守得云开见月明，豁然开朗了，因此写下本篇，同时分享一下我自己的理解，希望帮助到更多迷惑中的人。

动态规划，可以帮我们解决好多实际问题。

动态规划的意思和他字面意思差不多：在一个动态的过程中，不断更新我们的最优解，得到全局的最优解。听上去和贪心差不多，（可以参考我上一篇文章）但是贪心主要是局部最优解，而非一个动态的过程。因此许多能用贪心解决的问题，我们也可以用动态规划来解决。

可见动态规划的适用性广泛以及重要性强。

那我们接下来就进入动态规划的学习中来。

动态规划

我们动态规划一般分为以下几步：

1.我们要清楚状态的描述和定义：我们一般用dp[i][j]来定义状态，从1，1到i，j经过的得到的最大值。

2.状态转移方程（这一步是动态规划的核心）：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];

3.确定边界：如果从上往下来的话，那么我们的dp[i][j]=a[1][1],即确定了上边界。

基本就分为以下三步，我们熟练掌握，最重要的就是我们的状态转移方程，那么接下来我们来看一道动态规划的题目：

数字金字塔，要求遍历得到最大值。

我们按照我们前面的三个思路：

第一步我们首先定义二维数组a和dp。先将题目中的表导入a中。

第二步就是我们的状态转移方程：我们可以知道，下面最大值得去上面两个分支的最大值，再加上下一行的数值。因而我们得到状态转移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j];

第三步我们确定边界：dp[i][j]=a[1][1],即确定了上边界。

我们需要知道我们最后得到的dp[i][j]，只是最终的一个值，因此我们要与最大值做对比，在每一步循环中对比，然后取最大值。

那么我们就可以得到我们下面的代码：

#includeusing namespace std;int a[1001][1001],dp[1001][1001];int main(){int n;int maxx=0;cin>>n;for(int i=1;ia[i][j];}}dp[1][1]=a[1][1];for(int i=2;i