👉什么是动态规划👈
动态规划（Dynamic Programming，简称为 DP）是分治思想的延伸，通俗来说就是大事化小，小事化了的艺术。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
动态规划具备了以下三个特点：
把原来的问题分解成了几个相似的子问题
所有的子问题都只需要解决一次
储存子问题的解
动态规划的本质，是对问题状态的定义和状态转移方程的定义（状态以及状态之间的递推关系），动态规划问题一般从以下四个角度来考虑：状态定义、状态间的转移方程定义、状态的初始化和返回结果。
状态定义的要求：定义的状态一定能够形成递推关系。动态规划适用的场景：最大最小值问题、可不可行、是不是以及方案个数等问题。
👉斐波那契数列👈
斐波那契数列不管是递归版本和循环版本的解法，都是非常简单的，但是它仍然是非常经典的一道动态规划的题目。它能够让我们很好去熟悉动态规划状态的定义、状态转移方程的定义、状态的初始化以及返回结果。
状态：F(i) 第 i 项斐波那契数
状态转移方程：F(i) = F(i - 1) + F(i - 2)
初始状态：F(0) = 0，F(1) = 1，F(2) = 1
返回结果：F(n) 第 n 项斐波那契数
以上的分析过程是非常重要的，特别是对一些难题，这也是解决动态规划题目的难点所在。
class Solution { public: int Fibonacci(int n) { // 创建数组，保存中间状态的解 int* F = new int[n + 1]; // 初始化F(0)和F(1) F[0] = 0, F[1] = 1; // 状态转移方程F(i) = F(i-1) + F(i-2) for(int i = 2; i <= n; ++i) { F[i] = F[i - 1] + F[i - 2]; } // 返回结果 int ret = F[n]; delete[] F; return ret; } };
其实我们求解当前第 i 项的斐波那契数，只需要前两项的斐波那契数，所以我们可以对空间复杂度进行进一步的优化。
class Solution { public: int Fibonacci(int n) { int f0 = 0; int f1 = 1; int fn = 1; for(int i = 2; i <= n; ++i) { // f0为F(i-2)，f1为F(i-1) fn = f0 + f1; f0 = f1; f1 = fn; } return fn; } };
👉拆分词句👈
给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列，使得单词序列中所有的单词都是dict中的单词（序列可以包含一个或多个单词）。例如:
给定s=“nowcode”；dict=[“now”, “code”]。返回true，因为"nowcode"可以被分割成"now code"。
如果我们想一下采用暴力的方式去分割字符串的话，很明显是行不通的。这时候，我们可以尝试一下采用动规。动态最难的就是如何定义状态以及状态定义好后，如何确定状态转移方程。完成了这两部，题目也差不多可以解决了。
那状态（子问题）如何确定呢？其实状态一般都是从问题中抽象出来的。本道题的问题是字符串 s 是否可以被分割，那么状态 F(i) 是不是就是字符串 s 的前 i 个字符是否可以被分割。那接下来就确定状态转移方程，见下图。
class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { if(dict.empty()) // 词典为空 { return false; } vector<bool> canBreak(s.size() + 1, false); // 初始状态 canBreak[0] = true; for(int i = 1; i <= s.size(); ++i) { // j < i && F(j) && 第[j + 1, i]字符组成的单词是否在词典里 for(int j = 0; j < i; ++j) { if(canBreak[j] && (dict.find(s.substr(j, i - j)) != dict.end())) { canBreak[i] = true; break; } } } return canBreak[s.size()]; } };
通过拆分词句这道题，我们也可以看出状态方程不一定是一个等式，且需要辅助状态（实际不存在的状态）。
👉三角矩阵👈
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) { return 0; } int row = triangle.size(); int col = triangle[0].size(); for(int i = 1; i < row; ++i) { for(int j = 0; j <= i; ++j) { if(j == 0) { triangle[i][j] += triangle[i - 1][j]; } else if(j == i) { triangle[i][j] += triangle[i - 1][j - 1]; } else { triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]); } } } // 找出从顶部到底部的最小路径和 int ret = triangle[row - 1][0]; for(int j = 1; j < row; ++j) { if(triangle[row - 1][j] < ret) { ret = triangle[row - 1][j]; } } return ret; } };
思路二：从下向上推
class Solution { public: int minimumTotal(vector<vector<int> > &triangle) { if(triangle.empty()) { return 0; } int row = triangle.size(); int col = triangle[0].size(); for(int i = row - 2; i >= 0; --i) { for(int j = 0; j <= i; ++j) { triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]); } } return triangle[0][0]; } };
通过这道题目可以看出，状态定义的不同，状态转移方程也会不同，代码量和简洁程度也会有所不同。
👉总结👈
本篇博客主要讲解了什么是动态规划以及几道动态规划的题目：斐波那契数列、拆分词句和三角矩阵。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
