20211104蓝桥杯培训

能采用动态规划求解的问题的一般要具有 3 个性质：

最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势）

解题步骤：

1.  拆分问题

2.  定义状态 (并找出初状态)

3.  状态转移方程

题目讲解：

C 题数塔问题

有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 

我们知道，从定点开始每次只有两个方向，左下和右下，要想知道如何走才能得到最大值，我们只需要知道它的两个子节点的如何走才能得到最大值，相同的情况我们又可以问它的子节点的子节点，这样重复下去一直都爱最后一行。

故最后的状态转移方程式   dp [i][j] = num [i][j] + max (dp [i+1][j], dp [i+1][j+1]); 注意这是倒推的，就好像我们只有知道了地 i+1 个才能知道第 i 个。仔细想一想为什么递推完成后 dp [1][1] 就是最大值呢？（从循环条件中找答案）

#include

using namespace std;

const int MAXN = 100+10;

int num[MAXN][MAXN];

int dp[MAXN][MAXN];

int main()

{

    int t;

    scanf("%d", &t);

    while( t-- )

    {

        memset(dp, 0, sizeof(dp));

        int n;

        scanf("%d", &n);

        for( int i=1; i<=n; i++ )

        {

            for( int j=1; j<=i; j++ )

                scanf("%d", &num[i][j]);

        }

        for( int j=1; j<=n; j++ )

            dp[n][j] = num[n][j];

        for( int i = n-1; i >= 1; i-- )

        {

             for( int j=1; j <= i; j++ )

             {

                 dp[i][j] = num[i][j] + max(dp[i+1][j], dp[i+1][j+1]);

             }

        }

        printf("%d\n", dp[1][1] );

    }

    return 0;

}