前言

本文主要是记录作为算法的初学者在学习算法过程中的笔记，目前考虑按照题目类型分类进行思路总结和相关的题目代码实现。

1 - 动态规划问题（DP 问题，Dynamic Programming）

1 - 问题概述

动态规划（英語：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。

2 - 问题关键点

1. 动态规划问题一般形式就是求最值（比如求最长递增子序列）。
2. 动态规划的核心问题是穷举（分析问题初步要用穷举的思想，将问题原规模减小，然后穷举，寻找规律）。计算机可以暴力穷举（递归），也可以利用“备忘录”（存储递归过程中已经形成的一些状态值，从而给递归树剪枝，减小时间复杂度）或DP Table（常用这种办法，本质上就是利用一个数组存储穷举的各种状态的对应值形成的表，此时是自底向下的迭代思想，设置边界条件初值 dp【0 或 1】，然后代入状态转移方程，从而迭代求出 dp【i】）。
3. 动态规划三要素：重叠子问题、最优子结构、状态转移方程

• 重叠子问题：如果暴力穷举（递归）的话，就会出现重叠子问题。（画递归树，只要存在重复节点，就说明存在重叠子问题）
  
• 最优子结构：「最优子结构」是某些问题的一种特定性质，并不是动态规划问题专有的。也就是说，很多问题其实都具有最优子结构，只是其中大部分不具有重叠子问题，所以我们不把它们归为动态规划系列问题而已。我先举个很容易理解的例子：假设你们学校有 10 个班，你已经计算出了每个班的最高考试成绩。那么现在我要求你计算全校最高的成绩，你会不会算？当然会，而且你不用重新遍历全校学生的分数进行比较，而是只要在这 10 个最高成绩中取最大的就是全校的最高成绩。我给你提出的这个问题就符合最优子结构：可以从子问题的最优结果推出更大规模问题的最优结果。让你算每个班的最优成绩就是子问题，你知道所有子问题的答案后，就可以借此推出全校学生的最优成绩这个规模更大的问题的答案。
• 状态转移方程：一个状态 = 该状态之前的状态进行运算 就是状态转移方程。

4. DP Table：边界条件 + 状态转移方程 自底向上迭代求出所有结果。

3 - 题目练习

1 - 爬楼梯（Leetcode 70 题 简单）

1 - 题目描述

https://leetcode.cn/problems/climbing-stairs/
其实就是一个斐波那契数列问题的变体。

2 - 解题思路

1. 将大规模问题拆解为小规模问题先行思考，比如这题先假设从 0 楼爬到 3 楼（一共要爬 4 层楼）的情况，那么可以推出爬到 4 楼的方法种数 = 爬到 3 楼的方法种数 ＋ 爬到 2 楼的方法种数 = 5 种。
2. 不难推出该 dp 问题的状态转移方程：dp【i】 = dp【i-1] + dp【i-2】。
3. 设置边界条件 dp【0】 = dp【1】 = 1，利用状态转移方程自底向上迭代求出所有情况。

3 - 代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

//DP Table迭代法
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n+1);
		for(int i = 0;i <= n;i++){
			dp[i] = 0;
		}
		dp[0] = 1; //边界条件，爬0层楼就一种方法
		dp[1] = 1; //爬一层楼也就一种方法
		for(int i = 2;i <= n;i++){
			dp[i] = dp[i-1] + dp[i-2]; //状态转移方程
		}
		return dp[n];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

//状态压缩，减小空间复杂度，该题不需要用一个大的数组存储所有的状态值
class Solution {
public:
    int climbStairs(int n) {
       int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
};

4 - 总结