剑指Offer题解——动态规划

╰半夏微凉° 2022-11-24 14:06 189阅读 0赞

### 文章目录 ###

*   *  剑指 Offer 12. 矩阵中的路径
     *   *  回溯
     *  剑指 Offer 14- I. 剪绳子
     *   *  动态规划
     *  剑指 Offer 14- II. 剪绳子 II
     *   *  动态规划
     *  剑指 Offer 19. 正则表达式匹配
     *   *  解法
     *  剑指 Offer 47. 礼物的最大价值
     *   *  动态规划
     *  剑指 Offer 63. 股票的最大利润
     *   *  动态规划
         *   *  推荐阅读

## 剑指 Offer 12. 矩阵中的路径 ##

[剑指 Offer 12. 矩阵中的路径][Offer 12.]

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

\[\[“a”,“b”,“c”,“e”\],  
\[“s”,“f”,“c”,“s”\],  
\[“a”,“d”,“e”,“e”\]\]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

示例 1：
    
    输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
    输出：true
    示例 2：
    
    输入：board = [["a","b"],["c","d"]], word = "abcd"
    输出：false
    提示：
    
    1 <= board.length <= 200
    1 <= board[i].length <= 200

### 回溯 ###

class Solution {
        
        private int m, n;
        private int[][] direction = {
        {
        1, 0}, {
        -1, 0}, {
        0, 1}, {
        0, -1}};
        public boolean exist(char[][] board, String word) {
        
            if (word == null || word.length() == 0) {
        
                return true;
            }
            if (board == null || board.length == 0 || board[0].length == 0) {
        
                return false;
            }
            m = board.length;
            n = board[0].length;
            boolean[][] visited = new boolean[m][n];
            for (int i = 0; i < m; i++) {
        
                for (int j = 0; j < n; j++) {
        
                    if (dfs(0, i, j, visited, board, word)) {
        
                        return true;
                    }
                }
            }
            return false;
        }
        private boolean dfs(int curLen, int r, int c, boolean[][] visited, char[][] board, String word) {
        
            if (curLen == word.length()) {
        
                return true;
            }
            if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != word.charAt(curLen) || visited[r][c]) {
        
                return false;
            }
            visited[r][c] = true;
            for (int[] d : direction) {
        
                if (dfs(curLen + 1, r + d[0], c + d[1], visited, board, word)) {
        
                    return true;
                }
            }
            visited[r][c] = false;
            return false;
        }
    }

## 剑指 Offer 14- I. 剪绳子 ##

[剑指 Offer 14- I. 剪绳子][Offer 14- I.]

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m-1\] 。请问 k\[0\]*k\[1\]*…\*k\[m-1\] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

示例 1：
    
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1
    示例 2:
    
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
    提示：
    
    2 <= n <= 58

### 动态规划 ###

class Solution {
        
        public int cuttingRope(int n) {
        
            int[] dp = new int[n + 1];
            dp[1] = dp[2] = 1;
            for (int i = 3; i <= n; i++) {
        
                for (int j = 1; j < i; j++) {
        
                    dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[i - j] * j));
                }
            }
            return dp[n];
        }
    }

## 剑指 Offer 14- II. 剪绳子 II ##

[剑指 Offer 14- II. 剪绳子 II][Offer 14- II. _ II]

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m - 1\] 。请问 k\[0\]*k\[1\]*…\*k\[m - 1\] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：
    
    输入: 2
    输出: 1
    解释: 2 = 1 + 1, 1 × 1 = 1
    示例 2:
    
    输入: 10
    输出: 36
    解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
     
    
    提示：
    
    2 <= n <= 1000

### 动态规划 ###

详细题解见[https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/][https_leetcode-cn.com_problems_jian-sheng-zi-ii-lcof_solution_mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f]

class Solution {
        
        public int cuttingRope(int n) {
        
            if(n <= 3) return n - 1;
            int b = n % 3, p = 1000000007;
            long rem = 1, x = 3;
            for(int a = n / 3 - 1; a > 0; a /= 2) {
        
                if(a % 2 == 1) rem = (rem * x) % p;
                x = (x * x) % p;
            }
            if(b == 0) return (int)(rem * 3 % p);
            if(b == 1) return (int)(rem * 4 % p);
            return (int)(rem * 6 % p);
        }
    }

## 剑指 Offer 19. 正则表达式匹配 ##

[剑指 Offer 19. 正则表达式匹配][Offer 19.]

请实现一个函数用来匹配包含’. ‘和’*‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab\*a"均不匹配。

示例 1:
    
    输入:
    s = "aa"
    p = "a"
    输出: false
    解释: "a" 无法匹配 "aa" 整个字符串。
    示例 2:
    
    输入:
    s = "aa"
    p = "a*"
    输出: true
    解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
    示例 3:
    
    输入:
    s = "ab"
    p = ".*"
    输出: true
    解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
    示例 4:
    
    输入:
    s = "aab"
    p = "c*a*b"
    输出: true
    解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
    示例 5:
    
    输入:
    s = "mississippi"
    p = "mis*is*p*."
    输出: false
    s 可能为空，且只包含从 a-z 的小写字母。
    p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

### 解法 ###

class Solution {
        
        public boolean isMatch(String s, String p) {
        
            int m = s.length();
            int n = p.length();
            boolean[][] f = new boolean[m + 1][n + 1];
            f[0][0] = true;
            for (int i = 0; i <= m; ++i) {
        
                for (int j = 1; j <= n; ++j) {
        
                    if (p.charAt(j - 1) == '*') {
        
                        f[i][j] = f[i][j - 2];
                        if (matches(s, p, i, j - 1)) {
        
                            f[i][j] = f[i][j] || f[i - 1][j];
                        }
                    } else {
        
                        if (matches(s, p, i, j)) {
        
                            f[i][j] = f[i - 1][j - 1];
                        }
                    }
                }
            }
            return f[m][n];
        }
        private boolean matches(String s, String p, int i, int j) {
        
            if (i == 0) {
        
                return false;
            }
            if (p.charAt(j - 1) == '.') {
        
                return true;
            }
            return s.charAt(i - 1) == p.charAt(j - 1);
        }
    }

## 剑指 Offer 47. 礼物的最大价值 ##

[剑指 Offer 47. 礼物的最大价值][Offer 47.]

在一个 m\*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:
    
    输入: 
    [
      [1,3,1],
      [1,5,1],
      [4,2,1]
    ]
    输出: 12
    解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
     
    
    提示：
    
    0 < grid.length <= 200
    0 < grid[0].length <= 200

### 动态规划 ###

class Solution {
        
        public int maxValue(int[][] grid) {
        
            int m = grid.length, n = grid[0].length;
            for (int i = 1; i < n; ++i) {
        
                grid[0][i] += grid[0][i - 1];
            }
            for (int i = 1; i < m; ++i) {
        
                grid[i][0] += grid[i - 1][0];
            }
            for (int i = 1; i < m; i++) {
        
                for (int j = 1; j < n; j++) {
        
                    grid[i][j] += Math.max(grid[i - 1][j], grid[i][j - 1]);
                }
            }
            return grid[m - 1][n - 1];
        }
    }

## 剑指 Offer 63. 股票的最大利润 ##

[剑指 Offer 63. 股票的最大利润][Offer 63.]

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1:
    
    输入: [7,1,5,3,6,4]
    输出: 5
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
    示例 2:
    
    输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     
    
    限制：
    
    0 <= 数组长度 <= 10^5

### 动态规划 ###

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if (prices == null || prices.length == 0) {
        
                return 0;
            }
            int minPrices = prices[0];
            int maxProfit = 0;
            for (int i = 1; i < prices.length; i++) {
        
                if (minPrices > prices[i]) {
        
                    minPrices = prices[i];
                } else if (prices[i] - minPrices > maxProfit) {
        
                    maxProfit = prices[i] - minPrices;
                }
            }
            return maxProfit;
        }
    }

--------------------

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

--------------------

![format_png][]

[Offer 12.]: https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/
[Offer 14- I.]: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/
[Offer 14- II. _ II]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/
[https_leetcode-cn.com_problems_jian-sheng-zi-ii-lcof_solution_mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f]: https://leetcode-cn.com/problems/jian-sheng-zi-ii-lcof/solution/mian-shi-ti-14-ii-jian-sheng-zi-iitan-xin-er-fen-f/
[Offer 19.]: https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
[Offer 47.]: https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/
[Offer 63.]: https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png]: /images/20221124/0e607dd1cf934e2c8d00ebb3995356f9.png