珍惜眼前的幸福，而不是去奢求无法得到的东西。
算法描述
“动态规划（Dynamic Programming, DP）在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间 · · · · · · 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。”
通俗一点来讲，动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。
经典一维动态规划
leetcode.70.爬楼梯：给定 n 节台阶，每次可以走一步或走两步，求一共有多少种方式可以走完这些台阶。
1
2
3
4
5
6
7
8
int climbStairs(int n) {
if (n <= 2) return n;
vector<int> dp(n + 1, 1);
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
HOUSE ROBBER
假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。
定义一个数组 dp，dp[i] 表示抢劫到第 i 个房子时，可以抢劫的最大数量。我们考虑 dp[i]，此时可以抢劫的最大数量有两种可能，一种是我们选择不抢劫这个房子，此时累计的金额即为dp[i-1]；另一种是我们选择抢劫这个房子，那么此前累计的最大金额只能是 dp[i-2]，因为我们不能够抢劫第 i-1 个房子，否则会触发警报机关。因此本题的状态转移方程为 dp[i] = max(dp[i-1],nums[i-1] + dp[i-2])。
1
2
3
4
5
6
7
8
9
10
int rob(vector<int>& nums) {
if (nums.empty()) return 0;
int n = nums.size();
vector<int> dp(n + 1, 0);
dp[1] = nums[0];
for (int i = 2; i <= n; ++i) {
dp[i] = max(dp[i-1], nums[i-1] + dp[i-2]);
}
return dp[n];
}
总结
动归很难，慢慢练。
