0


动态规划:基础篇

1. 斐波那契数(LeetCode509)

题目描述https://leetcode.cn/problems/fibonacci-number/description/

解法1:动态规划(基础版)

解题思路:动态规划五部曲

  • Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:第i个数的斐波那契数值是dp[i]
  • Step2:确定递推公式 - dp[i] = dp[i - 1] + dp[i - 2] 题目已给
  • Step3:初始化dp数组 - 由递推公式可知,需要初始化前两个元素(题目已给) - dp[0] = 0- dp[1] = 1
  • Step4:确定遍历顺序 - 由递推公式可知,后面的斐波那契数值依赖于前面两个- 因此,需要从前向后遍历
  • Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>

class Solution 
{
public:
    int fib(int n) 
    {
        if (n <= 1) return n;

        // Step3:初始化dp数组
        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        // Step4:确定遍历顺序
        for (int i = 2; i <= n; i++)
        {
            // Step2:确定递推公式
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

int main()
{
    int n = 4;

    Solution s;
    int ans = s.fib(n);   // 3

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(n) 需要计算每个元素的斐波那契数值
  • 空间复杂度:O(n) 需要存储每个元素的斐波那契数值

注意事项

  • if (n <= 1) return n; 当n为0或1时,无法由递推公式推导得到,需要根据dp数组的含义直接返回结果,此处在实际编程过程中容易忽略。(所有动态规划题目都需要格外注意)

解法2:动态规划(优化版)

解题思路:利用"状态压缩"进行优化 → 由于当前数值仅依赖于前面两个数值,因此只需要维护两个数值 (后面将讲解的很多动规的题目其实都是当前状态依赖前两个,或者前三个状态,都可以做空间上的优化)

#include <iostream>
using namespace std;
#include <vector>
  
class Solution
{
public:
    int fib(int n)
    {
        if (n <= 1) return n;

        vector<int> dp(2, 0);  // 优化:只需要维护两个数值即可,不需要记录整个序列
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            int sum = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = sum;
        }
        return dp[1];
    }
};

int main()
{
    int n = 4;

    Solution s;
    int ans = s.fib(n);   // 3

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(n) 需要计算每个元素的斐波那契数值
  • 空间复杂度O(1) 无需存储每个元素的斐波那契数值(只需要维护两个数值即可,不需要记录整个序列)

2. 爬楼梯(方案个数)(斐波那契数列扩展)(LeetCode70)

题目描述https://leetcode.cn/problems/climbing-stairs/description/

解法1:动态规划(基础版)

解题思路:动态规划五部曲
爬到第1层楼梯:有1种方法
爬到第2层楼梯:有2种方法 1+1(每次爬一个台阶)、2(一次爬两个台阶)
爬到第3层楼梯:有3种方法
1 +2(先爬一个台阶、再爬两个台阶) 由第1层楼梯过来
1+1 +1(每次爬一个台阶) 由第2层楼梯过来
2 +1(先爬两个台阶、再爬一个台阶) 由第2层楼梯过来
可见,到第三层楼梯的状态 可以由 第二层楼梯 和 第一层楼梯状态 推导出来

  • Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:爬到第i层楼梯的方法个数有dp[i]种
  • Step2:确定递推公式 - 从dp[i]的定义可以看出,dp[i]可以有两个方向推出来 - dp[i-1]:上到第i-1层楼梯,有dp[i-1]种方法,再一步 跳一个台阶 即可到达第i层楼梯- dp[i-2]:上到第i-2层楼梯,有dp[i-2]种方法,再一步 跳两个台阶 即可到达第i层楼梯- dp[i] = dp[i-1] + dp[i-2]
  • Step3:初始化dp数组 - 由递推公式可知,需要初始化前两个元素 - dp[1] = 1- dp[2] = 2- 注意:此处并不初始化dp[0],因为没有实际意义- 很多题解强行将dp[0]初始化为1,基本都是直接奔着答案去解释的(因为在递推的过程中i从2开始遍历本题就能过)
  • Step4:确定遍历顺序 - 由递推公式可知,需要从前向后遍历
  • Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>

class Solution 
{
public:
    int climbStairs(int n) 
    {
        if (n <= 2) return n;

        vector<int> dp(n+1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)  // 注意:此处i是从3开始遍历
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

int main()
{
    Solution s;
    int ans = s.climbStairs(3);

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(n) 需要计算到达每层楼梯的方法个数
  • 空间复杂度:O(n) 需要存储到达每层楼梯的方法个数

解法2:动态规划(优化版)

解题思路:利用"状态压缩"进行优化 → 由于当前数值仅依赖于前面两个数值,因此只需要维护两个数值 (动态规划的常见优化思路)

#include <iostream>
using namespace std;
#include <vector>

class Solution
{
public:
    int climbStairs(int n)
    {
        if (n <= 2) return n;

        vector<int> dp(3);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++)  // 注意:此处i是从3开始遍历
        {
            int sum = dp[1] + dp[2];
            dp[1] = dp[2];
            dp[2] = sum;
        }
        return dp[2];
    }
};

int main()
{
    Solution s;
    int ans = s.climbStairs(3);

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(n) 需要计算到达每层楼梯的方法个数
  • 空间复杂度O(1) 无需存储每个元素的斐波那契数值(只需要维护两个数值即可,不需要记录整个序列)

3. 爬楼梯(最小花费)(LeetCode746)

题目描述https://leetcode.cn/problems/min-cost-climbing-stairs/

解法1:动态规划(基础版)

解题思路:动态规划五部曲

  • Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:到达第i台阶所花费的最少体力为dp[i]
  • Step2:确定递推公式 - 由于每次只能向上爬一个或者两个台阶,因此到达第i台阶有两个途径 - 从第i-1台阶跳1步:需要花费 dp[i-1]+cost[i-1]- 从第i-2台阶跳2步:需要花费 dp[i-2]+cost[i-2]- dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
  • Step3:初始化dp数组 - 题目描述:可以选择从下标为0或下标为1的台阶开始爬楼梯- 到达第0个台阶是不花费体力,但从第0个台阶往上跳的话,需要花费cost[0]- 到达第1个台阶是不花费体力,但从第1个台阶往上跳的话,需要花费cost[1]- dp[0] = 0- dp[1] = 0
  • Step4:确定遍历顺序 - 由递推公式可知,需要从前向后遍历
  • Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>

class Solution 
{
public:
    int minCostClimbingStairs(vector<int>& cost) 
    {
        vector<int> dp(cost.size()+1);
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i <= cost.size(); i++)
        {
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[cost.size()];
    }
};

int main()
{
    vector<int> cost{ 10,15,20 };   // 15
    //vector<int> cost{ 1,100,1,1,1,100,1,1,100,1 };   // 6

    Solution s;
    int ans = s.minCostClimbingStairs(cost);

    cout << ans << endl;
}

复杂度分析

  • 时间复杂度:O(n) 需要计算到达每层楼梯的最小体力
  • 空间复杂度:O(n) 需要存储到达每层楼梯的最小体力

解法2:动态规划(优化版)

#include <iostream>
using namespace std;
#include <vector>

class Solution
{
public:
    int minCostClimbingStairs(vector<int>& cost)
    {
        vector<int> dp(2);
        dp[0] = 0;
        dp[1] = 0;

        for (int i = 2; i <= cost.size(); i++)
        {
            int dpi = min(dp[0] + cost[i-2], dp[1] + cost[i-1]);
            dp[0] = dp[1];
            dp[1] = dpi;
        }
        return dp[1];
    }
};

int main()
{
    vector<int> cost{ 10,15,20 };   // 15
    //vector<int> cost{ 1,100,1,1,1,100,1,1,100,1 };   // 6

    Solution s;
    int ans = s.minCostClimbingStairs(cost);

    cout << ans << endl;
}

复杂度分析

  • 时间复杂度:O(n) 需要计算到达每层楼梯的最小体力
  • 空间复杂度O(1)

4. 不同路径(无障碍)(LeetCode62)

题目描述https://leetcode.cn/problems/unique-paths/description/

解法1:动态规划(基础版)

解题思路:动态规划五部曲

  • Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i][j]:从(0,0)出发到达(i,j)的不同路径有dp[i][j]条
  • Step2:确定递推公式 - 机器人每次只能向下或者向右移动一步,因此到达(i,j)有两个途径 - 从(i-1,j)向下移动:dp[i-1][j] 从(0,0)出发,到(i-1,j)的不同路径个数- 从(i,j-1)向右移动:dp[i][j-1] 从(0,0)出发,到(i,j-1)的不同路径个数- dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
  • Step3:初始化dp数组 - 从(0,0)出发,到达第一行的任意位置,只有1种路径 → dp[0][j] = 1- 从(0,0)出发,到达第一列的任意位置,只有1种路径 → dp[i][0] = 1- 注意:只能向下或向右移动
  • Step4:确定遍历顺序 - 由递推公式可知,需要从前向后、从上向下遍历
  • Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>

class Solution
{
public:
    int uniquePaths(int m, int n) 
    {
        // 示例:m=3 n=7
        // 1  1  1  1  1  1  1
        // 1  2  3  4  5  6  7
        // 1  3  6  10 15 21 28

        // Step3:初始化dp数组
        vector<vector<int>> dp(m, vector<int>(n, 0));   // 二维数组的初始化(重要)
        for (int i = 0; i < m; i++)  dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        // Step4:确定遍历顺序
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                // Step2:确定递推公式
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

int main()
{
    Solution s;
    int ans = s.uniquePaths(3, 7);  // 28

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(m×n) 需要计算到达每一个位置的不同路径个数,两层for循环(第一层for循环遍历m-1行,第二层for循环遍历n-1列)
  • 空间复杂度:O(m×n) 需要存储到达每一个位置的不同路径个数

解法2:动态规划(优化版)

解题思路:使用一维数组(可以理解为滚动数组)进行空间优化 → 不利于理解,但可以优化空间

#include <iostream>
using namespace std;
#include <vector>

class Solution
{
public:
    int uniquePaths(int m, int n)
    {
        // 示例:m=3 n=7
        // 初始化一维数组    1  1  1  1  1  1  1
        // i=1              1  2  3  4  5  6  7
        // i=2              1  3  6  10 15 21 28

        // Step3:初始化dp数组
        vector<int> dp(n, 1);
        // Step4:确定遍历顺序(只能先遍历行,后遍历列)
        for (int i = 1; i < m; i++)       // 遍历行时,只能从上向下遍历
        {
            for (int j = 1; j < n; j++)   // 遍历列时,只能从前向后遍历
            // for (int j = n-1; j > 0; j--)  // 错误
            {
                // Step2:确定递推公式
                // dp[j-1]:在计算dp[j]时,dp[j-1]已经计算完毕,因此dp[j-1]为第i行("新值") → 从(i,j-1)出发,向右移动
                // dp[j](公式右侧):dp[j]还没有计算,因此dp[j]为第i-1行("旧值") → 从(i-1,j)出发,向下移动
                dp[j] = dp[j - 1] + dp[j];
            }
        }
        return dp[n - 1];
    }
};

int main()
{
    Solution s;
    int ans = s.uniquePaths(3, 7);  // 28

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(m×n) 需要计算到达每一个位置的不同路径个数
  • 空间复杂度O(n) 每一阶段仅存储一行中所有位置的信息(先计算完一行,再计算下一行)

5. 不同路径(有障碍)(LeetCode63)

题目描述https://leetcode.cn/problems/unique-paths-ii/description/

解法1:动态规划(基础版)

解题思路:本题与不同路径(无障碍)的区别

  • 区别1dp数组的初始化- 不同路径1:直接将第一行和第一列初始化为1- 不同路径2:若某个位置存在障碍物,则该位置及其之后的所有位置均不可达
  • 区别2递推公式- 不同路径1:所有位置都可以计算递推公式- 不同路径2:若某个位置存在障碍物,则该位置的不同路径个数为0,无需计算递推公式,而是直接使用默认值(遇到障碍dp[i][j]保持0)
#include <iostream>
using namespace std;
#include <vector>

class Solution 
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) 
    {
        int m = obstacleGrid.size();     // 网格的行数
        int n = obstacleGrid[0].size();  // 网格的列数

        // 若起点或终点存在障碍物,则表明终点不可达,直接返回路径个数0
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;

        // Step3:初始化dp数组
            // 若第一行存在障碍物,则该障碍物及其之后的所有位置均不可达;若第一行不存在障碍物,则所有位置均初始化为1
            // 若第一列存在障碍物,则该障碍物及其之后的所有位置均不可达;若第一列不存在障碍物,则所有位置均初始化为1
        // 注意代码里for循环的终止条件,一旦遇到obstacleGrid[i][0] == 1的情况,就停止dp[i][0]的赋值1的操作,dp[0][j]同理
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;      // 初始化第一列
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;      // 初始化第一行

        // Step4:确定遍历顺序
        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++)
            {
                // Step2:确定递推公式
                // 当前位置不存在障碍物,执行if语句,计算达到该位置的不同路径个数
                // 当前位置存在障碍物,不执行if语句,使用默认的初始化值0,表明该位置不可达 或 达到该位置的不同路径个数为0
                if (obstacleGrid[i][j] == 0)
                {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

int main()
{
    vector<vector<int>> obstacleGrid{ {0,0,0},{0,1,0},{0,0,0} };  // 2
    //vector<vector<int>> obstacleGrid{ {0,1},{0,0} };  // 1

    Solution s;
    int ans = s.uniquePathsWithObstacles(obstacleGrid);

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(mxn)
  • 空间复杂度:O(mxn)

注意事项

  • if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0; 若起点或终点存在障碍物,则表明终点不可达,直接返回路径个数0(易漏点)

解法2:动态规划(优化版)

#include <iostream>
using namespace std;
#include <vector>

class Solution
{
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid)
    {
        int m = obstacleGrid.size();     // 网格的行数
        int n = obstacleGrid[0].size();  // 网格的列数

        // 若起点或终点存在障碍物,则表明终点不可达,直接返回路径个数0
        if (obstacleGrid[0][0] == 1 || obstacleGrid[m - 1][n - 1] == 1) return 0;

        // Step3:初始化dp数组
        vector<int> dp(n, 0);
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[j] = 1;

        // Step4:确定遍历顺序
        for (int i = 1; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                // Step2:确定递推公式
                // 对于第1列:若存在障碍物,则赋值为0;若不存在障碍物,保持不变
                // 对于其余列:若存在障碍物,则赋值为0;若不存在障碍物,则利用递推公式推导              
                if (obstacleGrid[i][j] == 1)   // 若存在障碍物(无论哪一列),则赋值为0
                {
                    dp[j] = 0;
                }
                else if(j != 0)                // 若不存在障碍物且非第1列,则利用递推公式
                {
                    dp[j] = dp[j - 1] + dp[j];
                }
                // 注:以上代码不能修改如下
                // if (obstacleGrid[i][j] == 1) dp[j] = 0;   // 若存在障碍物,则赋值为0
                // if (j != 0) dp[j] = dp[j - 1] + dp[j];    // 若不存在障碍物,则利用递推公式(第一列不存在障碍物,则延续上一行的结果,不需要任何操作)
            }
        }
        return dp[n - 1];
    }
};

int main()
{
    vector<vector<int>> obstacleGrid{ {0,0,0},{0,1,0},{0,0,0} };  // 2
    //vector<vector<int>> obstacleGrid{ {0,1},{0,0} };  // 1

    Solution s;
    int ans = s.uniquePathsWithObstacles(obstacleGrid);

    cout << ans << endl;

    system("pause");
    return 0;
}

复杂度分析

  • 时间复杂度:O(mxn)
  • 空间复杂度:O(n)

6. 整数拆分(LeetCode343)

待补充!!!

7. 不同的二叉搜索树(LeetCode96)

题目描述https://leetcode.cn/problems/unique-binary-search-trees/description/

以"n=3"举例分析

  • 当1为头结点时:右子树有两个节点,两个节点的布局 和 n=2时两棵树的布局 是一样的
  • 当2为头结点时:左右子树都只有一个节点,一个节点的布局 和 n=1时只有一棵树的布局 是一样的
  • 当3为头结点时:左子树有两个节点,两个节点的布局 和 n=2时两棵树的布局 是一样的 - dp[3]:元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量- 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量dp[2] * 左子树有0个元素的搜索树数量dp[0]- 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量dp[1] * 左子树有1个元素的搜索树数量dp[1]- 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量dp[0] * 左子树有2个元素的搜索树数量dp[2]- dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

解题思路:动态规划五部曲

  • Step1:确定dp数组(一维)/dp表格(二维)、下标的含义 - dp[i]:由i个节点组成的二叉搜索树的个数为dp[i]
  • Step2:确定递推公式 - 假设头节点的数值为j(需要遍历头节点的所有可能)- dp[j-1]:由j-1个节点组成的二叉搜索树的个数(左子树的节点个数为j-1)- dp[i-j]:由i-j个节点组成的二叉搜索树的个数(右子树的节点个数为i-j)
  • Step3:初始化dp数组 - dp[0] = 1- dp[1] = 1 - dp[2] = 2
  • Step4:确定遍历顺序 - 从递推公式可以看出,i是由j-1和i-j推导而来,因此需要从前向后遍历- j从1遍历到i:j-1小于i;i-j小于i,因此i由小于i的项推导得到
  • Step5:打印dp数组(调试)
#include <iostream>
using namespace std;
#include <vector>

class Solution
{
public: 
    int numTrees(int n) 
    {
        if (n == 1) return 1;
        if (n == 2) return 2;

        vector<int> dp(n + 1, 0);
        dp[0] = 1;  // 易错点:dp[0]不能为0,否则会导致左右子树的布局个数相乘为0
        dp[1] = 1;
        dp[2] = 2;

        for (int i = 3; i <= n; i++)      // 第一层for循环:遍历二叉搜索树中的节点个数
        {
            for (int j = 1; j <= i; j++)  // 第二层for循环:遍历头节点的数值(状态)
            {
                dp[i] += (dp[j - 1] * dp[i - j]);
            }
        }
        return dp[n];
    } 
};

int main()
{
    //int n = 3;  // 5
    int n = 1;  // 1

    Solution s;
    int ans = s.numTrees(n);

    cout << ans << endl;

    system("pause");
    return 0;
}

注意事项:当结点个数为0时,是否需要初始化,应该初始化为什么?这是一个难点(易错点、易漏点)。

  • dp[0] = 1; dp[0]不能为0,否则会导致左右子树的布局个数相乘为0
  • 本题的解法不能进行状态压缩,因为每次计算dp[i]时,需要依赖前面的所有状态。
标签: 动态规划 算法

本文转载自: https://blog.csdn.net/weixin_39549734/article/details/140842868
版权归原作者 华科大胡子 所有, 如有侵权,请联系我们删除。

“动态规划:基础篇”的评论:

还没有评论