字数统计: 3k字   |   阅读时长: 13分

动态规划-1

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，

例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

对于动态规划问题，我将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！

  1. 确定dp数组（dp table）以及下标的含义

  2. 确定递推公式

  3. dp数组如何初始化

  4. 确定遍历顺序

  5. 举例推导dp数组

509. 斐波那契数 - 力扣（LeetCode） (leetcode-cn.com)

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

1
2
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

  1. 确定dp数组以及下标的含义，dp[i]的定义为：第i个数的斐波那契数值是dp[i]
  2. 确定递推公式：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];
  3. dp数组初始化：dp[0] = 0; dp[1] = 1;
  4. 确定遍历顺序：从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的
  5. 举例推导dp数组，按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//时间复杂度：O(n)
//空间复杂度：O(n)
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];
    }
};

70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
  1. 确定dp数组以及下标的含义：dp[i]： 爬到第i层楼梯，有dp[i]种方法
  2. 确定递推公式：dp[i] = dp[i - 1] + dp[i - 2] 。
  3. 初始化：dp[1] = 1，dp[2] = 2
  4. 遍历顺序：从前向后
  5. 举例模拟推导dp数组，证明正确
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//时间复杂度：$O(n)$
//空间复杂度：$O(n)$
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++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};

这道题目还可以继续深化，就是一步一个台阶，两个台阶，三个台阶，直到 m个台阶，有多少种方法爬到n阶楼顶。

这其实是一个完全背包问题，实现代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int climbStairs(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) { // 把m换成2，就可以AC爬楼梯这道题
                if (i - j >= 0) dp[i] += dp[i - j];
            }
        }
        return dp[n];
    }
};

746. 使用最小花费爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

1
2
3
4
5
6
请你计算并返回达到楼梯顶部的最低花费。
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
  总花费为 15 。
  1. dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]. (注意这里认为是第一步一定是要花费,最后一步不用花费)
  2. 状态转移方程：dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
  3. dp数组初始化：dp[0] = cost[0]; dp[1] = cost[1];
  4. 遍历顺序从前到后
  5. 模拟验证dp数组是否正确。
1
2
3
4
5
6
7
8
9
10
11
12
13
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]);
    }
};

62. 不同路径 - 力扣（LeetCode） (leetcode-cn.com)

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

1
2
3
4
5
6
7
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

方法一：这道题目，刚一看最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。

注意题目中说机器人每次只能向下或者向右移动一步，那么其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int dfs(int i, int j, int m, int n)
    {
        if(i > m || j > n)
        return 0;
        if(i == m && j == n)
        return 1;
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

来分析一下时间复杂度，这个深搜的算法，其实就是要遍历整个二叉树。

这棵树的深度其实就是m+n-1（深度按从1开始计算）。

那二叉树的节点个数就是 2^(m + n - 1) - 1。可以理解深搜的算法就是遍历了整个满二叉树（其实没有遍历整个满二叉树，只是近似而已）

所以上面深搜代码的时间复杂度为O(2^(m + n - 1) - 1)，可以看出，这是指数级别的时间复杂度，是非常大的。

方法2：动态规划

  1. dp数组的定义:dp[i][j]：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。
  2. 递推公式：dp[i][j]= dp[i - 1][j] + dp[i][j - 1]
  3. 数组初始化：如何初始化呢，首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理。
  4. 从左到右即可
  5. 模拟检测dp数组是否正确。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//时间复杂度：O(m × n)
//空间复杂度：O(m × n)
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];
    }
};

63. 不同路径 II - 力扣（LeetCode） (leetcode-cn.com)

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

1
2
3
4
5
6
输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

这个题是上一个题的升级版，加入了障碍物。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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++) //初始化，如果有障碍，右侧的都到不了了，全是0
        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) //障碍物对应的dp数组应该清零
            continue;
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

343. 整数拆分 - 力扣（LeetCode） (leetcode-cn.com)

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

1
2
3
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

动态规划五步：

  1. dp[i]表示拆分数字i，能够返回的最大乘积是dp[i].
  2. 确定递推公式。dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));也可以这么理解，j (i - j) 是单纯的把整数拆分为两个数相乘，而j dp[i - j]是拆分成两个以及两个以上的个数相乘。然后再取随着j变化最大的dp.
  3. dp[2] = 1
  4. 遍历顺序从前向后，i从3到n，j从1到i - 1
  5. 模拟检测dp数组是否正确。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//时间复杂度：O(n^2)
//空间复杂度：O(n)
class Solution {
public:
    int integerBreak(int n) {
        vector <int> dp(n + 1, 0);
        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];
    }
};

96. 不同的二叉搜索树 - 力扣（LeetCode） (leetcode-cn.com)

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

1
2
输入：n = 3
输出：5
  1. 确定dp数组（dp table）以及下标的含义：dp[i] ： 1到i为节点组成的二叉搜索树的个数为dp[i]。

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

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

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

  1. 递推公式：dp[3] = dp[2] dp[0] + dp[1] dp[1] + dp[0] * dp[2]
  2. 初始化dp[0] = 1
  3. 遍历顺序：遍历i里面每一个数作为头结点的状态，用j来遍历。
  4. 模拟检测dp数组是否正确。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//时间复杂度：$O(n^2)$
//空间复杂度：$O(n)$
class Solution {
public:
    int numTrees(int n) {
        vector <int> dp(n + 1, 0);
        dp[0] = 1;
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                dp[i] = dp[i] + dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊