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

1.1 题目

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

输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

1.2 思路

动态规划的经典题目和入门题目，注意初始值，需要处理dp[i][0]和dp[0][i]两个边边上的数据。

1.3 代码

  1. class Solution {
  2.     public int maxValue(int[][] grid) {
  3.         int h = grid.length;
  4.         int w = grid[0].length;
  5.         int[][] dp = new int[h][w];
  7.         // 初始值
  8.         dp[0][0] = grid[0][0];
  9.         for (int i = 1; i < h; ++i) {
  10.             dp[i][0] += dp[i - 1][0] + grid[i][0];
  11.         }
  12.         for (int i = 1; i < w; ++i) {
  13.             dp[0][i] += dp[0][i - 1] + grid[0][i];
  14.         }
  16.         // dp数组其他部分赋值
  17.         for (int i = 0; i < h - 1; ++i) {
  18.             for (int j = 0; j < w - 1; ++j) {
  19.                 dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]) + grid[i + 1][j + 1];
  20.             }
  21.         }
  22.         return dp[h - 1][w - 1];
  23.     }
  24. }

2、剑指 Offer 49.丑数

做了多少遍还是不会….

2.1 题目

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

2.2 思路

image.png
image.png

2.3 代码

  1. class Solution {
  2.     public int nthUglyNumber(int n) {
  3.         // dp[i]表示第i + 1个丑数
  4.         int[] dp = new int[n];
  5.         dp[0] = 1;
  6.         int a = 0, b = 0, c = 0;
  7.         for (int i = 1; i < n; ++i) {
  8.             int n2 = dp[a] * 2;
  9.             int n3 = dp[b] * 3;
  10.             int n5 = dp[c] * 5;
  11.             dp[i] = Math.min(Math.min(n2, n3), n5);
  12.             if (dp[i] == n2) {
  13.                 ++a;
  14.             }
  15.             if (dp[i] == n3) {
  16.                 ++b;
  17.             }
  18.             if (dp[i] == n5) {
  19.                 ++c;
  20.             }
  21.         }
  22.         return dp[n - 1];
  23.     }
  24. }

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

3.1 题目

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
示例 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。

3.2 思路

这道题有两种思路：

  1. 暴力法，两层循环求数组中后面的元素与前面的元素的最大差值。时间复杂度O(n2)，空间复杂度O(1)；
  2. 动态规划，时间复杂度O(n)，空间复杂度O(1)。

这里介绍一下动态规划的思路。

  1. 状态定义：令dp[i]表示以prices[i]结尾的子数组对应的最大利润；
  2. 转移方程：dp[i] = Math.max(dp[i - 1], prices[i] - min[0: i - 1])，其中min[0: i - 1]表示prices数组下标从0到i-1范围中最小值；
  3. 初始状态：dp[0] = 0；
  4. 返回值：dp[prices.len - 1]。

对上述基本代码做优化：

  1. 由于最后仅是返回dp[len - 1]，可以将一维的dp数组用一个值res代替，将空间复杂度由O(n)降为O(1)；
  2. 由于要求min[0: i - 1]，如果单独求需要从0到i - 1遍历，需要O(n)的时间复杂度，如果在遍历prices数组的过程中维护一个前i - 1个元素（包括第i - 1）的最小值，令这个最小值在遍历的过程中取最小，就可以借助一遍遍历数组的机会获取，而无需再单独遍历获取。

    3.3 代码

    1. class Solution {
    2.  public int maxProfit(int[] prices) {
    3.      int res = 0;
    4.      if (prices == null || prices.length == 0) {
    5.          return res;
    6.      }
    7.      int minVal = prices[0];
    8.      for (int i = 1; i < prices.length; ++i) {
    9.          res = Math.max(res, prices[i] - minVal);
    10.          minVal = Math.min(minVal, prices[i]);
    11.      }
    12.      return res;
    13.  }
    14. }

    4、剑指 Offer 42.连续子数组的最大和

    这道题难点在于dp[i]该如何定义。

    4.1 题目

    输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
    示例1:

    输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

4.2 思路

暴力破解法O(n2)就不说了，本题用动态规划，优化的版本时间复杂度为O(n)，空间复杂度为O(1)。

  1. 状态定义：令dp[i]表示以nums[i]结尾的连续子串的和的最大值；
  2. 转移方程：由于dp[i]中一定会包含nums[i]，当dp[i - 1] < 0时，由于dp[i - 1]为dp[i]的值做了负贡献，还不如仅有一个元素nums[i]，因此转移方程为：

image.png

  1. 初始状态：dp[0] = nums[0]；
  2. 返回值：返回dp数组的最大值，需要在遍历的过程中维护一个res，不断地求res和dp[i]的最大值，并赋值给res。

优化：根据上述思路可以得到12.3中未优化版本的代码，此时空间复杂度为O(n）；由于题目中给了一个数组nums，因此可将原数组nums作为dp数组，直接在nums上修改即可，优化后的代码为12.3优化版，空间复杂度为O(1)。

输入参数nums不计到空间复杂度。

4.3 代码

未优化版：

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         int[] dp = new int[len];
  5.         dp[0] = nums[0];
  6.         int res = nums[0];
  7.         for (int i = 1; i < len; ++i) {
  8.             if (dp[i - 1] >= 0) {
  9.                 dp[i] = nums[i] + dp[i - 1];
  10.             } else {
  11.                 dp[i] = nums[i];
  12.             }
  13.             res = Math.max(res, dp[i]);
  14.         }
  15.         return res;
  16.     }
  17. }

优化版：

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         int res = nums[0];
  5.         for (int i = 1; i < len; ++i) {
  6.             nums[i] += Math.max(nums[i - 1], 0);
  7.             res = Math.max(res, nums[i]);
  8.         }
  9.         return res;
  10.     }
  11. }

5、剑指 Offer 14- I.剪绳子

妙啊。

5.1 题目

给你一根长度为 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

5.2 思路

  1. 状态定义：dp[i]表示长度为i的绳子，剪成至少两段绳子后，这些绳子长度的最大乘积；
  2. 转移方程：由于绳子至少要剪成两段，因此i >= 2。假设对长度为i的绳子剪出的第一段绳子长度为j，由于当j = 1时对乘积没有帮助，因此j >= 2。且不再对前面剪过的绳子（长度为j范围内的绳子）再剪，则有：
    1. 将长度为i的绳子分成 j 和 i- j两段，且对 i - j 不再继续剪了，此时的乘积为 j * (i - j)；
    2. 将长度为i的绳子分成 j 和 i- j两段，对 i - j 还要继续剪，此时的乘积为 j * dp[i - j]；
    3. 因此对于长度为i的绳子，当第一段绳子长度为j时，最大乘积为Math.max( j (i - j), j dp[i - j])；
    4. 由于 j 的取值范围是 [2, i)，需要遍历 j 的长度，因此最终的转移方程为：

dp[i] = Math.max(dp[i], Math.max( j (i - j), j dp[i - j])）。

  1. 初始状态：当绳子长度为0或者1时，由于dp[i]定义是绳子至少要剪成两段，因此这两种情况都无法剪，因此的dp[0] = 0, dp[1] = 0, dp[2] = 1；
  2. 返回值：dp[n]。

    5.3 代码

    1. class Solution {
    2.  public int cuttingRope(int n) {
    3.      int[] dp = new int[n + 1];
    4.      dp[2] = 1;
    5.      for (int i = 3; i <= n; ++i) {
    6.          for (int j = 2; j < i; ++j) {
    7.              dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
    8.          }
    9.      }
    10.      return dp[n];
    11.  }
    12. }

    6、剑指 Offer 60.n个骰子的点数

    好难啊……

    6.1 题目

    把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
    示例 1:

    输入: 1 输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

输入: 2 输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

6.2 思路

  1. 状态定义：dp[i][j]表示i个筛子，点数之和为j的概率；
  2. 转移方程：设输入 n 个骰子的解（即概率列表）为 f(n) ，其中「点数和」x 的概率为 f(n, x) 。假设已知 n - 1个骰子的解 f(n - 1) ，此时添加一枚骰子，求 n 个骰子的点数和为 x 的概率 f(n, x) 。当第n个骰子的点数为 1时，前 n - 1个骰子的点数和应为 x - 1 ，方可组成点数和 x ；同理，当第n个骰子点数为 2 时，前 n−1 个骰子应为 x - 2 ；以此类推，直至第n个骰子点数为 6 。将这 6 种情况的概率相加，即可得到概率 f(n, x) 。递推公式如下所示：

image.png
需要注意的是，上式中的 i 并不一定取遍[1, 6]的值，第 n 个筛子的点数（对应代码中的k）应小于n个筛子对应的点数之和（对应代码中的j）。

  1. 初始状态：初始化dp[1][1 ~6]即可，均为1/6。

  2. 返回值：返回dp数组第n行对应的一维数组即可。

    6.3 代码

    1. class Solution {
    2.  public double[] dicesProbability(int n) {
    3.      // n个筛子的组合的最大值为 6n - (n - 1) = 5n + 1
    4.      double[] res = new double[n * 5 + 1];
    5.      // dp[i][j]表示i个筛子，点数之和为j的概率
    6.      double[][] dp = new double[n + 1][n * 6 + 1];
    7.      // 初始化仅有一个筛子时dp[i][j]的值
    8.      for (int j = 1; j <= 6; ++j) {
    9.          dp[1][j] = 1.0 / 6;
    10.      }
    11.      // i表示筛子个数
    12.      for (int i = 2; i <= n; i++) {
    13.          // j表示i个筛子的点数之和
    14.          // j的最小值是i个筛子都摇到1，为i * 1 = 1
    15.          // j的最大值是i个筛子都摇到6，为i * 6
    16.          for (int j = i; j <= i * 6; j++) {
    17.              // 当i个筛子的点数之和为j时，考虑i个筛子的情况与i- 1个筛子之间的关系
    18.              // i - 1个筛子到i个筛子之间，多了第i个筛子的结果，第i个筛子的点数范围为[1, 6]
    19.              // k表示第i个筛子摇到的点数
    20.              for (int k = 1; k <= 6; k++) {
    21.                  // 虽然k理论上可以是[1, 6]，但是由于i个筛子的点数之和为j这个条件不变，
    22.                  // 因此必须满足j > k
    23.                  if (j - k > 0) {
    24.                      //
    25.                      dp[i][j] += dp[i - 1][j - k] / 6;
    26.                  } else {
    27.                      break;
    28.                  }
    29.              }
    30.          }
    31.      }
    32.      // 最后的结果数组跟dp数组的第n行有关，因为dp数组的行数代表筛子个数
    33.      // 实际上res数组就是dp数组中第n行对应的一维数组
    34.      for (int i = 0; i <= 5 * n; i++) {
    35.          // n个筛子点数之和最小值为 n * 1 = n，最大值为 6 * n, 因此是 n + i
    36.          res[i] = dp[n][n + i];
    37.      }
    38.      return res;
    39.  }
    40. }

    7、剑指 Offer 13.机器人的运动范围

    太难了……

    7.1 题目

    地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

    7.2 思路

    这道题看上去像是回溯 + dfs，但细节上不一样，建议背下来思路……

  3. dfs时只需要向下和向右搜索即可，这一点看题解，我是没咋看懂；

  4. visited矩阵在dfs时只需要将走过的点置为true，不需要像回溯那样再回滚；

  5. 有一个请十进制数每一位的数字的方法，可以留意一下这个通用的实现方案：

    1. int i = 45;
    2. List<Integer> list = new ArrayList<>();
    3. while (i != 0) {
    4.  // val是十进制数字的每一位数字
    5. int val = i % 10;
    6. list.add(val);
    7. i = i / 10;
    8. }

    7.3 代码

    1. class Solution {
    2.  private boolean[][] visited;
    3.  private int m;
    4.  private int n;
    5.  private int k;
    7.  public int movingCount(int m, int n, int k) {
    8.      this.m = m;
    9.      this.n = n;
    10.      this.k = k;
    11.      visited = new boolean[m][n];
    12.      return dfs(0, 0);
    13.  }
    15.  private int dfs(int i, int j) {
    16.      if (!isValied(i, j) || visited[i][j]) {
    17.          return 0;
    18.      }
    20.      // 不需要回滚
    21.      visited[i][j] = true;
    22.      // dfs只需要向下或者向右
    23.      return 1 + dfs(i + 1, j) + dfs(i, j + 1);
    24.  }
    26.  private boolean isValied(int i, int j) {
    27.      return i >= 0 && i < m && j >= 0 && j < n && getSum(i, j) <= k;
    28.  }
    30.  // 计算横纵坐标之和
    31.  private int getSum(int i, int j) {
    32.      int sum = 0;
    33.      while (i != 0) {
    34.          sum += i % 10;
    35.          i = i / 10;
    36.      }
    37.      while (j != 0) {
    38.          sum += j % 10;
    39.          j = j / 10;
    40.      }
    41.      return sum;
    42.  }
    43. }

    8、剑指 Offer 46. 把数字翻译成字符串

    这道题难点在于dp[i]该如何定义。

    8.1 题目

    输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
    示例1:

    输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

8.2 思路

暴力破解法O(n2)就不说了，本题用动态规划，优化的版本时间复杂度为O(n)，空间复杂度为O(1)。

  1. 状态定义：令dp[i]表示以nums[i]结尾的连续子串的和的最大值；
  2. 转移方程：由于dp[i]中一定会包含nums[i]，当dp[i - 1] < 0时，由于dp[i - 1]为dp[i]的值做了负贡献，还不如仅有一个元素nums[i]，因此转移方程为：

image.png

  1. 初始状态：dp[0] = nums[0]；
  2. 返回值：返回dp数组的最大值，需要在遍历的过程中维护一个res，不断地求res和dp[i]的最大值，并赋值给res。

优化：根据上述思路可以得到12.3中未优化版本的代码，此时空间复杂度为O(n）；由于题目中给了一个数组nums，因此可将原数组nums作为dp数组，直接在nums上修改即可，优化后的代码为12.3优化版，空间复杂度为O(1)。

输入参数nums不计到空间复杂度。

8.3 代码

未优化版：

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         int[] dp = new int[len];
  5.         dp[0] = nums[0];
  6.         int res = nums[0];
  7.         for (int i = 1; i < len; ++i) {
  8.             if (dp[i - 1] >= 0) {
  9.                 dp[i] = nums[i] + dp[i - 1];
  10.             } else {
  11.                 dp[i] = nums[i];
  12.             }
  13.             res = Math.max(res, dp[i]);
  14.         }
  15.         return res;
  16.     }
  17. }

优化版：

  1. class Solution {
  2.     public int maxSubArray(int[] nums) {
  3.         int len = nums.length;
  4.         int res = nums[0];
  5.         for (int i = 1; i < len; ++i) {
  6.             nums[i] += Math.max(nums[i - 1], 0);
  7.             res = Math.max(res, nums[i]);
  8.         }
  9.         return res;
  10.     }
  11. }

9、剑指 Offer 43.1～n 整数中 1 出现的次数

太难了，这找规律，顶不住。

9.1 题目

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。
示例 1：

输入：n = 12 输出：5

示例 2：

输入：n = 13 输出：6

9.2 思路

太难了看题解吧……
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/

9.3 代码

  1. class Solution {
  2.     public int countDigitOne(int n) {
  3.         int digit = 1, res = 0;
  4.         int high = n / 10, cur = n % 10, low = 0;
  5.         while(high != 0 || cur != 0) {
  6.             if(cur == 0) res += high * digit;
  7.             else if(cur == 1) res += high * digit + low + 1;
  8.             else res += (high + 1) * digit;
  9.             low += cur * digit;
  10.             cur = high % 10;
  11.             high /= 10;
  12.             digit *= 10;
  13.         }
  14.         return res;
  15.     }
  16. }

10、剑指 Offer 10- II.青蛙跳台阶问题

10. 1 题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

10.2 思路

大数计算取余要注意，否则结果溢出。

10.3 代码

  1. class Solution {
  2.     public int numWays(int n) {
  3.         if (n == 0 || n == 1) {
  4.             return 1;
  5.         }
  6.         int[] dp = new int[n + 1];
  7.         dp[0] = dp[1] = 1;
  8.         for (int i = 2; i <= n; ++i) {
  9.             dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
  10.         }
  11.         return dp[n];
  12.     }
  13. }

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

放弃，这dp太难了。

12、剑指 Offer 10- I.斐波那契数列

12.1 题目

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：

输入：n = 2 输出：1

示例 2：

输入：n = 5 输出：5

12.2 思路

大数运算用BigInteger吧，我累了。

12.3 代码

  1. class Solution {
  2.     public int fib(int n) {
  3.         if (n == 0 || n == 1) {
  4.             return n;
  5.         }
  6.         BigInteger[] dp = new BigInteger[n + 1];
  7.         dp[0] = BigInteger.valueOf(0);
  8.         dp[1] = BigInteger.valueOf(1);
  9.         for (int i = 2; i <= n; ++i) {
  10.             dp[i] = dp[i - 1].add(dp[i - 2]);
  11.         }
  12.         return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
  13.     }
  14. }

13、剑指 Offer 14- II.剪绳子 II

13.1 题目

给你一根长度为 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。

13.2 思路

整体思路跟剪绳子1一样，唯一不同时需要大数运算。
BigInteger的api：

  1. // int -> BigInteger
  2. BigInteger bigValue = BigInteger.valueOf(value);
  4. // BigInteger -> int 
  5. int intValue = bigValue.intValue();
  7. // 比较两个BigInteger，返回其中较大的
  8. BigInteger maxValue = bigValue1.max(bigValue2);
  10. // 对BigInteger取余
  11. BigInteger bigRes = bigValue.mod(bigValue2)；

13.3 代码

  1. import java.math.BigInteger;
  3. class Solution {
  4.     public int cuttingRope(int n) {
  5.         BigInteger[] dp = new BigInteger[n + 1];
  6.         dp[0] = BigInteger.valueOf(0);
  7.         dp[1] = BigInteger.valueOf(0);
  8.         dp[2] = BigInteger.valueOf(1);
  9.         for (int i = 3; i <= n; ++i) {
  10.             for (int j = 2; j < i; ++j) {
  11.                 dp[i] = dp[i].max(BigInteger.valueOf(j * (i - j)).max(dp[i - j].multiply(BigInteger.valueOf(j))));
  12.             }
  13.         }
  14.         return dp[n].mod(BigInteger.valueOf(1000000007)).intValue();
  15.     }
  16. }

14、剑指 Offer 62. 圆圈中最后剩下的数字

约瑟夫环，看答案都费劲…..

14.1 题目

0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：

输入: n = 5, m = 3 输出: 3

示例 2：

输入: n = 10, m = 17 输出: 2

14.2 思路

背下来吧：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/
image.png

14.3 代码

  1. class Solution {
  2.     public int lastRemaining(int n, int m) {
  3.         int res = 0;
  4.         for (int i = 2; i <= n; ++i) {
  5.             res = (res + m) % i;
  6.         }
  7.         return res;
  8.     }
  9. }

15、64. 最小路径和

15.1 题目

image.png

15.2 思路

比较简单的dp问题，需要仔细，不然还是做错…..

15.3 代码

  1. class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int m = grid.length, n = grid[0].length;
  4.         int[][] dp = new int[m][n];
  5.         dp[0][0] = grid[0][0];
  6.         for (int i = 1; i < n; ++i) {
  7.             dp[0][i] = dp[0][i - 1] + grid[0][i];
  8.         }
  9.         for (int i = 1; i < m; ++i) {
  10.             dp[i][0] = dp[i - 1][0] + grid[i][0];
  11.         }
  12.         for (int i = 1; i < m; ++i) {
  13.             for (int j = 1; j < n; ++j) {
  14.                 dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
  15.             }
  16.         }
  17.         return dp[m - 1][n - 1];
  18.     }
  19. }

16、96. 不同的二叉搜索树

一点思路都没有，甚至不知道这是个dp的题目。打死都想不出来的状态转移方程，只能死记硬背，没有其他法子。

16.1 题目

image.png

16.2 思路

image.png
image.png

16.3 代码

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         int[] dp = new int[n + 1];
  4.         dp[0] = 1;
  5.         dp[1] = 1;
  7.         for (int i = 2; i <= n; ++i) {
  8.             for (int j = 1; j <=i; ++j) {
  9.                 dp[i] += dp[j - 1] * dp[i - j];
  10.             }
  11.         }
  12.         return dp[n];
  13.     }
  14. }

17、312. 戳气球

17.1 题目

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] nums[i] nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量。
示例 1：

输入：nums = [3,1,5,8] 输出：167 解释： nums = [3,1,5,8] —> [3,5,8] —> [3,8] —> [8] —> [] coins = 315 + 358 + 138 + 181 = 167

示例 2：

输入：nums = [1,5] 输出：10

17.2 思路

17.3 代码

18、62. 不同路径

18.1 题目

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
image.png

18.2 思路

标准的网格动态规划。

18.3 代码

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][] dp = new int[m][n];
  4.         // 初始值
  5.         dp[0][0] = 1;
  6.         for (int i = 1; i < n; ++i) {
  7.             dp[0][i] = 1;
  8.         }
  9.         for (int i = 1; i < m; ++i) {
  10.             dp[i][0] = 1;
  11.         }
  12.         for (int i = 1; i < m; ++i) {
  13.             for (int j = 1; j < n; ++j) {
  14.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  15.             }
  16.         }
  17.         return dp[m - 1][n - 1];
  18.     }
  19. }

19、279. 完全平方数

这个dp的定义真想不到。

19.1 题目

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 1：

输入：n = 12 输出：3 解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13 输出：2 解释：13 = 4 + 9

19.2 思路

image.png

19.3 代码

  1. class Solution {
  2.     public int numSquares(int n) {
  3.         int[] dp = new int[n + 1];
  4.         dp[0] = 0;
  5.         for (int i = 1; i <= n; ++i) {
  6.             int minVal = Integer.MAX_VALUE;
  7.             for (int j = 1; j * j <= i; ++j) {
  8.                 minVal = Math.min(minVal, dp[i - j * j]);
  9.             }
  10.             dp[i] = 1 + minVal;
  11.         }
  12.         return dp[n];
  13.     }
  14. }

20、121. 买卖股票的最佳时机

20.1 题目

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：

输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

20.2 思路

  1. 状态定义：dp[i]表示前i天的最大利润；
  2. 转移方程：前i天的最大利润，分为两种情况，最后求这两种情况的最大值：
    1. 第i天卖股票，则对应prices[i] - min[0, i - 1]， min[0, i - 1]表示前i - 1天（包括第i - 1天）的股票最小值；
    2. 第i天不卖股票，第i天的股票价格对dp[i]不产生影响，则dp[i] = dp[i - 1]。

则dp[i] = Math.max(prices[i] - min[0, i - 1], dp[i - 1])；

  1. 初始状态：dp[0] = 0，由dp[1]反向推出，比如[7, 6]这种情况；

  2. 返回值：dp[len - 1], len 为prices数组的长度。

    20.3 代码

    1. class Solution {
    2.  public int maxProfit(int[] prices) {
    3.      int len = prices.length;
    4.      int[] dp = new int[len + 1];
    5.      dp[0] = 0;
    6.      int minVal = Integer.MAX_VALUE;
    7.      for (int i = 1; i < len; ++i) {
    8.          minVal = Math.min(minVal, prices[i - 1]);
    9.          dp[i] = Math.max(dp[i - 1], prices[i] - minVal);
    10.      }
    11.      return dp[len - 1];
    12.  }
    13. }

    21、309. 最佳买卖股票时机含冷冻期

    21.1 题目

    给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

    21.2 思路

    真做不出来。

    21.3 代码

    1. class Solution {
    2.  public int maxProfit(int[] prices) {
    3.      if (prices.length == 0) {
    4.          return 0;
    5.      }
    7.      int n = prices.length;
    8.      // f[i][0]: 手上持有股票的最大收益
    9.      // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
    10.      // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
    11.      int[][] f = new int[n][3];
    12.      f[0][0] = -prices[0];
    13.      for (int i = 1; i < n; ++i) {
    14.          f[i][0] = Math.max(f[i - 1][0], f[i - 1][2] - prices[i]);
    15.          f[i][1] = f[i - 1][0] + prices[i];
    16.          f[i][2] = Math.max(f[i - 1][1], f[i - 1][2]);
    17.      }
    18.      return Math.max(f[n - 1][1], f[n - 1][2]);
    19.  }
    20. }

    22、337. 打家劫舍 III

    22.1 题目

    image.png

    22.2 思路

    image.png

    22.3 代码

    1. class Solution {
    2.  private Map<TreeNode, Integer> f = new HashMap<>();
    4.  private Map<TreeNode, Integer> g = new HashMap<>();
    6.  public int rob(TreeNode root) {
    7.      if (root == null) {
    8.          return 0;
    9.      }
    10.      dfs(root);
    11.      return Math.max(f.get(root), g.get(root));
    12.  }
    14.  private void dfs(TreeNode root) {
    15.      if (root == null) {
    16.          return;
    17.      }
    18.      dfs(root.left);
    19.      dfs(root.right);
    20.      f.put(root, root.val + g.getOrDefault(root.left, 0) + g.getOrDefault(root.right, 0));
    21.      g.put(root,
    22.              Math.max(f.getOrDefault(root.left, 0), g.getOrDefault(root.left, 0)) +
    23.                      Math.max(f.getOrDefault(root.right, 0), g.getOrDefault(root.right, 0)));
    24.  }
    25. }

    23、最大子数组和

    23.1 题目

    给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。
    示例 1：

    输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1] 输出：1

示例 3：

输入：nums = [5,4,-1,7,8] 输出：23

23.2 思路

动态规划的经典题目，暴力破解两次for循环就不说了。

  1. 令dp[i]表示以下标为i结尾的最大子数组和，则有转移方程：dp[i + 1] = Math.max(dp[i] + nums[i + 1], nums[i + 1])，dp[i]强调一定要以i这个下标结尾；
  2. 题目要求的最终解并不一定是以数组最后一个元素结尾的连续数组，以数组中任意一个元素结尾的连续数组均可以，只是要返回一个最大值，因此在遍历dp数组时需要维护一个最大值；
  3. 最终返回的是这个最大值，而不是dp[len - 1]；
  4. 由于dp数组中，dp[i + 1]仅与dp[i]有关系，因此可以考虑用一个变量代替这个一维数组dp，降低空间复杂度。

    23.3 代码

    一维dp数组：
    1. class Solution {
    2.  public int maxSubArray(int[] nums) {
    3.      int len = nums.length;
    4.      int[] dp = new int[len];
    5.      dp[0] = nums[0];
    6.      int res = nums[0];
    7.      for (int i = 1; i < len; ++i) {
    8.          dp[i] = Math.max(nums[i], dp[i - 1] + nums[i]);
    9.          res = Math.max(res, dp[i]);
    10.      }
    11.      return res;
    12.  }
    13. }
    优化后的dp：
    1. class Solution {
    2.  public int maxSubArray(int[] nums) {
    3.      int len = nums.length;
    4.      int dp = nums[0];
    5.      int res = nums[0];
    6.      for (int i = 1; i < len; ++i) {
    7.          dp = Math.max(nums[i], dp + nums[i]);
    8.          res = Math.max(res, dp);
    9.      }
    10.      return res;
    11.  }
    12. }

    24、爬楼梯

    24.1 题目

    假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
    示例 1：

    输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。

    1. 1 阶 + 1 阶
    2. 2 阶

示例 2：

输入：n = 3 输出：3 解释：有三种方法可以爬到楼顶。

  1. 1 阶 + 1 阶 + 1 阶
  2. 1 阶 + 2 阶
  3. 2 阶 + 1 阶

24.2 思路

就用动态规划做。

24.3 代码

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         if (n == 0 || n == 1) {
  4.             return 1;
  5.         }
  6.         int[] dp = new int[n + 1];
  7.         dp[0] = 1;
  8.         dp[1] = 1;
  9.         for (int i = 2; i <= n; ++i) {
  10.             dp[i] = dp[i - 1] + dp[i - 2];
  11.         }
  12.         return dp[n];
  13.     }
  14. }

25、198. 打家劫舍

25.1 题目

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：

输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1] 输出：12 解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。

25.2 思路

image.png
注意：dp[i - 1]表示前i间屋子的最大金额总和，因此dp数组长度就是nums数组长度。

25.3 代码

  1. class Solution {
  2.     public int rob(int[] nums) {
  3.         if (nums == null || nums.length == 0) {
  4.             return 0;
  5.         }
  6.         int n = nums.length;
  7.         int[] dp = new int[n];
  8.         dp[0] = nums[0];
  9.         if (n == 1) {
  10.             return dp[0];
  11.         }
  12.         dp[1] = Math.max(nums[0], nums[1]);
  13.         for (int i = 2; i < n; ++i) {
  14.             dp[i] = Math.max((dp[i - 2] + nums[i]), dp[i - 1]);
  15.         }
  16.         return dp[n - 1];
  17.     }
  18. }

26、300. 最长递增子序列

26.1 题目

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：

输入：nums = [10,9,2,5,3,7,101,18] 输出：4 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3] 输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7] 输出：1

26.2 思路

  1. 状态定义：令dp[i]表示以数组中下标为i结尾的最长上升子序列的长度，注意dp[i]一定要包含nums[i]；
  2. 转移方程：dp[i] = max(dp[j]) + 1，其中0 <= j < i且nums[i] > nums[j]；
  3. 初始状态：dp[0] = 1；
  4. 返回值：遍历dp数组时维护一个dp[i]的最大值，返回这个最大值。

    26.3 代码

    1. class Solution {
    2.  public int lengthOfLIS(int[] nums) {
    3.      if (nums == null || nums.length == 0) {
    4.          return 0;
    5.      }
    6.      int n = nums.length;
    7.      int res = 1;
    8.      int[] dp = new int[n];
    9.      dp[0] = 1;
    10.      for (int i = 1; i < n; ++i) {
    11.          int maxJ = 1;
    12.          for (int j = 0; j < i; ++j) {
    13.              if (nums[i] > nums[j]) {
    14.                  maxJ = Math.max(maxJ, dp[j]);
    15.                  dp[i] = maxJ + 1;
    16.                  res = Math.max(dp[i], res);
    17.              }
    18.          }
    19.      }
    20.      return res;
    21.  }
    22. }

    27、322. 零钱兑换

    27.1 题目

    给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。
    示例 1：

    输入：coins = [1, 2, 5], amount = 11 输出：3 解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3 输出：-1

示例 3：

输入：coins = [1], amount = 0 输出：0

27.2 思路

动态规划的题目，核心思想是：假设dp[i]为凑齐金额为i所需的最少硬币数目，那么有：
dp[i] = min(dp[i - c1], dp[i - c2], dp[i - c3], …dp[i - cn]) + 1，其中c1…cn为硬币中面值小于i的硬币面额。
注意当没有凑出任何方案的时候要返回-1，可以用一个amount + 1来做判断，因为凑出amount值所需最多的硬币数目就是amount（全部都是1），amount + 1是一个不可能达到的值，作为最大值。

27.3 代码

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         // dp[i]表示凑齐金额为i所需要的最少硬币数目
  4.         int[] dp = new int[amount + 1];
  5.         int max = amount + 1;
  6.         Arrays.fill(dp, max);
  7.         dp[0] = 0;
  9.         for (int i = 1; i <= amount; ++i) {
  10.             for (int j = 0; j < coins.length; ++j) {
  11.                 if (coins[j] <= i) {
  12.                     dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
  13.                 }
  14.             }
  15.         }
  16.         return dp[amount] > amount? -1: dp[amount];
  17.     }
  18. }

28、139. 单词拆分

28.1 题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意，你可以重复使用字典中的单词。

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false

28.2 思路

动态规划的题。

  1. 转态定义：定义dp[i]表示s字符串下标从0到i - 1的子串是否满足单词拆分的要求，dp为boolean类型数组，dp[0]表示空串。dp数组的长度为s.length() + 1，这是由返回值决定的；
  2. 转移方程：求dp[i]，即s字符串下标从0到 i -1的字符子串是否满足单词拆分要求，用一个j枚举从0到i - 1之间的点，判断左边0到j - 1下标的子串是否满足单词拆分要求，即dp[j]，判断右边的子串（从下标j到下标i - 1）是否在dict字典中，如果左右两边的条件都为true，即当前dp[i]的值为true，进入下一个dp[i + 1]的计算中；
  3. 初始状态：dp[0] = true，表示空串为true，比如s = leet, dict = leet，则当j = 0时，dp[0] = true，leet在dict中，取了完整的leet判断是否在dict中，因此dp[0]不应参与实际的判断，为true；

  4. 返回值：dp[s.length]。

    28.3 代码

    1. class Solution {
    2.  public boolean wordBreak(String s, List<String> wordDict) {
    3.      int len = s.length();
    4.      boolean[] dp = new boolean[len + 1];
    5.      dp[0] = true;
    6.      Set<String> set = new HashSet<>(wordDict);
    8.      for (int i = 1; i <= len; ++i) {
    9.          for (int j = 0; j < i; ++j) {
    10.              if (dp[j] && set.contains(s.substring(j, i))) {
    11.                  dp[i] = true;
    12.                  break;
    13.              }
    14.          }
    15.      }
    16.      return dp[len];
    17.  }
    18. }