动态规划入门

算法简述

动态规划(dynamic programming, 简称dp)是一种应用十分广泛的算法。它可以理解成是对枚举法的一种优化。通常在求解一个复杂的最优解问题时，我们会把它拆分成很多子问题，然后各个击破，最后汇总起来得到最终答案。如果我们采用枚举法列举所有情况，你会发现会有很多重复的子问题。而dp的核心思想就是：将很多子问题的结果储存起来，以空间换取时间的方式，尽可能地避免重复的计算量。
有人做过一个这样的比喻：你追一个MM的时候，需要对该MM身边的各闺中密友都好，这样你追MM这个问题就分解为对其MM朋友的问题，只有把这些问题都解决了，最终你才能追到MM。
动态规划的两个最重要的要素就是：

1. 状态的定义
2. 状态的转移

题目链接

hdu-2084 数塔
题意：

---

给定类似下图的一个数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？

解法：

首先，从上到下的模型我们可以倒过来。这样，问题就变成了：求从底层走到顶层的数字之和的最大值了。记第i层第j个点的数值为a[i][j]

1. 状态定义：
   dp[i][j]表示从底层走到(i, j)点所能达到最大的数字之和；
2. 状态转移：
   第i层第j个点可由第i+1层j或j+1的点走过来，所以dp[i][j]=max(dp[i+1][j], dp[i+1][j+1]) + a[i][j] for i in range(n-1)
3. 初始条件：
   dp[n-1][j]=a[n-1][j] for j in range(n)

核心代码：

System.arraycopy(a[n - 1], 0, dp[n - 1], 0, n);
for (int i = n - 2; i >= 0; --i) {
    for (int j = 0; j <= i; ++j) {
        dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + a[i][j];
    }
}

完整代码