首页 > 其他分享 >动态规划：基础篇

动态规划：基础篇

时间：2024-08-03 09:56:37浏览次数：12  
标签：obstacleGrid int 复杂度 基础 include 遍历 动态 规划 dp

目录

1. 斐波那契数(LeetCode509)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. 整数拆分(LeetCode343) 

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

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：动态规划(基础版)

解题思路：本题与不同路径（无障碍）的区别

  • 区别1：dp数组的初始化
    • 不同路径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]时，需要依赖前面的所有状态。

标签：obstacleGrid,int,复杂度,基础,include,遍历,动态,规划,dp
From： https://blog.csdn.net/weixin_39549734/article/details/140842868

相关文章

  • 动态规划：删除并获得点数
    目录题目描述思路解题过程复杂度Code 题目描述        给你一个整数数组 nums ，你可以对它进行一些操作。每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除 所有 等于 nums[i]-1 和 nums[i]+1 的元素。开始你拥有......
  • VUE动态路由和按钮的实现
    动态路由动态菜单//通过循环组件完成动态菜单<el-menuactive-text-color="#ffd04b"background-color="#545c64"class="el-menu-vertical-demo"text-color="#fff":collapse="isCollapse"routerdefault-activestyle="......
  • 动态规划学习笔记
    P3195求出玩具的前缀和\(S\)。设\(f_i\)表示区间\([1,i]\)的最大答案。开始应该是\(f_0=0\)。\(f_i=\max_{1\lej<i}f_j+(i+S_i-L-1-(j+S_j))^2\)。\(f_i=\max_{1\lej<i}f_j+(i+S_i-L-1)^2+(j+S_j)^2-2(i+S_i-L-1)(j+S_j)\)。设\(g_i=i+S_i,k=L+1\)，那么\(f_......
  • 基础算法：离散化(C++实现)
    文章目录1.离散化的定义2.离散化例题2.1离散化+二分2.2离散化+哈希表1.离散化的定义离散化是一种在程序设计和算法优化中常用的技术，其核心思想是将无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。具体来说，离散化是在不改变数据相对大小的条......
  • python数据分析与可视化基础
    一、数据分析介绍：1.数据分析含义：数据分析是指用适当的统计分析方法对收集来的大量数据进行分析，将它们加以汇总和理解并消化，以求最大化地开发数据的功能，发挥数据的作用。数据分析是为了提取有用信息和形成结论而对数据加以详细研究和概括总结的过程。数据分析的数学基础在20世纪早......
  • NLP从零开始------6基础文本处理之命名实体识别
    1.命名实体识别介绍        命名实体识别（NamedEntityRecognition，NER）中的“命名实体”一般是指文本中具有特别意义或指代性非常强的实体（比如：人名，地名，时间或者机构组织等）。        命名实体可分为实体类、时间类和数字类3大类，以及人名、机构名、地名、时间......
  • 【系统规划与管理师】【论文】【资料】IT服务方案设计与实施
    （整理该篇资料作为写作素材）内容涵盖：1、本阶段作为系统规划与管理师应做什么；（what）2、做法的目的和效益；（why）3、本阶段作为系统规划与管理师应怎么做；（how）————应思考的问题：————（1）如何将这些做法及效益串联起来，转换为自己的做法在论文中进行巧妙衔接和说明？（2）哪几个部分......
  • 机械学习—零基础学习日志（高数19——函数极限理解深化）
    零基础为了学人工智能，真的开始复习高数本次学习笔记，主要讲解函数极限的计算问题。极限四则运算规则这里有几个需要注意的地方。函数极限的四则运算，需要知道极限存在才能大胆放心的使用。而且使用超实数的概念会更好帮助我们理解，极限的运算。以下图来说。大量的同学，会直接......
  • Java基础5
    数组的概念数组（Array）是多个相同类型数据按照一定顺序排列的集合，并使用一个名字命名，并通过编号的方式对这些数据进行统一管理。 几个相关概念：①数组名 ②数组的元素 ③数组的下标 ④数组的长度特点：数组中的元素在内存中是依次紧密排列的，有序的。数组，属于引用数据类......
  • 微信小程序笔记完整总结，带你零基础速成微信小程序。
     ......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99