LeetCode动态规划基础题-基础题

前言

动态规划基本上面试会被经常问到的问题，一些基础的题目可以快速的让自己入门。
觉得有帮助的，要不三连一下~

一、基础的问题 1. 斐波那契

class Solution {
public:
    int fib(int N) {
        if (N <= 1) return N;
        vector<int> dp(N + 1);
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= N; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[N];
    }
};

2. 爬楼梯

// 版本一
class Solution {
public:
    int climbStairs(int n) {
        if (n <= 1) return n; // 因为下面直接对dp[2] *** 作了，防止空指针
        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];
    }
};

3 使用最小花费爬楼梯

// 版本一
class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        vector<int> dp(cost.size());
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.size(); i++) {
            dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        // 注意最后一步可以理解为不用花费，所以取倒数第一步，第二步的最少值
        return min(dp[cost.size() - 1], dp[cost.size() - 2]);
    }
};

4 不同路径

class Solution {
public:
    int uniquePaths(int m, int n) {
        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;
        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 - 1][n - 1];
    }
};

5 不同路径II

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        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;
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

6. 整数拆分(剪绳子)

与整数拆分的题目是一样的，

class Solution {
public:
    int cuttingRope(int n) {
        //适当地举例子才能找到规律
        // 2 =1, 3=2, 4=4=dp[4] = max(dp[4-1]*dp[1]=dp[4-2]*dp[2])
        // 因为题目说n>1 所以边界判断可以简化
        if(n <4)
            return n-1;
        vector<int> dp(n+1,0);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;// 表示如果长度大于4的情况下 3 dp[3]不需要切分 为3
        // dp[i] = dp[i-j]*dp[j]; dp[i]当前最大乘积
        int maxValue = 0;
        for(int i = 4; i <=n; ++i){
            for(int j = 1; j <i; ++j){
                dp[i] = dp[i -j]*dp[j];
                maxValue = max(maxValue,dp[i]);
                dp[i]  = maxValue;
            }
        }
        return dp[n];
    }
};

一步到位的递归：

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j < i - 1; j++) {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

大数版

这题已经不能用动态规划了，因为取余之后max函数不能用来比较大小了。

比如取余后2000000014 会小于 1000000020

class Solution {
private:
    const long long int mod = 1e9+7;
public:
    int cuttingRope(int n) {
        // 尽可能与更多的3相乘
        if(n <= 3) return n -1;
        long res = 1;
        while(n > 4){
            res = (res * 3) %mod;
            n -= 3;
        }
        return (res *n) %mod;
    }
};

7 不同的二叉树

96.不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

思路：

先找规律

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

二、小结

结题一般分为五个步骤
1.dp以及下标的含义
2. 递推公式
3. 初始化
4. 遍历顺序
5.距离推导

三、学习资料

1. 代码随想录
2. LeetCode