动态规划——简单的动态规划问题
目录
一、什么是动态规划
二、简单的动态规划问题
1、第N个泰波那契数
2、最小花费爬楼梯
3、不同路径
4、下降路径最小和
一、什么是动态规划
动态规划算法（Dynamic Programming，DP）是运筹学的一个分支，用于求解决策过程的最优化问题。它通过将复杂问题分解为多个子问题，并存储子问题的解，以避免重复计算，从而提高效率。
使用动态规划算法解决问题的步骤：
1、确定状态表示
2、推出状态转移方程
3、建立dp表，并初始化
4、确定填表顺序后，编写代码
5、最后根据题意和状态表示，返回结果
二、简单的动态规划问题
1、第N个泰波那契数
第N个泰波那契数
第一步：确定状态表示
根据题意，我们需要求出第n个泰波那契数的值，所以我们可以用 dp[ i ] 来表示第 i 个泰波那契数的值。
第二步：推出状态转移方程
其实题目已经给出了状态转移方程，即第n个泰波那契数的值，为它前面三个泰波那契数值之和。所以状态转移方程如下。
第三步：初始化dp表。因为我们的状态转移方程需要计算，i-3，i-2，i-1，所以 i 需要大于等于3，所以我们需要将dp表前三个位置初始化，dp[0] = 0，dp[1] = 1，dp[2] = 1。
最后的返回值，就是第n个泰波那契数的值，即dp[n]。
解题代码：
class Solution
{
public:int tribonacci(int n) {if(n == 0)return 0;if(n == 1 || n == 2)return 1;vector<int> dp(n+1);dp[0] = 0, dp[1] = 1, dp[2] = 1;for(int i = 3; i <= n; i++)dp[i] = dp[i-3] + dp[i-2] + dp[i-1];return dp[n];}
};
2、最小花费爬楼梯
最小花费爬楼梯
第一步：确定状态表示
根据题意，我们要求的是到达顶部所需的最低花费，所以我们可以将状态表示设为，dp[ i ] 表示到达第i个阶梯时所需要的最小花费。
第二部：推出状态转移方程
根据题意，我们可以一次性向上一步或者两步。所以，对于到达 i 位置来说，我们可以从 i-2 位置向上两步到达 i 位置，也可以从 i-1 位置向上一步到达 i 位置。
这样，我们就可以推出状态转移方程了，如下。
第三步：初始化dp表，因为我们的状态转移方程需要计算，i-2，i-1，所以 i 需要大于等于2。也就是说，dp表下标为0和下标为1的位置需要我们进行初始化。根据题意，我们可以选择从下标为0和1的元素，作为初始台阶，所以 dp[0] = dp[1] = 0。
填表顺序：为了能够知道第 i 个位置的数据，我们需要知道 i 位置之前位置的值，所以应该从左往右填写dp表。
最后的返回值，我们需要返回到达顶层所需费用，所以返回dp[n]。
解题代码：
class Solution
{
public:int minCostClimbingStairs(vector<int>& cost){int n = cost.size();vector<int> dp(n+1);dp[0] = dp[1] = 0;for(int i = 2; i <= n; i++)dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);return dp[n];}
}; 
3、不同路径
不同路径
第一步：确定状态表示
题目是让我们求到达右下角时所有的路径总数，所以dp[ i ][ j ]：表示从原点前进到坐标为（i，j）的位置时， 所有的路径总数。
第二步：推出状态转移方程
根据题意，我们每次可以向下或者向右移动一步，所以可以先知道到（i，j-1）位置有多少路径，向右移动一步就可以到（i，j)，或者，先知道到（i-1，j）位置有多少路径，然后向下移动一步就可以到（i，j)。
第三步：初始化dp表
在使用状态转移方程的时候，我们会用到 j-1 和 i-1 位置的数据，那么对于第0行和第0列来说，就会发生越界访问的问题。为了解决这一问题，我们可以给dp表多增加一行和一列。
然后从 （1，1）位置开始填写。需要注意的是，下标的对应关系，比如（1，1）对应的是原表中（0，0）的位置。
填表顺序：为了能够知道第 （i, j）位置的数据，我们需要知道 （i，j-1）和（i-1，j）位置的值，所以应该从左往右，从上向下填写dp表。
最后的返回值，我们需要返回到达右下角位置的所有路径，所以返回dp[m][n]。
解题代码：
class Solution
{
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1, vector<int>(n+1));dp[0][1] = 1;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){dp[i][j] = dp[i-1][j] + dp[i][j-1];}}return dp[m][n];}
};
4、下降路径最小和
下降路径最小和
第一步：确定状态表示
根据题意，题目是让我们求从第一行任意一个位置，依次向下，到最后一行任意一个位置，这些数的和最小，所以用 dp[i][j] 表示从第一行到达 (i，j）位置，这些数的和的最小值。
第二步：推出状态转移方程
第三步：初始化dp表
在使用状态转移方程的时候，我们会用到 j-1 ， i-1 和 j+1 位置的数据，那么对于第0行和第0列，以及最后一列来说，就会发生越界访问的问题。为了解决这一问题，我们可以给dp表多增加一行和两列。
然后从 （1，1）位置开始填写。需要注意的是，下标的对应关系，比如（1，1）对应的是原表中（0，0）的位置。
填表顺序：为了能够知道第 （i, j）位置的数据，我们需要知道 （i-1，j-1）和（i-1，j），以及（i-1, j+1) 位置的值，所以应该从左往右，从上向下填写dp表。
最后的返回值，我们需要返回到达最后一行任意位置的路径和最小，所以返回最后一行的最小值。
解题代码：
class Solution
{
public:int minFallingPathSum(vector<vector<int>>& matrix) {int m = matrix.size(), n = matrix[0].size();vector<vector<int>> dp(m+1, vector<int>(n+2, INT_MAX));for(int i = 0; i <= n+1; i++)dp[0][i] = 0;for(int i = 1; i <= m; i++){for(int j = 1; j <= n; j++){dp[i][j] = min(dp[i-1][j], min(dp[i-1][j-1], dp[i-1][j+1])) + matrix[i-1】[j-1];}}int ret = dp[m][1];for(int i = 2; i <= n; i++){if(ret > dp[m][i])ret = dp[m][i];}return ret;}
};