动态规划 - 简书

总结：https://labuladong.gitbook.io/algo/

最长回文子串

https://leetcode-cn.com/problems/longest-palindromic-substring/

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"

动态规划解法
我们用 P(i,j) 表示字符串 s 的第 i 到 j 个字母组成的串是否为回文串；那么我们就可以写出动态规划的状态转移方程：

也就是说，只有 s[i+1:j-1]是回文串，并且 s 的第 i 和 j 个字母相同时，s[i:j] 才会是回文串。

上文的所有讨论是建立在子串长度大于 2 的前提之上的，我们还需要考虑动态规划中的边界条件，即子串的长度为 1或 2。对于长度为 1 的子串，它显然是个回文串；对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。因此我们就可以写出动态规划的边界条件：

根据这个思路，我们就可以完成动态规划了，最终的答案即为所有 P(i,j)=true 中 j−i+1（即子串长度）的最大值。

注意：在状态转移方程中，我们是从长度较短的字符串向长度较长的字符串进行转移的，因此一定要注意动态规划的循环顺序。程序中我们使用d表示子字符串的长度，作为第一层循环的变量，从小到大逐渐增加；

public static String longestPalindrome(String s) {

        int n = s.length();
        boolean[][] P = new boolean[n][n];

        if (n <= 1) {
            return s;
        }

        int maxLen = 1;
        String maxStr = s.substring(0, 1);

        // 初始化(边界条件)
        for (int i = 0; i < n; i++) {
            P[i][i] = true;
            if (i < n - 1) {
                P[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
                if (P[i][i + 1]) {
                    maxLen = 2;
                    maxStr = s.substring(i, i + 2);
                }
            }
        }

        // 动态规划
        for (int d = 2; d <= n - 1; d++) {
            for (int L = 0; L < n - d; L++) {
                int R = L + d;
                P[L][R] = P[L + 1][R - 1] & (s.charAt(L) == s.charAt(R));
                if (P[L][R]) {
                    int len = R - L + 1;
                    if (len > maxLen) {
                        maxStr = s.substring(L, R + 1);
                        maxLen = len;
                    }
                }
            }
        }

        return maxStr;
    }

中心扩散法
遍历所有可能出现的回文子串的“中心位置”，从“中心位置”尝试尽可能扩散出去，得到一个回文串。

枚举“中心位置”时间复杂度为 O(N)，从“中心位置”扩散得到“回文子串”的时间复杂度为 O(N)，因此时间复杂度为 $O(N^2)$ 。

在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。

奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。

 public static String longestPalindrome(String s) {

        if (s.length() <= 1) {
            return s;
        }

        int maxLen = 1;
        String maxStr = s.substring(0, 1);

        for (int i = 0; i < s.length(); i++) {
            String s1 = expand(s, i, i);// aba
            String s2 = expand(s, i, i + 1);// abba
            String maxLenStr = s1.length() > s2.length() ? s1 : s2;
            if (maxLenStr.length() > maxLen) {
                maxLen = maxLenStr.length();
                maxStr = maxLenStr;
            }
        }

        return maxStr;
    }

    public static String expand(String s, int L, int R) {
        int n = s.length();
        while (L >= 0 && L < n && R >= 0 && R < n && s.charAt(L) == s.charAt(R)) {
            L--;
            R++;
        }
        return s.substring(L+1, R);
    }

马拉车算法（Malacher，中心扩散算法的改进版）

     public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        // 得到预处理字符串
        String newString = preProcess(s);
        int newLen = newString.length();

        int[] armLen = new int[newLen]; // 记录已经计算过的回文子串半径长度信息
        int maxRight = 0; // 它是遍历过的 i 的 i + armLen[i] 的最大者
        int maxCenter = 0; // 它是遍历过的 i 的 i + armLen[i] 的最大者 对应的 i

        int oriMaxLen = 1; // 原始字符串的最长回文子串的长度
        int oriMaxStart = 0; // 原始字符串的最长回文子串的起始位置

        for (int i = 0; i < newLen; i++) {
            int offset = 0;
            if (i < maxRight) {
                int mirror = 2 * maxCenter - i;
                offset = Math.min(maxRight - i, armLen[mirror]); // 马拉车算法的关键, 即每次扩散时不再从center开始, 而是从center +/- armLen开始
            }
            // 每次扩散时不再从center开始, 而是从center +/- armLen开始
            armLen[i] = expand(newString, i, offset);

            // 更新maxRight以便最大限度利用已经计算过的回文长度信息
            if (i + armLen[i] > maxRight) {
                maxRight = i + armLen[i];
                maxCenter = i;
            }

            // 更新原始字符串的最长回文信息
            if (armLen[i] > oriMaxLen) {
                oriMaxLen = armLen[i];
                oriMaxStart = (i - oriMaxLen) / 2;
            }
        }
        return s.substring(oriMaxStart, oriMaxStart + oriMaxLen);
    }

    private int expand(String s, int center, int offSet) {
        int len = s.length();
        int i = center - (1 + offSet);
        int j = center + (1 + offSet);
        int armLen = offSet;
        while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
            armLen++;
        }
        return armLen;
    }

    private String preProcess(String s){
        StringBuilder newSB = new StringBuilder("#");
        for(char c : s.toCharArray()){
            newSB.append(c).append('#');
        }
        return newSB.toString();
    }

回文子串（求个数）

动态规划

    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];
        int count = 0;
        for (int d = 0; d < n; d++) {
            for (int L = 0; L < n - d; L++) {
                if (d == 0) {
                    dp[L][L] = true;
                    count++;
                    continue;
                }
                if (d == 1) {
                    dp[L][L + 1] = s.charAt(L) == s.charAt(L + 1);
                    count += dp[L][L + 1] ? 1 : 0;
                    continue;
                }
                int R = L + d;
                dp[L][R] = dp[L + 1][R - 1] & s.charAt(L) == s.charAt(R);
                count += dp[L][R] ? 1 : 0;
            }
        }
        return count;
    }

马拉车算法（Malacher算法，中心扩散算法的改进版）

public int countSubstrings(String s) {
        if (s.length() <= 1) {
            return 1;
        }

        int count = 0;

        String newString = preProcess(s); // 得到预处理字符串
        int newLen = newString.length();

        int[] armLen = new int[newLen]; // 记录已经计算过的回文子串半径长度信息
        int maxRight = 0; // 它是遍历过的 i 的 i + armLen[i] 的最大者
        int maxCenter = 0; // 它是遍历过的 i 的 i + armLen[i] 的最大者 对应的 i

        for (int i = 0; i < newLen; i++) {
            int offset = 0;
            if (i < maxRight) {
                int mirror = 2 * maxCenter - i;
                offset = Math.min(maxRight - i, armLen[mirror]); // 马拉车算法的关键, 即每次扩散时不再从center开始, 而是从center +/- armLen开始
            }

            armLen[i] = expand(newString, i, offset); // 每次扩散时不再从center开始, 而是从center +/- armLen开始
            count += (armLen[i] + 1) / 2; // 记录数量: +1是因为本身也算回文字符串, /2是因为增加的字符不能算在原始字符之中

            // 更新maxRight以便最大限度利用已经计算过的回文长度信息
            if (i + armLen[i] > maxRight) {
                maxRight = i + armLen[i];
                maxCenter = i;
            }

        }
        return count;
    }

    private int expand(String s, int center, int offSet) {
        int len = s.length();
        int i = center - (1 + offSet);
        int j = center + (1 + offSet);
        int armLen = offSet;
        while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {
            i--;
            j++;
            armLen++;
        }
        return armLen;
    }

    private String preProcess(String s){
        StringBuilder newSB = new StringBuilder("#");
        for(char c : s.toCharArray()){
            newSB.append(c).append('#');
        }
        return newSB.toString();
    }

最长回文子序列

状态
f[i][j] 表示 s 的第 i 个字符到第 j 个字符组成的子串中，最长的回文序列长度是多少。
转移方程
如果 s 的第 i 个字符和第 j 个字符相同的话
$f[i][j] = f[i + 1][j - 1] + 2$
如果 s 的第 i 个字符和第 j 个字符不同的话
$f[i][j] = max(f[i + 1][j], f[i][j - 1])$
遍历变量（或者说遍历顺序），为了保证每个子问题一定是计算好的，我们将第一维变量设置为i和j的距离，这样就能保证子问题一定是计算好的。
初始化
f[i][i] = 1 单个字符的最长回文序列是 1
结果
f[0][n - 1]

    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int d = 0; d < n; d++) {
            for (int left = 0; left < n - d; left++) {
                if (d == 0) {
                    dp[left][left] = 1;
                    continue;
                }
                int right = left + d;
                if (s.charAt(left) == s.charAt(right)) {
                    dp[left][right] = dp[left + 1][right - 1] + 2;
                } else {
                    dp[left][right] = Math.max(dp[left + 1][right], dp[left][right - 1]);
                }
            }
        }
        return dp[0][n-1];
    }

动态规划
最长公共子序列（Longest Common Subsequence，简称 LCS）是一道非常经典的面试题目，因为它的解法是典型的二维动态规划，大部分比较困难的字符串问题都和这个问题一个套路，比如说编辑距离。而且，这个算法稍加改造就可以用于解决其他问题，所以说 LCS 算法是必须掌握的。
1）定义状态变量dp[i][j]，表示字符串（0-i）和字符串（0-j）的LCS的长度，这里的i和j是各自字符串的最后一个字符下标。
2）确定状态转移方程：所谓确定状态转移方程，可以理解成求解dp[i][j]，可以利用dp[<=i][<=j]的一切子问题的答案。
如果某个字符应该在 LCS 中，那么这个字符肯定同时存在于 s1 和 s2 中，因为LCS 是最长公共子序列。此时我们会联想到比对s1.charAt[i] == s2.chatAt[j]。
如果s1.charAt[i] == s2.chatAt[j]的情况下，dp[i][j]如何求？此时要利用dp[i][j]的定义，表示字符串（0-i）和字符串（0-j）的LCS的长度，此处i和j均为字符串的末尾，那么此字符必定在字符串（0-i）和字符串（0-j）的LCS中，所以有：dp[i][j] = dp[i-1][j-1] + 1；
如果s1.charAt[i] != s2.chatAt[j]的情况下，dp[i][j]如何求？那么这两个字符中至少有一个不在LCS中，所以有：dp[i][j] =Math.max(dp[i-1][j]，dp[i][j-1])；
3）边界条件，字符串的下标可以从1开始，这样就避免的边界条件的额外赋值。

public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

两个字符串的删除操作

动态规划
此题同上面的最长子序列问题

    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if (len1 == 0) {
            return len2;
        }
        if (len2 == 0) {
            return len1;
        }
        int[][] dp = new int[len1 + 1][len2 + 1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return len1 + len2 - 2 * dp[len1][len2];
    }

最长重复子数组

动态规划

    public int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m == 0 || n == 0) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1]; // dp[i][j]表示以A[i-1],B[j-1]为结尾元素的最长公共子数组长度
        int maxComLen = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxComLen = Math.max(maxComLen, dp[i][j]);
                }
            }
        }
        return maxComLen;
    }

空间优化

dp[i][j]只与dp[i-1][j-1]的值有关；所以可以降维；
二维数组降成一维数组，一般将row变量取消；前提是row只与row-1状态有关（最多row-2）；所以dp[i][j]降成dp[j]，则状态方程变为dp[j] = dp[j-1] + 1；
要保证dp[j-1]维持上一轮的值，这里有两种方法可以实现：一般来说直接用一个变量保存上一轮的值即可；另一种方法是内循环倒序；
另外注意一点，上面的二维数组的赋零操作省略了，因为初始化的值就是零；但是在一维数组中，赋零操作就是必要的，去改变上一轮的值。

    public int findLength(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m == 0 || n == 0) {
            return 0;
        }
        int[] dp = new int[n + 1];
        int maxComLen = 0;
        for (int i = 1; i <= m; i++) {
            int prev = 0; // dp[i-1][j-1]
            for (int j = 1; j <= n; j++) {
                int temp = dp[j];
                if (A[i - 1] == B[j - 1]) {
                    dp[j] = prev + 1; 
                }else {
                    dp[j] = 0;
                }
                maxComLen = Math.max(maxComLen, dp[j]);
                prev = temp; // 保存上一轮的值
            }
        }
        return maxComLen;
    }

滑动窗口
由于此题是连续子数组，所以可用滑动窗口解决。

最长上升子序列(https://leetcode-cn.com/problems/longest-increasing-subsequence/)

给定一个无序的整数数组，找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
说明:
可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
你算法的时间复杂度应该为 O(n2) 。

进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?

动态规划
定义 dp[i]为考虑前 i 个元素，以第 i个数字结尾的最长上升子序列的长度，注意nums[i] 必须被选取。

我们从小到大计算 dp[]数组的值，在计算 dp[i]之前，我们已经计算出dp[0…i−1] 的值，则状态转移方程为：

即考虑往 dp[0…i−1] 中最长的上升子序列后面再加一个 nums[i]。由于 dp[j] 代表 nums[0…j] nums[j] 结尾的最长上升子序列，所以如果能从 dp[j]这个状态转移过来，那么 nums[i] 必然要大于nums[j]，才能将 nums[i] 放在 nums[j] 后面以形成更长的上升子序列。
最后，整个数组的最长上升子序列即所有 dp[i] 中的最大值。

总结：最后的求解值，未必一定是dp数组中的某个值，而是通过简单的遍历可以从dp数组中获取到。

public static int lengthOfLIS(int[] nums) {

        if (nums.length <= 1) {
            return nums.length;
        }
        int[] dp = new int[nums.length];
        // 初始化
        dp[0] = 1;
        // 规划
        for (int tail = 1; tail < nums.length; tail++) {
            int max = 0;
            for (int i = 0; i < tail; i++) {
                if (nums[tail] > nums[i]) {
                    max = Math.max(max, dp[i]);
                }
            }
            dp[tail] = max + 1;
        }
        // 输出dp数组中最大的即可
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            max = Math.max(max, dp[i]);
        }
        return max;
    }

贪心+二分法
对于此题的进阶，一旦出现logn的时间复杂度，往往可以联想到二分法。
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d[i]，表示长度为 i 的最长上升子序列的末尾元素的最小值（已知元素），用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。

同时我们可以注意到 d[i]是关于 i 单调递增的。

我们依次遍历数组nums[] 中的每个元素，并更新数组 d[] 和 len 的值。如果nums[i]>d[len] 则更新 len=len+1，否则在d[1…len]中找满足d[i−1]<nums[j]<d[i] 的下标 i，并更新 d[i]=nums[j]。

根据 d 数组的单调性，我们可以使用二分查找寻找下标 i，优化时间复杂度。

public static int lengthOfLIS2(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int len = 1;
        int[] minTail = new int[nums.length+1];
        minTail[len] = nums[0];

        for (int i = 1; i < nums.length; i++) {
            if (len < nums.length && nums[i] > minTail[len]) {
                len += 1;
                minTail[len] = nums[i];
            } else {
                int l = 1;
                int r = len;
                while (l <= r) {
                    int m = l + (r - l) / 2;
                    if (minTail[m] < nums[i]) {
                        l = m + 1;
                    } else {
                        r = m - 1;
                    }
                }
                minTail[l] = nums[i];
            }
        }

        return len;
    }

最长递增子序列的个数

动态规划

本题在"求解最长递增子序列的长度"的基础上，多维持一个记录最长子序列的个数的数组。

        int[] dp = new int[nums.length]; // dp[i]表示以nums[i]结尾的最长子序列的长度
        int[] count = new int[nums.length]; // count[i]表示以nums[i]结尾的最长子序列的个数

代码如下

    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        int[] dp = new int[nums.length]; // dp[i]表示以nums[i]结尾的最长子序列的长度
        int[] count = new int[nums.length]; // count[i]表示以nums[i]结尾的最长子序列的个数
        // 初始化
        dp[0] = 1;
        count[0] = 1;
        // 规划
        for (int tail = 1; tail < nums.length; tail++) {
            int max = 0;
            int cnt = 1;
            for (int i = 0; i < tail; i++) {
                if (nums[tail] > nums[i]) {
                    if(dp[i] > max){
                        max = dp[i];
                        cnt = count[i];
                    }else if(dp[i] == max){
                        cnt += count[i];
                    }
                }
            }
            dp[tail] = max + 1;
            count[tail] = cnt;
        }
        // dp数组的最大者为最长子序列的长度
        int maxLen = 1;
        for (int i = 0; i < nums.length; i++) {
            maxLen = Math.max(maxLen, dp[i]);
        }
        // 遍历count数组
        int countOfLIS = 0;
        for(int i = 0; i < nums.length; i++){
            if(dp[i] == maxLen){
                countOfLIS += count[i];
            }
        }
        return countOfLIS;
    }

最小路径和(https://leetcode-cn.com/problems/minimum-path-sum/)

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

二维动态规划
复杂度分析
时间复杂度：O(mn)。遍历整个矩阵恰好一次。
空间复杂度：O(mn)。使用额外的一个同大小矩阵。O(1)，直接使用原始的grid矩阵即可

public static int minPathSum(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        int[][] minPath = new int[m][n];

        // 初始化
        minPath[0][0] = grid[0][0];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    minPath[i][j] = Math.min(minPath[i - 1][j], minPath[i][j - 1]) + grid[i][j];
                } else if (i == 0 && j > 0) {
                    minPath[i][j] = minPath[i][j - 1] + grid[i][j];
                } else if (j == 0 && i > 0) {
                    minPath[i][j] = minPath[i - 1][j] + grid[i][j];
                }
            }
        }

        return minPath[m - 1][n - 1];
    }

    public static int minPathSum2(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
                } else if (i == 0 && j > 0) {
                    grid[i][j] = grid[i][j - 1] + grid[i][j];
                } else if (j == 0 && i > 0) {
                    grid[i][j] = grid[i - 1][j] + grid[i][j];
                }
            }
        }

        return grid[m - 1][n - 1];
    }

一维动态规划
逐行计算，计算下一行时利用上一行的结果，并覆盖之；

public static int minPathSum(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;

        int[] minPath = new int[n];

        // 初始化
        minPath[0] = grid[0][0];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    minPath[j] = Math.min(minPath[j], minPath[j - 1]) + grid[i][j];
                } else if (i == 0 && j > 0) {
                    minPath[j] = minPath[j - 1] + grid[i][j];
                } else if (i > 0 && j == 0) {
                    minPath[j] = minPath[j] + grid[i][j];
                }
            }
        }

        return minPath[n - 1];
    }

背包问题的动态规划解法--归纳与总结

背包问题的判定

背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。

常见背包问题

分为三类：

排列组合问题：
组合总和 Ⅳ(https://leetcode-cn.com/problems/combination-sum-iv/)（排列问题）
目标和(https://leetcode-cn.com/problems/target-sum/)（排列问题）
零钱兑换 II(https://leetcode-cn.com/problems/coin-change-2/)（组合问题）
状态转移公式：dp[i] = dp[i-num]
True、False问题
单词拆分(https://leetcode-cn.com/problems/word-break/)
分割等和子集(https://leetcode-cn.com/problems/partition-equal-subset-sum/)
状态转移公式：dp[i] = dp[i] or dp[i-num]
最大最小问题
一和零(https://leetcode-cn.com/problems/ones-and-zeroes/)
零钱兑换(https://leetcode-cn.com/problems/coin-change/)
状态转移公式：max(dp[i], dp[i-num]+1) 或者 dp[i] = min(dp[i], dp[i-num]+1)

对于状态转移公式的说明：
这里的状态转移公式只给出一个规划变量，即输出变量target；有些问题是一维规划问题，使用这一个规划变量即可；有些问题是二维规划问题，还需要添加其他规划变量，比如数组的范围下标（前多少个元素）。对于target这个规划变量，其取值范围值得关注，比如负值是否有意义，该怎么处理；是否截止到所求值即可；

组合总和 Ⅳ(https://leetcode-cn.com/problems/combination-sum-iv/)

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
示例:
nums = [1, 2, 3]
target = 4
所有可能的组合为（这里其实是排列问题）：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。
进阶：
如果给定的数组中含有负数会怎么样？
问题会产生什么变化？
我们需要在题目中添加什么限制来允许负数的出现？

动态规划
考虑到这里顺序不同的序列被视作不同的组合（即组合问题，这是和零钱兑换问题不同的地方），所以按照下面的方法进行动态规划：
定义状态dp[i]为总和为i的所有可能的组合数。那么将所有组合按照最后一个数字进行分类，就可以得到状态转移方程了：
$dp[i]=\sum_{j=0}^{n-1}dp[i-nums[j]]$

public static int combinationSum4(int[] nums, int target) {

        int[] dp = new int[target + 1];

        // 初始化
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (i - num >= 0) {
                    dp[i] += dp[i - num];
                }
            }
        }

        return dp[target];
    }

目标和(https://leetcode-cn.com/problems/target-sum/)

给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
示例 1:
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释:
-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
一共有5种方法让最终目标和为3。
注意:
数组非空，且长度不会超过20。
初始的数组的和不会超过1000。
保证返回的最终结果能被32位整数存下。

二维动态规划
这道题也是一个常见的背包问题，我们可以用类似求解背包问题的方法来求出可能的方法数。

我们用 dp[i][j] 表示用数组中的前 i 个元素，组成和为 j 的方案数。考虑第 i 个数 nums[i]，它可以被添加 + 或 -，因此状态转移方程如下：
dp[i][j] = dp[i - 1][j - nums[i]] + dp[i - 1][j + nums[i]]

这里j为和，所以j的取值范围为-sum~sum，而由于数组下标不能为负，所以对j可以进行位移（用j+sum代替j），于是状态转移方程转变为：
dp[i][j+sum] = dp[i - 1][j + sum - nums[i]] + dp[i - 1][j + sum + nums[i]]

public static int findTargetSumWays(int[] nums, int S) {

        // 目标数的取值范围: -sum ~ sum
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 考虑数组下标不能小于0, 将每个目标数加sum, 于是目标数的取值范围 0 ~ 2*sum
        int n = nums.length;
        int t = 2 * sum + 1;
        int[][] dp = new int[n][t];

        // 初始化(需要考虑0的情形)
        if(nums[0] != 0){
            dp[0][-nums[0] + sum] = 1;
            dp[0][nums[0] + sum]  = 1;
        }else {
            dp[0][sum] = 2;
        }


        for (int i = 1; i < n; i++) {
            for (int j = -sum; j <= sum; j++) {
                if (j + sum - nums[i] >= 0) {
                    dp[i][j + sum] += dp[i - 1][j + sum - nums[i]];
                }
                if (j + sum + nums[i] < t) {
                    dp[i][j + sum] += dp[i - 1][j + sum + nums[i]];
                }
            }
        }

        return S > sum ? 0 : dp[n - 1][S + sum];
    }

零钱兑换 II(https://leetcode-cn.com/problems/coin-change-2/)

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1

注意:
你可以假设：
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数

动态规划
二维的动态规划如下：

public static int change(int amount, int[] coins) {

        if (coins.length == 0) {
            return amount == 0 ? 1 : 0;
        }

        int[][] dp = new int[coins.length][amount + 1];

        // 边界条件
        for (int j = 0; j <= amount; j++) {
            dp[0][j] = j % coins[0] == 0 ? 1 : 0;
        }

        for (int i = 1; i < coins.length; i++) {
            for (int j = 0; j <= amount; j++) {
                if (j - coins[i] >= 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[coins.length - 1][amount];
    }

空间优化之后如下：

public static int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        // 初始化
        dp[0] = 1;

        // 动态规划
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        
        return dp[amount];
    }

另一种二维的动态规划如下（空间优化之后不通过）:

    public static int change(int amount, int[] coins) {

        if (coins.length == 0) {
            return amount == 0 ? 1 : 0;
        }

        int[][] dp = new int[amount + 1][coins.length];

        // 边界条件
        for (int j = 0; j < coins.length; j++) {
            dp[0][j] = 1;
        }
        for (int i = 0; i <= amount; i++) {
            dp[i][0] = i % coins[0] == 0 ? 1 : 0;
        }

        for (int i = 1; i <= amount; i++) {
            for (int j = 1; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    dp[i][j] = dp[i][j - 1] + dp[i - coins[j]][j];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[amount][coins.length - 1];
    }

单词拆分(https://leetcode-cn.com/problems/word-break/)

给定一个非空字符串 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

动态规划
这个方法的想法是对于给定的字符串（s）可以被拆分成子问题 s1 和 s2 。如果这些子问题都可以独立地被拆分成符合要求的子问题，那么整个问题 s 也可以满足。也就是，如果 "catsanddog" 可以拆分成两个子字符串 "catsand" 和 "dog" 。子问题 "catsand" 可以进一步拆分成 "cats" 和 "and" ，这两个独立的部分都是字典的一部分，所以 "catsand" 满足题意条件，再往前， "catsand" 和 "dog" 也分别满足条件，所以整个字符串 "catsanddog" 也满足条件。

public static boolean wordBreak3(String s, List<String> wordDict) {
        int n = s.length();

        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;

        for(int end = 1; end <= s.length(); end++){
            for(int start = 0; start < end; start++){
                if(dp[start] && wordDict.contains(s.substring(start, end))){
                    dp[end] = true;
                    break;
                }
            }
        }

        return dp[s.length()];
    }

分割等和子集(https://leetcode-cn.com/problems/partition-equal-subset-sum/)

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

动态规划
做这道题需要做这样一个等价转换：是否可以从这个数组中挑选出一些正整数，使得这些数的和等于整个数组元素的和的一半。
即将此问题转化为0-1背包问题：背包容量为sum/2 ，物品为题意给出的数组，问能否取出一次物品恰好装满背包。

public static boolean canPartition(int[] nums) {

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 2 != 0) {
            return false;
        }

        int target = sum / 2;

        boolean[][] dp = new boolean[nums.length][target + 1];

        // 边界计算
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        for (int j = 1; j <= target; j++) {
            dp[0][j] = nums[0] == j;
        }

        for (int i = 1; i < nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (j - nums[i] >= 0) {
                    dp[i][j] = dp[i - 1][j - nums[i]] | dp[i - 1][j];
                }
            }
            if (dp[i][target] == true) {
                return true;
            }
        }

        return false;
    }

一和零(https://leetcode-cn.com/problems/ones-and-zeroes/)

在计算机界中，我们总是追求用有限的资源获取最大的收益。
现在，假设你分别支配着 m 个 0 和 n 个 1。另外，还有一个仅包含 0 和 1 字符串的数组。
你的任务是使用给定的 m 个 0 和 n 个 1 ，找到能拼出存在于数组中的字符串的最大数量。每个 0 和 1 至多被使用一次。
注意:
给定 0 和 1 的数量都不会超过 100。
给定字符串数组的长度不会超过 600。
示例 1:
输入: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
输出: 4
解释: 总共 4 个字符串可以通过 5 个 0 和 3 个 1 拼出，即 "10","0001","1","0" 。
示例 2:
输入: Array = {"10", "0", "1"}, m = 1, n = 1
输出: 2
解释: 你可以拼出 "10"，但之后就没有剩余数字了。更好的选择是拼出 "0" 和 "1" 。

思路：把总共的 0 个 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成。这里的目标值是能放进背包的字符串的数量。

第 1 步：定义状态
依然是尝试「题目问啥，就把啥定义成状态」。
dp[k][i][j] 表示输入字符串在能够使用 i 个 0 和 j 个 1 的情况下，能够容纳前k个字符串的最大数量。

第 2 步：状态转移方程
dp[k][i][j] = Math.max(dp[k - 1][i][j], dp[k - 1][i - c0][j - c1] + 1)
c0:当前字符串（即第k个字符串）使用0的个数;
c1:当前字符串（即第k个字符串）使用1的个数；

第 3 步：初始化
为了避免分类讨论，通常多设置一行。这里可以认为，第 0 个字符串是空串。第 0 行默认初始化为 0。
若不增加空串，则需要单独为k=0的情况赋值；

第 4 步：输出
输出是最后一个状态，即：dp[len][m][n]。

    // 增加空串避免初始化赋值
    public static int findMaxForm(String[] strs, int m, int n) {
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];

        // 动态规划
        for (int k = 1; k <= strs.length; k++) {

            int[] res = find(strs[k - 1]);
            int c0 = res[0];
            int c1 = res[1];

            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    if (i >= c0 && j >= c1) {
                        dp[k][i][j] = Math.max(dp[k - 1][i][j], dp[k - 1][i - c0][j - c1] + 1);
                    } else {
                        dp[k][i][j] = dp[k - 1][i][j];
                    }
                }
            }
        }

        return dp[strs.length][m][n];
    }
    
    public static int[] find(String s) {
        int[] c = new int[2];
        for (int i = 0; i < s.length(); i++) {
            c[s.charAt(i)-'0']++;
        }
        return c;
    }

考虑空间优化：
因为当前行只参考了上一行的值，因此可以使用「滚动数组」或者「从后向前赋值」的方法优化空间。这里采用「从后向前赋值」的方法。
1）优化空间只是将dp降维，实际的for循环仍然是三层；
2）dp降维后为什么里循环要从后向前赋值：为了使得上一次循环的结果不被下一次循环的结果覆盖掉，需要从后向前赋值。
举例说明：假设d[3][3] = d[1][1] + 1，实际想要得到的效果是当前循环的d[3][3]应该利用到上一次循环的d[1][1]结果；如果i和j从小到大赋值，会先将d[1][1]的值覆盖住，导致上一轮的结果还没有被利用到就已经没了。

 public static int findMaxForm3(String[] strs, int m, int n) {

        int[][] dp = new int[m + 1][n + 1];

        // 动态规划
        for (String str : strs) {

            int[] res = find(str);
            int c0 = res[0];
            int c1 = res[1];

            for (int i = m; i >=0; i--) {
                for (int j = n; j >= 0; j--) {
                    if (i >= c0 && j >= c1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - c0][j - c1] + 1);
                    }
                }
            }
        }

        return dp[m][n];
    }

零钱兑换(https://leetcode-cn.com/problems/coin-change/)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

动态规划解法
1）首先按照套路，题目问什么，就把什么当做状态变量
2）本题有两个状态变量，一个是coins索引，一个是总金额amount；不妨进行二维动态规划，但是哪一个变量放在外循环，哪一个变量放在内循环，是需要重点解决的问题：
如果把coins的索引放在外层，总金额放在内层，那么求解当前问题dp[coin][amount]时，并不能利用任何dp[*][amount-1]子问题的解；
如果把总金额放在外层，把coins的索引放在内层，那么求解当前问题dp[amount][coin_ind]，可以利用dp[amount][coin_ind-1]这一子问题的解：
dp[amount][coin_ind] = min(dp[amount][coin_ind-1], dp[amount-coin_val][coin_ind]+1);
3)考虑到本题求解的是最小值，所以初始化时，不能默认初始化为0，需要设置为无穷大，或者已知的不可能达到的大值。

public static int coinChange(int[] coins, int amount) {

        int MAX = amount + 1;

        int[][] dp = new int[amount + 1][coins.length];

        // 初始化
        for (int i = 0; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i == 0) {
                    dp[i][j] = 0;
                } else if (j == 0 && i % coins[j] == 0) {
                    dp[i][j] = i / coins[j];
                } else {
                    dp[i][j] = MAX;
                }
            }
        }

        for (int i = 1; i <= amount; i++) {
            for (int j = 1; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    dp[i][j] = Math.min(dp[i][j - 1], dp[i - coins[j]][j] + 1);
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[amount][coins.length - 1] == MAX ? -1 : dp[amount][coins.length - 1];
    }

空间优化
观察状态转移语句：

dp[i][j] = Math.min(dp[i][j - 1], dp[i - coins[j]][j] + 1);

dp[*][j] 的值只可能依赖于dp[*][j - 1]或者dp[*][j] 的值，所以可以去掉[j]。同时，初始条件也会简化。

 public static int coinChange(int[] coins, int amount) {
        int MAX = amount + 1;
        int[] dp = new int[amount + 1];
        // 初始化
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            dp[i] = MAX;
        }

        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i - coins[j] >= 0) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] == MAX ? -1 : dp[amount];
    }

不同路径(https://leetcode-cn.com/problems/unique-paths/)

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

示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。

向右 -> 向右 -> 向下
向右 -> 向下 -> 向右
向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9

二维动态规划
到达[i,j]的路径只可能有两类情况：从[i-1,j]往下走或者从[i.j-1]往右走；

public static int uniquePath(int m, int n) {

        int[][] dp = new int[m][n];
        //边界条件 
        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][j - 1] + dp[i - 1][j];
            }
        }

        return dp[m - 1][n - 1];
    }

不同路径 II

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    continue;
                }
                if (i == 0 && j == 0) {
                    dp[i][j] = 1;
                    continue;
                }
                if (i == 0) {
                    dp[i][j] = dp[i][j - 1];
                    continue;
                }
                if (j == 0) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

空间优化

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;

        int[] dp = new int[n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    continue;
                }
                if (i == 0 && j == 0) {
                    dp[j] = 1;
                    continue;
                }
                if (i == 0) {
                    dp[j] = dp[j - 1];
                    continue;
                }
                if (j == 0) {
                    continue;
                }
                dp[j] += dp[j - 1];
            }
        }
        return dp[n - 1];
    }

打家劫舍(https://leetcode-cn.com/problems/house-robber/)

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

动态规划
对于每个新加入的元素nums[k]，求sum只有两种情况：加入nums[k]和不加入nums[k]；
1）加入nums[k]，那么dp[k] = dp[k-2] + nums[k];
虽然dp[k-1]，也有可能没有将nums[k-1]纳入求和，但这种情况下dp[k-1]=dp[k-2]，所以上式也成立。
2）不加入nums[k]，那么dp[k] = dp[k-1]；
取两者之大即可；

 public static int rob(int[] nums) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int[] dp = new int[n];

        // 初始化
        dp[0] = nums[0];
        if(n == 1){
            return dp[0];
        }
        dp[1] = Math.max(nums[0], nums[1]);
        for (int k = 2; k < n; k++) {
            dp[k] = Math.max(dp[k - 1],  dp[k - 2] + nums[k]);
        }
        return dp[n - 1];
    }

打家劫舍 II(https://leetcode-cn.com/problems/house-robber-ii/)

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。

动态规划
环状排列意味着第一个房子和最后一个房子中只能选择一个偷窃，因此可以把此环状排列房间问题约化为两个单排排列房间子问题：
在不偷窃第一个房子的情况下（即 nums[1:n]），最大金额是 p1；
在不偷窃最后一个房子的情况下（即 nums[0:n-1]），最大金额是 p2。
综合偷窃最大金额：为以上两种情况的较大值，即 max(p1,p2) 。

public static int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int n = nums.length;
        return Math.max(rob_single(nums, 0, n - 2), rob_single(nums, 1, n - 1));
    }

    public static int rob_single(int[] nums, int start, int end) {
        int n = end - start + 1;
        int[] dp = new int[n];

        // 初始化
        dp[0] = nums[start];
        if (n == 1) {
            return dp[0];
        }
        dp[1] = Math.max(nums[start], nums[start + 1]);
        for (int k = 2; k < n; k++) {
            dp[k] = Math.max(dp[k - 1], dp[k - 2] + nums[start + k]);
        }
        return dp[n - 1];
    }

最大正方形

动态规划
注意：之前的一系列背包问题的动态规划思路是：问题问什么，我们就把什么定义为规划的状态变量；但是，如果不是背包问题，那么这个规律不再适用！往往要结合问题的特征进行某些条件的附加，很多情况下的dp数组不会直观给出哪个元素是问题的答案，而是需要遍历dp数组，得到解决问题的某个关键值（一般为最大/最小值）。
以此题为例进行说明：
第一步：如果直接把dp[i][j]定义为问题的所问：(0,0)~(i,j)的二维矩阵内，只包含1的最大正方形的面积/边长，你会发现，完全无法利用起相邻子问题的解，困难之处在于0的存在，会将连续为1的正方形切割开来。
第二步：既然不能直接将问题所问定义为状态变量，我们考虑添加附加条件：dp[i][j]定义为以(i,j)为右下角的，只包含1的最大正方形的边长。添加了附加条件之后，我们解决了上面的困难，即对于0的存在，对应的dp[i][j]值为零，因为以0为右下角则不可能只包含1，所以边长必定为0。那么在这种情况下，我们计算得到的dp数组，如何求得最后的答案：即dp[i][j]数组中最大边长的平方。
第三步：在确定dp[i][j]的定义后，我们需要计算整个dp[i][j]数组。
A）(i,j)为0，dp[i][j]则为零。
B）(i,j)为1：
1）若(i-1,j-1)，(i,j-1)，(i-1,j)任意一个为0，此时dp[i][j]为1；
2）若(i-1,j-1)，(i,j-1)，(i-1,j)全为1，且对应的dp[i-1][j-1]，dp[i][j-1]，dp[i-1][j]分别对应为n，p，q，如下图所示，则此时dp[i][j]为min(n,p,q)+1;

然后发现2）的递推公式也包含了1）的情况；

代码如下：

    public int maximalSquare(char[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        if (n == 0) {
            return 0;
        }
        int[][] dp = new int[m + 1][n + 1];
        int maxEdge = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    maxEdge = Math.max(maxEdge, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return maxEdge * maxEdge;
    }

统计全为 1 的正方形子矩阵

动态规划
此题与上面求最大正方形面积的题几乎一致。
规划的状态变量完全一样：dp[i][j] 表示以(i,j)为右下角的，只包含1的最大正方形的边长；这个最大边长同时表示以(i,j)为右下角的正方形的个数：假设最大正方形的边长为3，那么以此点为右下角的正方形有边长为3，边长为2，边长为1的正方形各一个，总共3个。于是此题最后的总数即dp[i][j]的所有元素求和。
计算dp[i][j]数组的状态转移公式跟上面求最大正方形面积的完全一致：
A）(i,j)为0，dp[i][j]则为零。
B）(i,j)为1：dp[i][j]为min(dp[i-1][j-1]，dp[i][j-1]，dp[i-1][j]) + 1;
代码如下：

public int countSquares(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) {
            return 0;
        }
        int n = matrix[0].length;
        if (n == 0) {
            return 0;
        }
        int totalCount = 0;
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i-1][j-1] == 1) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    totalCount += dp[i][j];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return totalCount;
    }

解码方法

动态规划
1）状态转移方程：dp[i]表示0~i的字符串的解码总数。第i个字符可以自己单独解码，也可以和前一个字符一起解码（满足一定条件）。所以状态转移方程为：dp[i] = dp[i-1]或者dp[i] = dp[i-1] + dp[i-2]。
2）注意'0'的存在，'0'不能作为开头；

    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0 || s.charAt(0) == '0') {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != '0') {
                if (s.charAt(i - 1) != '0' && s.substring(i - 1, i + 1).compareTo("26") <= 0) {
                    dp[i] = dp[i - 1] + (i > 1 ? dp[i - 2] : 1);
                } else {
                    dp[i] = dp[i - 1];
                }
            } else if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
                dp[i] = (i > 1 ? dp[i - 2] : 1);
            } else {
                return 0;
            }

        }
        return dp[n - 1];
    }

乘积最大子数组

动态规划
1）若不存在负数，只存在0和正数：令dp[i]表示以nums[i]结尾的最大子数组乘积，则 dp[i] = max(dp[i-1] * nums[i], nums[i])。
2）由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值的dp数组。
3）则有：令dp_max[i]表示以nums[i]结尾的最大子数组乘积，令dp_min[i]表示以nums[i]结尾的最小子数组乘积，于是则有了下面的状态转移方程：

dp_max[i] = Math.max(nums[i], Math.max(nums[i] * dp_max[i-1], nums[i] * dp_min[i-1]));
dp_min[i] = Math.min(nums[i], Math.min(nums[i] * dp_max[i-1], nums[i] * dp_min[i-1]));

4）最后取出dp_max数组中最大的值即可；
代码如下：

    public static int maxProduct(int[] nums) {
        int n = nums.length;
        if(n == 1){
            return nums[0];
        }
        int ans = nums[0];
        int[] dp_max = new int[n];
        int[] dp_min = new int[n];
        dp_max[0] = nums[0];
        dp_min[0] = nums[0];
        for(int i=1; i<n; i++){
            int num1 = nums[i] * dp_max[i-1];
            int num2 = nums[i] * dp_min[i-1];
            dp_max[i] = Math.max(nums[i], Math.max(num1, num2));
            dp_min[i] = Math.min(nums[i], Math.min(num1, num2));

            ans = Math.max(ans, dp_max[i]);
        }
        return ans;
    }

不同的二叉搜索树

动态规划

    public int numTrees(int n) {
        int[] total = new int[n + 1];
        total[0] = 1;
        total[1] = 1;
        for (int i = 2; i <= n; i++) {
            total[i] = 0;
            for(int root = 1; root <= i; root++){
                total[i] += total[root - 1] * total[i - root];
            }
        }
        return total[n];
    }

股票系列问题总结

状态变量：

dp[i][k][0/1] 
i: 天数; 取值:0~n-1, n为给出的股票价格的天数
k: 最大允许交易次数; 取值:k~1, 从大到小, 因为是最大允许交易次数, 而不是交易次数
0/1: 是否持有股票; 0表示没有持有股票; 1表示持有股票;

比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。
再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。

状态转移公式：

dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
              max(   选择 rest  ,           选择 sell      )

解释：今天我没有持有股票，有两种可能：
要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
要么是我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
              max(   选择 rest  ,           选择 buy         )

解释：今天我持有着股票，有两种可能：
要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。

边界条件：
dp[0][k][0] = 0
解释：第0天，未持有股票，这时候的利润当然是 0 。
dp[0][k][1] = -price[0]
解释：第0天，持有股票，此时反而付出price[0]的价格购买股票 。
dp[i][0][0] = 0
解释： k = 0 意味着根本不允许交易，这时候利润当然是 0 。
dp[i][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

不同的股票问题，根据条件的不同，可以进行降维。

买卖股票的最佳时机

动态规划

根据通用的状态转移公式：(当然此题用贪婪解法，一次遍历即可解决)

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

由于本题k=1，即最多允许一次交易，所以上面的状态转移公式中的dp[i-1][k-1][0]此项为0。从而上面的状态转移公式中的k这一状态变量可以移除。

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

代码如下，从上面的状态转移公式中可以看出，对于状态变量i，只会跟i-1有关，所以可以进一步进行空间优化。但是空间优化之后的代码，直观上比较难以理解。

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

    // 空间优化
    public int maxProfit_savespace(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int dp_0 = 0;
        int dp_1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            // dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            // dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp_1 = Math.max(dp_1, -prices[i]);

        }
        // return dp[prices.length-1][0];
        return dp_0;
    }

买卖股票的最佳时机 II

动态规划
根据通用的状态转移公式：

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

由于本题k=无穷，即允许无限次交易，所以上面的状态转移公式中的k或者k-1都等于无穷大，于是可以移除此变量。

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

  public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];
        for (int i = 0; i < prices.length; i++) {
            if (i == 0) {
                dp[0][0] = 0;
                dp[0][1] = -prices[0];
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        }
        return dp[prices.length - 1][0];
    }
    // 空间优化
   public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int dp_0 = 0;
        int dp_1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int temp = dp_0;
            // dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            // dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp_1 = Math.max(dp_1, temp - prices[i]);

        }
        // return dp[prices.length-1][0];
        return dp_0;
    }

最佳买卖股票时机含冷冻期

动态规划
本题与股票问题||类似，都允许无限次交易。不同的是交易冷冻期为1天，所以状态转移方程如下：唯一的不同是买入的时候，要从i-2的状态转移，而不是i-1。

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。

代码：

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

    // 空间优化
    public int maxProfit(int[] prices) {
        if (prices.length <= 1) {
            return 0;
        }
        // 初始化:第1天的值; 
        // 另外一种更加简洁的初始化是赋值为第-1天的值，i从0开始遍历：dp_0 = 0; dp_1 = Interger.MIN_VAL
        int dp_0 = Math.max(0, -prices[0] + prices[1]);
        int dp_1 = Math.max(-prices[0], -prices[1]);
        int dp_pre_0 = 0; // dp_pre_0 用于保存dp[i - 2][0]的值
        for (int i = 2; i < prices.length; i++) {
            int temp = dp_0;  //上一轮循环结束后dp_0的值
            dp_0 = Math.max(dp_0, dp_1 + prices[i]); // 本轮循环结束后dp_0的值
            dp_1 = Math.max(dp_1, dp_pre_0 - prices[i]);
            dp_pre_0 = temp; // 对于下一轮循环而言, dp_pre_0就是上上轮的dp_0的值了
        }
        return dp_0;
    }

买卖股票的最佳时机含手续费

动态规划
本题与股票问题||类似，都允许无限次交易。不同的是多了交易手续费，所以状态转移方程如下：唯一的不同是买入的时候，费用还要额外减去手续费。

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
解释：第 i 天选择 buy 的时候，要额外减去手续费用。

代码：

    public int maxProfit(int[] prices, int fee) {
        if (prices.length == 0) {
            return 0;
        }
        int[][] dp = new int[prices.length][2];
        for (int i = 0; i < prices.length; i++) {
            if (i == 0) {
                dp[0][0] = 0;
                dp[0][1] = -prices[0] - fee;
                continue;
            }
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
        }
        return dp[prices.length - 1][0];
    }
    // 空间优化
    public int maxProfit(int[] prices, int fee) {
        if (prices.length <= 1) {
            return 0;
        }
        // 初始化:第0天的值（另外一种更简化的初始化方法：初始化为第-1天的值，dp_0 = 0; dp_1 = Integer.MIN_VAL；i从0开始遍历）
        int dp_0 = 0;
        int dp_1 = -prices[0] - fee;
        for (int i = 1; i < prices.length; i++) {
            int temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, temp - prices[i] - fee);
        }
        return dp_0;
    }

买卖股票的最佳时机 III

动态规划
根据通用的状态转移公式：

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

此题中k=2，即最大允许交易次数为2，我们可以将最大允许买入次数设置为2（或者最大卖出次数设置为2）。由于最大允许交易次数是逐渐减小的，所以for循环中，k是从大到小递减。由于k=2，k可取2和1（当k取0时对应的值为0），所以可以将第二维、第三维变量列举出来，进行空间规划，共2*2=4个变量。

    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int maxK = 2;
        int[][][] dp = new int[prices.length][maxK + 1][2];
        for (int i = 0; i < prices.length; i++) {
            for (int k = maxK; k >= 1; k--) {
                if (i == 0) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[0];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[prices.length - 1][maxK][0];
    }

    // 空间优化
    public int maxProfit(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        // 初始化赋值, 即i=0时赋值
        int dp_1_0 = 0;
        int dp_1_1 = -prices[0];
        int dp_2_0 = 0;
        int dp_2_1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int temp = dp_1_0;
            dp_1_0 = Math.max(dp_1_0, dp_1_1 + prices[i]);
            dp_1_1 = Math.max(dp_1_1, - prices[i]);
            dp_2_0 = Math.max(dp_2_0, dp_2_1 + prices[i]);
            dp_2_1 = Math.max(dp_2_1, temp - prices[i]);
        }
        return dp_2_0;
    }

买卖股票的最佳时机 IV

动态规划
依旧根据通用的状态转移公式：

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

此题中k值为变量，即最大允许交易次数为k，我们可以将最大允许买入次数设置为k（或者最大卖出次数设置为k）。
此题和上题基本一致，但出现了内存超出空间问题，原因是输入的k值很大，其实当k大于n/2时，就跟无穷大的效果是一致的，因为最多只可能交易n/2次。所以当输入的k大于n/2时，我们直接利用前面第二题的答案返回即可。

    // 原始动态规划
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int[][][] dp = new int[prices.length][k + 1][2];
        for (int i = 0; i < prices.length; i++) {
            for (int t = k; t >= 1; t--) {
                if (i == 0) {
                    dp[i][t][0] = 0;
                    dp[i][t][1] = -prices[0];
                    continue;
                }
                dp[i][t][0] = Math.max(dp[i - 1][t][0], dp[i - 1][t][1] + prices[i]);
                dp[i][t][1] = Math.max(dp[i - 1][t][1], dp[i - 1][t - 1][0] - prices[i]);
            }
        }
        return dp[prices.length - 1][k][0];
    }

    // 空间优化的答案
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        if(k > prices.length / 2){
            return maxProfit_k_inf(prices);
        }
        int[][] dp_0 = new int[prices.length][k + 1];
        int[][] dp_1 = new int[prices.length][k + 1];
        for (int i = 0; i < prices.length; i++) {
            for (int t = k; t >= 1; t--) {
                if (i == 0) {
                    dp_0[i][t] = 0;
                    dp_1[i][t] = -prices[0];
                    continue;
                }
                dp_0[i][t] = Math.max(dp_0[i - 1][t], dp_1[i - 1][t] + prices[i]);
                dp_1[i][t] = Math.max(dp_1[i - 1][t], dp_0[i - 1][t - 1] - prices[i]);
            }
        }
        return dp_0[prices.length - 1][k];
    }

    // 代码重用:即k为无穷时的答案
    public int maxProfit_k_inf(int[] prices) {
        if (prices.length == 0) {
            return 0;
        }
        int dp_0 = 0;
        int dp_1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            int temp = dp_0;
            dp_0 = Math.max(dp_0, dp_1 + prices[i]);
            dp_1 = Math.max(dp_1, temp - prices[i]);
        }
        return dp_0;
    }

三角形最小路径和

动态规划

public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        if (m == 0) {
            return 0;
        }
        int[][] dp = new int[m][m];
        dp[0][0] = triangle.get(0).get(0);
        for (int row = 1; row < m; row++) {
            for (int col = 0; col <= row; col++) {
                int num = triangle.get(row).get(col);
                if (col == 0) { // 最左端
                    dp[row][col] = dp[row - 1][col] + num;
                }else if(col == row){ // 最右端
                    dp[row][col] = dp[row - 1][col - 1] + num;
                }else { // 中间
                    dp[row][col] = Math.min(dp[row - 1][col - 1] + num, dp[row - 1][col] + num);
                }
            }
        }

        // 从最后一行中找出最短路径
        int minPath = dp[m - 1][0];
        for (int i = 1; i < m; i++) {
            minPath = Math.min(minPath, dp[m - 1][i]);
        }
        return minPath;
    }

空间优化
记住空间优化的技巧：
观察自顶向下的代码会发现，对第row行的最小路径和的推导，只需要第row-1行的dp[row - 1][col]和dp[row - 1][col - 1]元素即可。可以使用两个变量暂存。
一维的dp数组只存储第row行的最小路径和。

 // 空间优化
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        if (m == 0) {
            return 0;
        }
        int[] dp = new int[m];
        dp[0] = triangle.get(0).get(0);
        int prev = 0; // 暂存dp[row - 1][col - 1]
        int curr; // 暂存暂存dp[row - 1][col]
        for (int row = 1; row < m; row++) {
            for (int col = 0; col <= row; col++) {
                int num = triangle.get(row).get(col);
                curr = dp[col];
                if (col == 0) { // 最左端
                    dp[col] = curr + num;
                }else if(col == row){ // 最右端
                    dp[col] = prev + num;
                }else { // 中间
                    dp[col] = Math.min(prev + num, curr + num);
                }
                prev = curr;
            }
        }

        int minPath = dp[0];
        for (int i = 1; i < m; i++) {
            minPath = Math.min(minPath, dp[i]);
        }
        return minPath;
    }

完全平方数

动态规划

如果是平方数，则为1；
否则，为min(dp[i - 1 * 1], dp[i - 2 * 2], ...) + 1

public int numSquares(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            if(isSqrt(i)){
                dp[i] = 1;
            }else {
                int start = 1;
                int min = i;
                while (i - start * start > 0){
                    min = Math.min(dp[i - start * start] + 1, min);
                    start++;
                }
                dp[i] = min;
            }
        }
        return dp[n];
    }

    public boolean isSqrt(int num){
        int sqrt = (int) Math.sqrt(num);
        return sqrt * sqrt == num;
    }

数学
详见leetcode的定理解说。

丑数

动态规划

public int nthUglyNumber(int n) {
        int a = 0;
        int b = 0;
        int c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int n2 = dp[a] * 2;
            int n3 = dp[b] * 3;
            int n5 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n5);
            if (dp[i] == n2) {
                a++;
            }
            if (dp[i] == n3) {
                b++;
            }
            if (dp[i] == n5) {
                c++;
            }
        }
        return dp[n - 1];
    }

整数拆分

动态规划

    public int integerBreak(int n) {
        if (n < 3) {
            return n - 1;
        }
        int[] dp = new int[n + 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), j * dp[i - j]));
            }
        }
        return dp[n];
    }

递归
暴力递归搜索

    public int integerBreak(int n) {
        if(n < 3){
            return n-1;
        }
        int ans = 0;
        for (int i = 1; i < n; i++) {
            ans = Math.max(ans, Math.max(i * (n - i), i * integerBreak(n - i)));
        }
        return ans;
    }

暴力超时原因是很多重复计算，于是加入缓存

    // 缓存搜索
    private int[] memory;

    public int integerBreak(int n) {
        memory = new int[n + 1];
        return recursion(n);
    }

    public int recursion(int n) {
        if (n < 3) {
            return n - 1;
        }
        if (memory[n] > 0) {
            return memory[n];
        }
        int res = 0;
        for (int i = 1; i < n; i++) {
            res = Math.max(res, Math.max(i * (n - i), i * recursion(n - i)));
        }
        memory[n] = res;
        return res;
    }

可被三整除的最大和

因为每一层dp的赋值会互相引用上一层的的值，所以需要加一个缓存变量dp2

     public int maxSumDivThree(int[] nums) {
        int[] dp = new int[]{0, Integer.MIN_VALUE, Integer.MIN_VALUE};
        for (int n : nums) {
            int[] dp2 = new int[3];
            for (int i = 0; i < 3; i ++) {
                int mod = n % 3;
                dp2[i] = Math.max(dp[i], dp[(3 + i - mod) % 3] + n);
            }   
            dp = dp2;
        }
        return dp[0];
    }

打家劫舍 III

class Solution {
    Map<TreeNode, Integer> f = new HashMap<TreeNode, Integer>();
    Map<TreeNode, Integer> g = new HashMap<TreeNode, Integer>();

    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(f.getOrDefault(root, 0), g.getOrDefault(root, 0));
    }

    public void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        dfs(node.right);
        f.put(node, node.val + g.getOrDefault(node.left, 0) + g.getOrDefault(node.right, 0));
        g.put(node, Math.max(f.getOrDefault(node.left, 0), g.getOrDefault(node.left, 0)) + Math.max(f.getOrDefault(node.right, 0), g.getOrDefault(node.right, 0)));
    }
}

空间优化

public int rob(TreeNode root) {
        int[] rootStatus = dfs(root);
        return Math.max(rootStatus[0], rootStatus[1]);
    }

    public int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[]{0, 0};
        }
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);
        int selected = node.val + l[1] + r[1];
        int notSelected = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
        return new int[]{selected, notSelected};
    }

石子游戏

解决博弈问题的动态规划通用思路

package com.qiyun;

/**
 * Created by qiyunsun on 2020/8/8.
 */
public class Solution {

    class Pair {
        int fir, sec;

        Pair(int fir, int sec) {
            this.fir = fir;
            this.sec = sec;
        }
    }

    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        // 初始化 dp 数组
        Pair[][] dp = new Pair[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i; j < n; j++)
                dp[i][j] = new Pair(0, 0);
        // 填入 base case
        for (int i = 0; i < n; i++) {
            dp[i][i].fir = piles[i];
            dp[i][i].sec = 0;
        }
        // 斜着遍历数组
        for (int l = 2; l <= n; l++) {
            for (int i = 0; i <= n - l; i++) {
                int j = l + i - 1;
                // 先手选择最左边或最右边的分数
                int left = piles[i] + dp[i + 1][j].sec;
                int right = piles[j] + dp[i][j - 1].sec;
                // 套用状态转移方程
                if (left > right) {
                    dp[i][j].fir = left;
                    dp[i][j].sec = dp[i + 1][j].fir;
                } else {
                    dp[i][j].fir = right;
                    dp[i][j].sec = dp[i][j - 1].fir;
                }
            }
        }
        Pair res = dp[0][n - 1];
        return res.fir - res.sec > 0;
    }
    
}

新21点

动态规划之反序求解

class Solution {
    public double new21Game(int N, int K, int W) {
        if (K == 0) {
            return 1.0;
        }
        double[] dp = new double[K + W];
        for (int i = K; i <= N && i < K + W; i++) {
            dp[i] = 1.0;
        }
        for (int i = K - 1; i >= 0; i--) {
            for (int j = 1; j <= W; j++) {
                dp[i] += dp[i + j] / W;
            }
        }
        return dp[0];
    }
}

优化
上述计算中，第二层for循环可以被优化，因为每一次第二层的计算相比上一次只有一个值的移动。

class Solution {
    public double new21Game(int N, int K, int W) {
        if (K == 0) {
            return 1.0;
        }
        double[] dp = new double[K + W];
        for (int i = K; i <= N && i < K + W; i++) {
            dp[i] = 1.0;
        }
        dp[K - 1] = 1.0 * Math.min(N - K + 1, W) / W;
        for (int i = K - 2; i >= 0; i--) {
            dp[i] = dp[i + 1] - (dp[i + W + 1] - dp[i + 1]) / W;
        }
        return dp[0];
    }
}