第14章 动态规划

斐波那契问题

LC70：青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

代码：

class Solution {
    public int numWays(int n) {
        if (n == 0) {
            return 1;
        }
        int[] dp = new int[2];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i % 2] = (dp[(i - 1) % 2] + dp[(i - 2) % 2]) % 1000000007;
        }
        return dp[n % 2];
    }
}

剑指offerⅡ88：爬楼梯的最少成本

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

分析状态转移方程：

用$f(i)$表示从楼梯的第$i$级在往上爬的最少成本，如果一个楼梯有$n$个台阶(从0到n-1)，由于一次可以爬1个或2个台阶，所以$min\{f(n-1),f(n-2)\}$就是问题的最优解。

那么对于每个$i$，状态转移方程为$f(i)=min\{f(n-1),f(n-2)\}+cost[i]$

方法一：递归代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        return Math.min(dfs(cost, length - 1), dfs(cost, length - 2));
    }

    private int dfs(int[] cost, int i) {
        if (i == 0 || i == 1) {
            return cost[i];
        }
        return Math.min(dfs(cost, i - 1), dfs(cost, i - 2)) + cost[i];
    }
}

该方法超出时间限制，因为有非常多的重复计算，下面考虑使用缓存来存储计算过的数值，来优化递归算法。

方法二：使用缓存的递归代码（不容易理解）

注意，长度为2的时候需要特殊判断，书上并没有考虑到这种情况。

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        int[] dp = new int[length];
        //需要判断该特殊情况
        if (length == 2) {
            return Math.min(cost[0], cost[1]);
        }
        dfs(cost, dp, length - 1);
        return Math.min(dp[length - 1], dp[length - 2]);
    }

    private void dfs(int[] cost, int[] dp, int i) {
        if (i == 0 || i == 1) {
            dp[i] = cost[i];
            return;
        }
        //如果该位为0，表示还没有被计算出来，需要计算。否则忽略。
        if (dp[i] == 0) {
            dfs(cost, dp, i - 1);
            dfs(cost, dp, i - 2);
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
    }
}

方法三：空间复杂度为O(n)的迭代代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        int[] dp = new int[length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < length; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[length - 1], dp[length - 2]);
    }
}

方法四：空间复杂度为O(1)的迭代代码

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int length = cost.length;
        int first = cost[0];
        int second = cost[1];
        for (int i = 2; i < length; i++) {
            int num = Math.min(first, second) + cost[i];
            first = second;
            second = num;
        }
        return Math.min(first, second);
    }
}

单序列问题

剑指offerⅡ89：房屋偷盗

一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

**分析确定状态转移方程：**用$f(i)$表示从下标为0偷到下标为i的房子，最多能偷到多少钱。所以状态转移方程为

$$f(i)=max\{f(i-1),f(i-2) + nums[i]\}$$

也就是说，决定是否盗窃i房屋时，需要考虑盗窃或者不盗窃该房屋的收益，取最大的。

带缓存的递归代码

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return 0;
        }
        int[] dp = new int[length];
        Arrays.fill(dp, -1);
        dfs(nums, dp, length - 1);
        return dp[length - 1];
    }

    private void dfs(int[] nums, int[] dp, int i) {
        if (i == 0) {
            dp[0] = nums[0];
        } else if (i == 1) {
            dp[1] = Math.max(nums[0], nums[1]);
        } else if (dp[i] < 0) {
            dfs(nums, dp, i - 1);
            dfs(nums, dp, i - 2);
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
    }
}

空间复杂度为O(n)的迭代代码

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        //题目输入条件写明长度大于0，所以不用判断。
        if (length == 1){
            return nums[0];
        }
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[length - 1];
    }
}

空间复杂度为O(1)的迭代代码

class Solution {
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int first = nums[0];
        int second = Math.max(nums[0], nums[1]);
        for (int i = 2; i < length; i++) {
            int num = Math.max(second, first + nums[i]);
            first = second;
            second = num;
        }
        return second;
    }
}

剑指offerⅡ90：环形房屋偷盗

一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。

给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

**思路：**分别搜索[0, length-2]和[1, length-1]的区域，取最大值。

自己的代码：

书上的代码：

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        } else if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        int result_1 = helper(nums, 0, nums.length - 2);
        int result_2 = helper(nums, 1, nums.length - 1);
        return Math.max(result_1, result_2);
    }

    private int helper(int[] nums, int left, int right) {
        int[] dp = new int[2];
        dp[0] = nums[left];
        dp[1] = Math.max(nums[left], nums[left + 1]);
        for (int i = left + 2; i <= right; i++) {
            int j = i - left;
            dp[j % 2] = Math.max(dp[(j - 1) % 2], dp[(j - 2) % 2] + nums[i]);
        }
        return dp[(right - left) % 2];
    }
}

上面算法值得注意的地方是：如果对2取模再寻找dp下标的话，必须将下标做转换。更详细的说明是： int j = i - left; return dp[(right - left) % 2];

剑指offerⅡ91：粉刷房子

假如有一排房子，共 n 个，每个房子可以被粉刷成红色、蓝色或者绿色这三种颜色中的一种，你需要粉刷所有的房子并且使其相邻的两个房子颜色不能相同。

当然，因为市场上不同颜色油漆的价格不同，所以房子粉刷成不同颜色的花费成本也是不同的。每个房子粉刷成不同颜色的花费是以一个 n x 3 的正整数矩阵 costs 来表示的。

例如，costs[0][0] 表示第 0 号房子粉刷成红色的成本花费；costs[1][2] 表示第 1 号房子粉刷成绿色的花费，以此类推。

请计算出粉刷完所有房子最少的花费成本。

示例 ：

输入: costs = [[17,2,17],[16,16,5],[14,3,19]]
输出: 10
解释: 将 0 号房子粉刷成蓝色，1 号房子粉刷成绿色，2 号房子粉刷成蓝色。
     最少花费: 2 + 5 + 3 = 10。

思路：

要计算粉刷到标号为i的房子时的成本，还需要考虑标号为i-1的房子的颜色。因此需要三个表达式，即$r(i),g(i),b(i)$，分别表示为将标号为i的房子粉刷为红色，绿色，蓝色时粉刷标号从0到i的共i+1栋房子的最少成本。因此有如下的状态转移方程：

$$r(i)=min(g(i-1),b(i-1))+cost[i][0]\\ g(i)=min(r(i-1),b(i-1))+cost[i][1]\\ b(i)=min(r(i-1),g(i-1))+cost[i][2]$$

自己写的算法：

class Solution {
    public int minCost(int[][] costs) {
        if (costs.length == 0) {
            return 0;
        }
        int[] dp = new int[3];
        int[] temp = new int[3];
        for (int i = 0; i < 3; i++) {
            dp[i] = costs[0][i];
        }
        for (int i = 1; i < costs.length; i++) {
            for (int j = 0; j < 3; j++) {
                int prev_1 = dp[(j + 1) % 3];
                int prev_2 = dp[(j + 2) % 3];
                temp[j] = Math.min(prev_1, prev_2) + costs[i][j];
            }
            for (int j = 0; j < 3; j++) {
                dp[j] = temp[j];
            }
        }
        return Math.min(Math.min(dp[0], dp[1]), dp[2]);
    }
}

书上的算法：

剑指offerⅡ92：反转字符

如果一个由 '0' 和 '1' 组成的字符串，是以一些 '0'（可能没有 '0'）后面跟着一些 '1'（也可能没有 '1'）的形式组成的，那么该字符串是 单调递增 的。

我们给出一个由字符 '0' 和 '1' 组成的字符串 s，我们可以将任何 '0' 翻转为 '1' 或者将 '1' 翻转为 '0'。

返回使 s 单调递增 的最小翻转次数。

思路：

令$f(i)$表示为字符串下标从0到i的字符反转成符号要求，且最后一位为0的最少反转次数;

令$g(i)$表示为字符串下标从0到i的字符反转成符号要求，且最后一位为1的最少反转次数.

如果S[0,i-1]在反转之后得到的符合要求的字符串的最后一个字符是0，那么无论下标为i的字符是0还是1，这i+1个字符组成的字符串都是符合要求的。所以有下面的状态转移方程：

$$f(i)=f(i-1)\quad \text{若}S[i]=0\\ f(i)=f(i-1)+1\quad \text{若}S[i]=1$$

如果S[0,i-1]在反转之后得到的符合要求的字符串的最后一个字符是1，那么必须保证下标为i的字符是1，这样才能保证i+1个字符组成的字符串是符合要求的。所以有如下的状态转移方程：

$$g(i)=min\{f(i-1),g(i-1)\}+1\quad \text{若}S[i]=0\\ g(i)=min\{f(i-1),g(i-1)\}\quad \text{若}S[i]=1$$

空间复杂度$O(n)$的算法

class Solution {
    public int minFlipsMonoIncr(String s) {
        int length = s.length();
        int[] f = new int[length];
        int[] g = new int[length];
        char ch = s.charAt(0);
        f[0] = ch == '0' ? 0 : 1;
        g[0] = ch == '1' ? 0 : 1;
        for (int i = 1; i < length; i++) {
            ch = s.charAt(i);
            f[i] = f[i - 1] + (ch == '0' ? 0 : 1);
            g[i] = Math.min(f[i - 1], g[i - 1]) + (ch == '0' ? 1 : 0);
        }
        return Math.min(f[length - 1], g[length - 1]);

    }
}

空间复杂度$O(1)$的算法

class Solution {
    public int minFlipsMonoIncr(String s) {
        int length = s.length();
        int[] f = new int[2];
        int[] g = new int[2];
        char ch = s.charAt(0);
        f[0] = ch == '0' ? 0 : 1;
        g[0] = ch == '1' ? 0 : 1;
        for (int i = 1; i < length; i++) {
            ch = s.charAt(i);
            f[i % 2] = f[(i - 1) % 2] + (ch == '0' ? 0 : 1);
            g[i % 2] = Math.min(f[(i - 1) % 2], g[(i - 1) % 2]) + (ch == '0' ? 1 : 0);
        }
        return Math.min(f[(length - 1) % 2], g[(length - 1) % 2]);
    }
}

剑指offerⅡ93：最长斐波那契数列

如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：

• n >= 3
• 对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}

给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回 0 。

剑指offerⅡ94：最少回文分割

给定一个字符串 s，请将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的 最少分割次数 。

示例 ：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

**思路：**对于每个下标j，判断S[j,i]是不是回文。如果是回文，此时的分割次数为在S[0,j-1]的基础上加1。因此f(i)就是所有符合条件的j对应的f(i-1)的最小值加1。

class Solution {
    public int minCut(String s) {
        int length = s.length();
        boolean[][] isPal = new boolean[length][length];
        int[] dp = new int[length];
        //先确定子串的结尾字符，再次判断isPal[j + 1][i - 1]时一定是之前循环就已经判断过的
        for (int i = 0; i < length; i++) {
            for (int j = 0; j <= i; j++) {
                char ch1 = s.charAt(j);
                char ch2 = s.charAt(i);
                //三种情况：一个字符，两个字符，三个及以上的字符
                if ((i == j) || ((ch1 == ch2) && (isPal[j + 1][i - 1] || (j + 1 == i)))) {
                    isPal[j][i] = true;
                }
            }
        }

        for (int i = 0; i < length; i++) {
            if (isPal[0][i]) {
                dp[i] = 0;
            } else {
                dp[i] = i;//最大分割
                for (int j = 1; j <= i; j++) {
                    if (isPal[j][i]) {
                        dp[i] = Math.min(dp[i], dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[length - 1];
    }
}

值得注意的是：用$O(n^2)$复杂度计算出所有子串是否回文的方法。

LC343：剪绳子

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

方法一：动态规划

1. 我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来
2. 用一个dp数组记录从0到n长度的绳子剪掉后的最大乘积，也就是dp[i]表示长度为i的绳子剪成m段后的最大乘积，初始化dp[2] = 1
3. 我们先把绳子剪掉第一段（长度为j），如果只剪掉长度为1，对最后的乘积无任何增益，所以从长度为2开始剪
4. 剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为$j * dp[i - j]$。取两者最大值$max(j * (i - j), j * dp[i - j])$
5. 第一段长度j可以取的区间为[2,i)，对所有j不同的情况取最大值，因此最终dp[i]的转移方程为
6. $dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))$
7. 最后返回dp[n]即可

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

方法二：贪心法

尽可能把绳子分成长度为3的小段，如果最后一段是4，应不用再分。

class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        int ans = 1;
        while (n > 4) {
            n = n - 3;
            ans = ans * 3;
        }
        return n * ans;//如果n == 4,那么就是留下来不用再分的长度为4的小段
    }
}

双序列问题

剑指offerⅡ95：最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

• 例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。

两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路：

用$f(i,j)$表示第一个字符串从0到i的子字符串和第二个字符串从0到i的子字符串的最长公共子序列的长度。

如果$s1[i]$与$s2[j]$相同，那么$f(i,j)$相当于在$s1[0..i-1]$和$s2[0..j-1]$的最长公共子序列的后面加一个公共字符，也就是$f(i,j)=f(i-1,j-1)+1$

如果$s1[i]$与$s2[j]$不同，此时s1[0..i]和s2[0..j]的最长公共子序列要么是$s1[0..i-1]$和$s2[0..j]$的最长公共子序列，要么是$s1[0..i]$和$s2[0..j-1]$的最长公共子序列。所以有如下的状态转移方程：

$$f(i,j)=\left\{ \begin{aligned} & f(i-1,j-1)+1 & \text{s1[i]==s2[j]}\\ & max\{f(i-1,j),f(i,j-1)\} & \text{s1[i]!=s2[j]} \end{aligned} \right.$$

值得注意的是：我们用$f(i-1,j-1)$保存最终的结果，$f(0,j)$表示$s1[0]$和$s2[0..j]$的最长公共子序列长度，$f(-1,j)$表示空串和$s2[0..j]$的最长公共子序列长度(为0)。

在实现代码的时候我们将所有左标向后移动一位，用0来记-1位。

空间复杂度为O(mn)的算法：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length();
        int length2 = text2.length();
        int[][] dp = new int[length1 + 1][length2 + 1];
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    dp[i + 1][j + 1] = Math.max(dp[i][j + 1], dp[i + 1][j]);
                }
            }
        }
        return dp[length1][length2];
    }
}

空间复杂度为两行的算法：

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length();
        int length2 = text2.length();
        if (length1 < length2) {
            return longestCommonSubsequence(text2, text1);//使两行的长度达到最小，更省空间
        }
        int[][] dp = new int[2][length2 + 1];
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                if (text1.charAt(i) == text2.charAt(j)) {
                    dp[(i + 1) % 2][j + 1] = dp[i % 2][j] + 1;
                } else {
                    dp[(i + 1) % 2][j + 1] = Math.max(dp[i % 2][j + 1], dp[(i + 1) % 2][j]);
                }
            }
        }
        return dp[length1 % 2][length2];
    }
}

空间复杂度为一行的算法：

剑指offerⅡ96：字符串交织

给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。

两个字符串 s 和 t 交织 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：

• s = s1 + s2 + ... + sn
• t = t1 + t2 + ... + tm
• |n - m| <= 1
• 交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

提示：a + b 意味着字符串 a 和 b 连接。

示例 1：

img

输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

思路：

用$f(i,j)$表示字符串$s1$的下标从0到i的字符串和字符串$s2$的下标从0到j的字符串能否交织得到字符串$s3$的下标从$0$到$i+j+1$的子字符串，那么$f(i-1,j-1)$就是问题的解。

$s3[i+j+1]$可能来自$s1[i]$，也可能来自$s2[j]$。

• 如果$s3[i+j+1]==s1[i]$，那么$f(i,j)=f(i-1,j)$。
• 如果$s3[i+j+1]==s2[j]$，那么$f(i,j)=f(i,j-1)$。
• 如果$s3[i+j+1]==s1[i]==s2[j]$，那么，只要$f(i-1,j)$ 和 $f(i,j-1)$有一个为true，那么$f(i,j)$就为true，即$f(i,j)=f(i-1,j)||f(i,j-1)$

特别地，考虑到$i=0$，那么$f(0,j)$依赖于$f(-1,j)$ 和 $f(0,j-1)$的值。$f(-1,j)$的含义是当$s1$为空串时，$s1$和$s2$的交织情况，即$s2[0..j]$是否和$s3[0..j]$相同。此时还有状态转移方程：

$$f(-1,j)=\left\{ \begin{aligned} & false & \text{s2[j]!=s2[j]}\\ & f(-1,j-1) & \text{s2[j]==s2[j]} \end{aligned} \right.$$

跟上个题类似，多开辟一个长度用来记录-1，但是下标最少也是0，所以统一向后移位一位，用0来记录-1，以此类推。

空间复杂度O(mn)的算法：

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int length1 = s1.length();
        int length2 = s2.length();
        int length3 = s3.length();
        if (length1 + length2 != length3) {
            return false;
        }
        boolean[][] dp = new boolean[length1 + 1][length2 + 1];
        dp[0][0] = true;
        for (int j = 0; j < length2; j++) {
            dp[0][j + 1] = s2.charAt(j) == s3.charAt(j) && dp[0][j];
        }
        for (int i = 0; i < length1; i++) {
            dp[i + 1][0] = s1.charAt(i) == s3.charAt(i) && dp[i][0];
        }
        for (int i = 0; i < length1; i++) {
            for (int j = 0; j < length2; j++) {
                dp[i + 1][j + 1] = (s1.charAt(i) == s3.charAt(i + j + 1) && dp[i][j + 1]) 
                                || (s2.charAt(j) == s3.charAt(i + j + 1) && dp[i + 1][j]);
            }
        }
        return dp[length1][length2];
    }
}

优化空间效率：

剑指offerⅡ97：子序列的数目

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

示例 ：

输入：s = "rabbbit", t = "rabbit"
输出：3

输入：s = "babgbag", t = "bag"
输出：5

**思路：**用$f(i,j)$表示字符串S下标从0到i的子串中子序列为字符串下标从0到j的子串的数目，那么$f(m-1,n-1)$就是题目所求。特别地，当S的长度小于T的长度时，返回0。

当S[i]==T[j]时，有两种情况：

• 用S[i]去匹配T[j]，那么S[0..i]中包含T[0..j]的子序列数目等于S[0..i-1]中包含T[0..j-1]的子序列数目
• 社区S[i]，那么S[0..i]中包含T[0..j]的子序列数目等于S[0..i-1]中包含T[0..j]的子序列数目

所以有状态转移方程:$f(i,j)=f(i-1,j-1)+f(i-1,j)$

**当S[i]!=T[j]时：**只能舍去S[i]，此时$f(i,j)=f(i-1,j)$

特别地，需要考虑S和T为空的情形：

• 当两者都为空，两个字符串匹配，因此$f(-1,-1)=1$；
• 对于所有的i，当$j=-1$时，即T为空，$f(i,-1)=1$；
• 对于所有的j，当$i=-1$时，即S为空，$f(-1,j)=0$。

算法：

class Solution {
    public int numDistinct(String s, String t) {
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        dp[0][0] = 1;
        for (int i = 0; i < s.length(); i++) {
            dp[i + 1][0] = 1;
            for (int j = 0; j < t.length(); j++) {
                if (s.charAt(i) == t.charAt(j)) {
                    dp[i + 1][j + 1] = dp[i][j] + dp[i][j + 1];
                } else {
                    dp[i + 1][j + 1] = dp[i][j + 1];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

优化空间效率：

LC44：通配符匹配

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。

'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。

两个字符串完全匹配才算匹配成功。

说明:

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。

思路：

• 边界条件，只有连续的*可以匹配空的字符串s，其余的情况当s和p为空时都为false

• 如果p[i] == s[i]或p[i] == '?'，这说明单个字符可以匹配，那么此时dp[i + 1][j + 1] = dp[i][j]

• 如果p[i] == '*'，分为两种情况。如果不使用这个*，那么就会从dp[i][j - 1]转移而来；如果使用这个*，那么就会从dp[i - 1][j]转移而来。

• 其他情况都是false

代码：

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

LC10：正则表达式匹配

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

示例 1:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 2:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

思路：

• base case：

  s和p都为空串，肯定匹配；p为空串，s不为空串，肯定不匹配；s为空串，p不为空串，这种情况只有在每一个*消去前一个字符，才能匹配。

• 如果s[i - 1] == p[j - 1] 或者 p[j - 1] == '.'，此时有dp[i][j] = dp[i - 1][j - 1]。

• 如果s[i - 1] 和p[j - 1]是不匹配的，此时要看p[j - 1]是否为*。如果不为*，那么dp[i][j]=false，如果为*，那么还需要继续判断：

  • 让*抵消掉之前的一个字符，即使得之前的字符出现0次，此时有dp[i][j] = dp[i][j - 2]
  • 让*使得之前的字符只出现1次，此时有dp[i][j] = dp[i - 1][j - 2]
  • 让*使得之前的字符只出现2次及以上，此时有dp[i][j] = dp[i - 1][j]
  • 合并为dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
  • 注意：只出现1次，只出现2次及以上，可以合并为dp[i - 1][j]，即只出现1次及以上。

代码：

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

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    if (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                    } else {
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }
}

LC72：编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

动态规划：

dp[i][j] 代表 word1 到 i 位置转换成 word2 到 j 位置需要最少步数

所以，

当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；

当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1

其中，dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。

注意，针对第一行，第一列要单独考虑，我们引入 '' 下图所示：

Snipaste_2019-05-29_15-28-02.png

第一行，是 word1 为空变成 word2 最少步数，就是插入操作

第一列，是 word2 为空，需要的最少步数，就是删除操作

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = i;
        }
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    int temp = Math.min(dp[i - 1][j], dp[i][j - 1]);
                    dp[i][j] = Math.min(temp, dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

矩阵路径问题

剑指offerⅡ98：路径数目

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

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

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

算法：

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        Arrays.fill(dp[0], 1);
        for (int i = 0; i < m; i++) {
            dp[i][0] = 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];
    }
}

**优化空间复杂度Ⅰ：**创建两行的二维数组dp，将f(i,j)保存在dp[i%2][j]中。代码略。

**优化空间复杂度Ⅱ：**在上面的基础上，进一步优化空间复杂度，将两行优化为一行，即一个一维数组解决问题。

class Solution {
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] = dp[j - 1] + dp[j];
            }
        }
        return dp[n - 1];
    }
}

剑指offerⅡ99：最小路径之和

给定一个包含非负整数的 *m* x *n* 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**一个机器人每次只能向下或者向右移动一步。

示例 ：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

**算法：**new一个dp[m][n]，显然空间复杂度不高

优化Ⅰ：创建dp[2][n]，空间效率显著提高

优化Ⅱ：创建dp[n]，在优化Ⅰ的基础上进行优化，与上个题类似

优化Ⅲ算法：不用创建dp，直接在原gird矩阵上操作

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

剑指offerⅡ100：三角形中最小路径之和

给定一个三角形 triangle ，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 ：

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出：11
解释：如下面简图所示：
   2
  3 4
 6 5 7
4 1 8 3
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

**思路：**求出到最后一行所有点的最短路径长度，再在其中选出最短的一个。

算法：

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] dp = new int[n][n];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = triangle.get(i).get(j);
                if (j == 0 && i != 0) {
                    dp[i][j] += dp[i - 1][j];
                } else if (j == i && i != 0) {
                    dp[i][j] += dp[i - 1][j - 1];
                } else {
                    dp[i][j] += Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
                }
            }
        }
        int ans = dp[n - 1][0];
        for (int num : dp[n - 1]) {
            ans = Math.min(ans, num);
        }
        return ans;
    }
}

遇到的问题：没有预先设定dp[0][0]，导致访问dp[i-1][j-1]的时候越界。设定dp[0][0]后，i从1开始；j从0开始，到等于i结束。

优化空间复杂度Ⅰ：创建dp[2][n]，将f(i,j)保存到dp[i%2][j]中，空间效率显著提高

优化空间复杂度Ⅱ：创建dp[1][n]，即dp[n]，但是这个题跟之前的dp[n]不太一样，在于计算完f(i,j)后，覆盖掉f(i-1,j)后，f(i-1,j)还会在计算f(i,j+1)时会用到，所以不能覆盖。但是计算f(i,j)时并不依赖同一行左侧的f(i,j-1)，因此并不一定要按照从左向右的顺序计算，也可以按照从右向左的顺序计算。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        for (List<Integer> row : triangle) {
            for (int j = row.size() - 1; j >= 0; j--) {
                if (j == 0) {
                    dp[j] = dp[j] + row.get(j);
                } else if (j == row.size() - 1) {
                    dp[j] = dp[j - 1] + row.get(j);
                } else {
                    dp[j] = Math.min(dp[j], dp[j - 1]) + row.get(j);
                }
            }
        }
        int ans = dp[0];
        for (int num : dp) {
            ans = Math.min(ans, num);
        }
        return ans;
    }
}

背包问题

剑指offerⅡ101：分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

示例 ：

输入：nums = [1,5,11,5]
输出：true
解释：nums 可以分割成 [1, 5, 5] 和 [11] 。

**思路：**所有数字的和$sum$应该是一个偶数，选出若干个数字，之和为$sum/2$，也可以描述成这个问题：选出若干物品，刚好放慢容量为t的背包，每个物品只能选择一次，所以是一个0-1背包问题。

分析状态转移方程：$f(i,j)$表示能否从前i个物品中选择若干物品放满容量为j的背包。如果总共又$n$个物品，那么$f(n,t)$就是问题的解。

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 == 1) {
            return false;
        }
        return sumsetSum(nums, sum / 2);
    }

    private boolean sumsetSum(int[] nums, int target) {
        //dp[i][j]代表前i个物品，是否刚好能装满容量为j的背包。其中下标0代表没有物品或背包为空。
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        for (int i = 0; i <= nums.length; i++) {
            dp[i][0] = true;//容量为0的背包，不管有多少物品都可以装满
        }
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i - 1][j];//不装
                if (dp[i][j] == false && j >= nums[i - 1]) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];//装
                }
                /**
                 *				  可以替换成下面更容易理解的逻辑
                 *                if(j >= nums[i - 1]){
                 *                     dp[i][j] = dp[i - 1][j - nums[i - 1]] || dp[i - 1][j];
                 *                 }else{
                 *                     dp[i][j] = dp[i - 1][j];
                 *                 } 
                 */
            }
        }
        return dp[nums.length][target];
    }
}

**优化空间效率Ⅰ：**用两行，没什么好说的。

**优化空间效率Ⅱ：**在上一问的基础上，用一行来表示，但dp[i][j]不能直接更新，因为在后面可能还要用到上一行的dp[i - 1][j - nums[i - 1]]，如果提前更新dp[i][j]，那么就会出错。一个办法是从后向前计算。下面只列出核心算法模块：

    private boolean sumsetSum(int[] nums, int target) {
        //dp[i][j]代表前i个物品，是否刚好能装满容量为j的背包。其中下标0代表没有物品或背包为空。
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;//容量为0的背包，不管有多少物品都可以装满
        for (int i = 1; i <= nums.length; i++) {
            for (int j = target; j > 0; j--) {
                if (j >= nums[i - 1]) {
                    dp[j] = dp[j - nums[i - 1]] || dp[j];//能装，要考虑装或不装
                } else {
                    dp[j] = dp[j];//不装该物品
                }
            }
        }
        return dp[target];
    }

剑指offerⅡ102：加减的目标值

给定一个正整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 ：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

**思路：**令p为所有正数之和，q为所有负数之和，那么有$p-q=sum$，$p+q=target$，所以有$2p=sum+target$，最后有$p=\frac{sum+target}{2}$。题目转化为在sums中找到多少组数字，他们的和等于(sum+target)/2，答案即为所求。

$f(i,j)$表示在数组的前i个数字中选出若干数字使得和等于j的方法的数目，$f(n,target)$就是问题的解。

$$f(i,j)=\left\{ \begin{aligned} & 1 & j==0\\ & 0 & i==0 \&\& j>0\\ & f(i-1,j)+f(i-1,j-nums[i]) & i>0\&\&j>nums[i] \end{aligned} \right.$$

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if ((sum + target) % 2 == 1 || sum < target) {
            return 0;
        }
        return subsetSum(nums, (sum + target) / 2);
    }

    private int subsetSum(int[] nums, int target) {
        int[][] dp = new int[nums.length + 1][target + 1];
        for (int i = 0; i <= nums.length; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 0; j <= target; j++) {
                /**
                 * 如果这一串数字中都为正数，那么j从1开始，所有dp[i][0]=1
                 * 如果这一串数字中包含0元素，那么dp[i][0]不能简单地都赋值为1，此时j的遍历要从0开始
                 * */
                if (j >= nums[i - 1]) {
                    /**
                     * 如果存在0元素，那么还需要进入到这个循环，也就是说当背包容量为0时，还可以放下0元素。
                     * 每当遇到一个0元素时，应该还需要判断是否要将其放入，所以就有了下面的表达式
                     * */
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[nums.length][target];
    }
}

**优化空间效率Ⅰ：**用两行，没什么好说的。

**优化空间效率Ⅱ：**在上一问的基础上，用一行来表示，但dp[i][j]不能直接更新，因为在后面可能还要用到上一行的dp[i - 1][j - nums[i - 1]]，如果提前更新dp[i][j]，那么就会出错。一个办法是从后向前计算。下面只列出核心算法模块：

    private int subsetSum(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= nums.length; i++) {
            for (int j = target; j >= 0; j--) {
                if (j >= nums[i - 1]) {
                    dp[j] = dp[j] + dp[j - nums[i - 1]];
                } else {
                    dp[j] = dp[j];
                }
            }
        }
        return dp[target];
    }

剑指offerⅡ103：最少硬币数目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 ：

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

**分析：**这个问题不再是0-1背包问题，而是无界背包问题（也叫完全背包问题）

第一种思路，时间复杂度O(ntk)：$f(i,j)$表示用前i种硬币凑出金额为j的最小硬币数目，当使用0枚标号为$i-1$的硬币时，$f(i,j)=f(i-1,j)$；当使用$k$枚标号为$i-1$的硬币时，$f(i,j)=f(i-1,j-k\times coins[i-1])+k$。由于目标是求出硬币数目的最小值，因此$f(i,j)$是上述所有情况的最小值。该状态转移方程可以用如下等式表示：

$$f(i,j)=min(f(i-1,j-k\times coins[i-1])+k),\text{其中}(k\times coins[i-1]<=j)$$

特别地，当j=0时，f(i,0)=0；当i=0, j>0时，即用0枚硬币凑出来大于0的金额，这显然不可能，用一个特殊值表示。

空间复杂度O()的算法(5%,5%)：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int coinsNum = coins.length;
        int[][] dp = new int[coinsNum + 1][amount + 1];
        for (int i = 0; i <= coinsNum; i++) {
            Arrays.fill(dp[i], amount + 1);
            dp[i][0] = 0;
        }
        for (int i = 1; i < coinsNum + 1; i++) {
            for (int j = 1; j < amount + 1; j++) {
                dp[i][j] = dp[i-1][j];//第i个硬币一个都放不进去
                for (int k = 1; k * coins[i - 1] <= j; k++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * coins[i - 1]] + k);
                }
            }
        }
        return dp[coinsNum][amount] > amount ? -1 : dp[coinsNum][amount];
    }
}

优化空间复杂度的算法：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int coinsNum = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i < coinsNum + 1; i++) {
            for (int j = amount; j >= 1; j--) {
                for (int k = 1; k * coins[i - 1] <= j; k++) {
                    dp[j] = Math.min(dp[j], dp[j - k * coins[i - 1]] + k);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

第二种思路，该思路更好，时间复杂度O(nt)：

用函数$f(i)$表示凑出总额为i的硬币需要的最少数目。

采用自下而上的方式思考，假设在计算$f(i)$之前，已经计算出来了$f(0)$至$f(i-1)$的答案，则$f(i)$的转移方程为：

$$f(i) = min\{f(i-coins[j])+1\}$$

class Solution {
    public int coinChange(int[] coins, int amount) {
        int coinsNum = coins.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

剑指offerⅡ104：排列的数目

给定一个由 不同 正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

**思路：**和面试题103类似，前者是求最小，该题是求和。

算法：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int j = 1; j <= target; j++) {
            for (int num : nums) {
                if (j >= num)
                    dp[j] += dp[j - num];
            }
        }
        return dp[target];
    }
}

股票买卖问题

LC121：买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 ：

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

方法一：动态规划：

dp[i] 表示前 i 天的最大利润，因为我们始终要使利润最大化，则：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }
        int[] dp = new int[n];
        int minPrice = prices[0];
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            dp[i] = Math.max(dp[i - 1], prices[i] - minPrice);
        }
        return dp[n - 1];
    }
}

方法二：一次遍历（优化的动态规划）

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }
        int minPrice = prices[0];
        int maxProfit = Integer.MIN_VALUE;
        for (int i = 1; i < n; i++) {
            minPrice = Math.min(minPrice, prices[i]);
            maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        }
        return maxProfit;
    }
}

LC122：买卖股票的最佳时机Ⅱ

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 ：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

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

LC123：买卖股票的最佳时机Ⅲ

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

一天结束时，可能有持股、可能未持股、可能卖出过1次、可能卖出过2次、也可能未卖出过。

所以定义状态转移数组dp[天数][当前是否持股][卖出的次数]为当前股民手中持有的钱（不包含股市中的钱）。

具体一天结束时的6种状态：

1. 未持股，未卖出过股票：说明从未进行过买卖，利润为0

   dp[i][0][0] = 0

2. 未持股，卖出过1次股票：可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）

   dp[i][0][1]=max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1])

3. 未持股，卖出过2次股票:可能是今天卖出，也可能是之前卖的（昨天也未持股且卖出过）

   dp[i][0][2]=max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][2])

4. 持股，未卖出过股票：可能是今天买的，也可能是之前买的（昨天也持股）

   dp[i][1][0]=max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0])

5. 持股，卖出过1次股票：可能是今天买的，也可能是之前买的（昨天也持股）

   dp[i][1][1]=max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1])

6. 持股，卖出过2次股票：最多交易2次，这种情况不存在

   dp[i][1][2] = Integer.MIN_VALUE

根据这些状态即可轻松写出代码：

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        if (n < 2) {
            return 0;
        }
        int[][][] dp = new int[n][2][3];
        dp[0][0][0] = 0;
        dp[0][1][0] = -prices[0];
        dp[0][0][1] = Integer.MIN_VALUE / 2;
        dp[0][0][2] = Integer.MIN_VALUE / 2;
        dp[0][1][1] = Integer.MIN_VALUE / 2;
        dp[0][1][2] = Integer.MIN_VALUE / 2;
        for (int i = 1; i < n; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = Math.max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1]);
            dp[i][0][2] = Math.max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][2]);
            dp[i][1][0] = Math.max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0]);
            dp[i][1][1] = Math.max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1]);
            //dp[i][1][2] = Integer.MIN_VALUE / 2;
        }
        return Math.max(Math.max(dp[n - 1][0][1], dp[n - 1][0][2]), 0);
    }
}

LC188：买卖股票的最佳时机Ⅳ

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

解析：

如果k > length / 2，说明买卖无次数限制，因为一次买卖需要2天。

定义状态转移数组dp[天数][卖出的次数][当前是否持股]为当前股民手中持有的钱（不包含股市中的钱）。

方法一：动态规划

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (k == 0 || n < 2) {
            return 0;
        }
        if (k >= n / 2) {
            return noKRestrict(prices);
        }
        int[][][] dp = new int[n + 1][k + 1][2];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][1] = Integer.MIN_VALUE;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                dp[i + 1][j + 1][1] = Math.max(dp[i][j][0] - prices[i], dp[i][j + 1][1]);
                dp[i + 1][j + 1][0] = Math.max(dp[i][j + 1][1] + prices[i], dp[i][j + 1][0]);
            }
        }
        return dp[n][k][0];
    }

    private int noKRestrict(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            int temp = prices[i] - prices[i - 1];
            if (temp > 0) {
                profit += temp;
            }
        }
        return profit;
    }
}

方法二：空间优化的动态规划