数据结构与算法学习——动态规划-3

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

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + nums[i][j];

   public int maxValue(int[][] grid) {
       if (grid == null || grid.length == 0) return 0;
       int row = grid.length;
       int column = grid[0].length;
       int[][] dp = new int[row][column];
       int value = 0;
// 初始化 dp 数组
       for (int i = 0;i < row;i++) {
           value += grid[i][0];
           dp[i][0] = value;
       }
       value = 0;
       for (int j = 0;j < column;j++) {
           value += grid[0][j];
           dp[0][j] = value;
       }
       for (int i = 1;i < row;i++) {
           for (int j = 1;j < column;j++) {
               dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
           }
       }
       return dp[row - 1][column - 1];
   }

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

public int lengthOfLongestSubstring(String s) {
    if (s == null || s.length() == 0) return 0;
    Map<Character, Integer> memo = new HashMap<>();
    // 由于 dp[i] 只与前一个状态 dp[i - 1] 有关，所以使用一个变量进行滚动
    int temp = 0, result = 0;
    for (int i = 0;i < s.length();i++) {
        // 如果没有对应的 key ，那么返回 -1
        int index = memo.getOrDefault(s.charAt(i), -1);
        // 更新 map 
        memo.put(s.charAt(i), i);
        temp = temp < i - index ? temp + 1 : i - index;
        result = Math.max(temp, result);
    }
    return result;
}

输入: 12258
输出: 5
解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi"

if (最后两个数可以翻译为一个字母) {
    dp[i] = dp[i - 1] + dp[i - 2];
} else {
    dp[i] = dp[i - 1];
}

    public int translateNum(int num) {
        //1 先将 num 转换为字符串
        String str = String.valueOf(num);
        // 创建一个 dp 数组，长度为 str.length()
        int[] dp = new int[str.length()];
        // 初始化 dp 数组
        dp[0] = 1;
        // 从 1 开始
        for (int i = 1;i < str.length();i++) {
            // 如果前一个数等于 1 ，或者前一个数等于 2 且当前数小于等于 5 
            if (str.charAt(i - 1) == '1' || (str.charAt(i - 1) == '2' && str.charAt(i) <= '5')) {
                if (i == 1) {
                    // 如果 i == 1，那么直接初始化为 2 
                    dp[i] = 2;
                } else {
                    dp[i] = dp[i - 2] + dp[i - 1];
                }
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[str.length() - 1];
    }

输入：nums = [3,4,2]
输出：6
解释：
删除 4 获得 4 个点数，因此 3 也被删除。之后，删除 2 获得 2 个点数。总共获得 6 个点数。

输入：nums = [2,2,3,3,3,4]
输出：9
解释：
删除 3 获得 3 个点数，接着要删除两个 2 和 4 。之后，再次删除 3 获得 3 个点数，再次删除 3 获得 3 个点数。总共获得 9 个点数。

nums = {2,2,3,3,3,4}
temp = {0,0,2,3,1}

dp[i] = Math.max(dp[i - 1], dp[i - 2] + i * temp[i]);

public int deleteAndEarn(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    //1 先找出数组中的最大数，用于构造新数组
    int max = Integer.MIN_VALUE;
    for (int num : nums) {
        max = Math.max(max, num);
    }
    if (max <= 0) return 0;
    // 必须是最大值 + 1 长度
    int[] temp = new int[max + 1];
    for (int num : nums) {
        temp[num]++;
    }
    // 接下来，就按照打家劫舍的方法做
    if (temp.length == 1) return temp[0];
    if (temp.length == 2) return Math.max(temp[0], temp[1]);
    int one = temp[0];
    int two = Math.max(temp[0], temp[1]);
    int cur = 0;
    for (int i = 2;i < temp.length;i++) {
        cur = Math.max(two, one + i * temp[i]);
        one = two;
        two = cur;
    }
    return cur;
}

dp[i] = Math.max(0, Math.min(maxLeft, maxRight) - height[i])

int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i])

public int trap(int[] height) {
    if (height == null || height.length <= 2) return 0;
    int[] leftMax = new int[height.length];
    leftMax[0] = height[0];
    // 正向遍历，获取每根柱子左边的最大高度
    for (int i = 1;i < height.length;i++) {
        leftMax[i] = Math.max(leftMax[i - 1], height[i]);
    }
    int[] rightMax = new int[height.length];
    // 反向遍历，获取每根柱子右边的最大高度
    rightMax[height.length - 1] = height[height.length - 1];
    for (int i = height.length - 2;i >= 0;i--) {
        rightMax[i] = Math.max(rightMax[i + 1], height[i]);
    }
    // 使用一个变量来计算总水量
    int sum = 0;
    // 第一根和最后一根柱子没有结果，直接跳过
    for (int i = 1;i < height.length - 1;i++) {
        int count = Math.max(0, Math.min(leftMax[i], rightMax[i]) - height[i]);
        sum += count;
    }
    return sum;
}

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。=

dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3),dp[p5] * 5);

public int nthUglyNumber(int n) {
    if (n == 1) return 1;
    // 创建一个最小堆，用于存放丑数
    PriorityQueue<Long> minHeap = new PriorityQueue<>();
    // 创建一个数组，用于存放质因子。
    int[] nums = {2, 3, 5};
    Set<Long> set = new HashSet<>();
    // 初始化，我们需要将 1 放入最小堆中
    minHeap.add(1L);
    long result = 0;
    for (int i = 0;i < n;i++) {
        result = minHeap.poll();
        for (int num : nums) {
            long uglyNum = num * result;
            // 只有集合中不存在时，才将结果加入到最小堆中
            if (!set.contains(uglyNum)) {
                minHeap.add(uglyNum);
                set.add(uglyNum);
            }
        }
    }
    return (int)result;
}

public int nthUglyNumber(int n) {
    if (n == 1) return 1;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    int p2 = 1, p3 = 1, p5 = 1;
    for (int i = 2;i <= n;i++) {
        dp[i] = Math.min(Math.min(dp[p2] * 2, dp[p3] * 3), dp[p5] * 5);
        if (dp[i] == dp[p2] * 2) {
            p2++;
        }
        if (dp[i] == dp[p3] * 3) {
            p3++;
        }
        if (dp[i] == dp[p5] * 5) {
            p5++;
        }
    }
    return dp[n];
}

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

if(dp[j] && j + nums[j] > i) {
  dp[i] = true;
}

public boolean canJump(int[] nums) {
    if (nums == null || nums.length <= 1) return true;
    boolean[] dp = new boolean[nums.length];
    dp[0] = true;
    for (int i = 1;i < nums.length;i++) {
        for (int j = 0;j < i;j++) {
            if (dp[j] && nums[j] + j >= i) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[nums.length - 1];
}

1、题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

if (j + nums[j] >= i) {
    // 如果在 j 位置可以直接到达 i 位置，那么直接在到达 j 所需要的最少步数 dp[j] 的基础上 + 1即可，但我们需要和 dp[i] 做比较，取最小值
    dp[i] = Math.min(dp[i], dp[j] + 1);
}=

public int jump(int[] nums) {
    int len = nums.length;
    if (len <= 1) return 0;
    // 创建一个大小为 len 的数组，并对它的值进行初始化
    int[] dp = new int[len];
    // 初始化数组的值为 Integer.MAX_VALUE ，因为我们需要与 0 作比较取最小值，所以要初始化一个值
    Arrays.fill(dp, Integer.MAX_VALUE);
    // 初始化 dp[0] 和 dp[1] ，当 i 等于 0 时，至少花 0 步就可以到达，当 i 等于 1 时，只需要一步就可以到达 1 
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2;i < len;i++) {
        for (int j = 0;j < i;j++) {
            // 如果在 [0, i - 1] 范围内有位置可以一步到达 i ，那么我们需要进行选择，
            if (j + nums[j] >= i) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    return dp[len - 1];
}

给定一个由整数数组 A 表示的**环形数组 C**，求 C 的非空子数组的最大可能和。
在此处，环形数组意味着数组的末端将会与开头相连呈环状。
（形式上，当0 <= i < A.length 时 C[i] = A[i]，且当 i >= 0 时 C[i+A.length] = C[i]）
此外，子数组最多只能包含固定缓冲区 A 中的每个元素一次。
（形式上，对于子数组 C[i], C[i+1], …, C[j]，不存在 i <= k1, k2 <= j 其中 k1 % A.length = k2 % A.length）

输入：[1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

输入：[5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

输入：[3,-1,2,-1]
输出：4
解释：从子数组 [2,-1,3] 得到最大和 2 + (-1) + 3 = 4

public int maxSubarraySumCircular(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int first = maxSubarray(nums);
    int total = 0;
    // 计算 total 的值
    for (int num : nums) {
        total += num;
    }
    int min = minSubarray(nums);
    int second = total - min;
    // 如果 total 等于 min ，那么证明差为 0 ，那么此时如果 first 返回的值是负数，那么就会返回错误的 0 
    if (total == min) return first;
    return Math.max(first, second);
}
private int minSubarray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int len = nums.length;
    int[] dp = new int[len];
    dp[0] = nums[0];
    int min = Integer.MAX_VALUE;
    for (int i = 1;i < len;i++) {
        dp[i] = Math.min(dp[i - 1] + nums[i], nums[i]);
        min = Math.min(dp[i], min);
    }
    return min;
}
private int maxSubarray(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int len = nums.length;
    int[] dp = new int[len];
    int max = Integer.MIN_VALUE;
    dp[0] = nums[0];
    for (int i = 1;i < len;i++) {
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        max = Math.max(dp[i], max);
    }
    return max;
}

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），
并返回该子数组所对应的乘积。

输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];
    int preMax = nums[0], preMin = nums[0], max = nums[0];
    int curMax = 0, curMin = 0;
    for (int i = 1;i < nums.length;i++) {
        if (nums[i] > 0) {
            curMax = preMax * nums[i];
            curMin = preMin * nums[i];
        } else {
            curMax = preMin * nums[i];
            curMin = preMax * nums[i];
        }
        preMax = Math.max(curMax, nums[i]);
        preMin = Math.min(curMin, nums[i]);
        max = Math.max(preMax, max);
    }
    return max;
}

给你一个整数数组 nums ，请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组，请你返回乘积为正数的最长子数组长度。

输入：nums = [1,-2,-3,4]
输出：4
解释：数组本身乘积就是正数，值为 24 。

输入：nums = [-1,-2,-3,0,1]
输出：2
解释：乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。

所以，如果 pos[i - 1] 大于 0 ，那么此时它可以放心乘上 nums[i] ，如果 pos[i - 1] 等于 0 ，
那么子数组 {nums[i]} 就是以 i 结尾的乘积为正数的最长子数组，即此时 pos[i] = 1，
所以我们可以直接列出当 nums[i] 大于 0 的状态转移方程；
而如果 neg[i - 1] 大于 0 ，那么它也可以放心乘上 nums[i]，如果 neg[i - 1] 等于 0，
那么 neg[i ] 依然为 0。

if (nums[i] > 0) {
    pos[i] = pos[i - 1] + 1;
    neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
}

如果 pos[i - 1] 大于 0，那么此时我们将 nums[i] 放入以 i - 1 结尾的子数组中，
整个子数组的乘积变为了负数，所以此时有 neg[i] = pos[i - 1] + 1；如果 pos[i - 1] 等于 0 ，
那么此时如果我们将 nums[i] 放入以 i - 1 结尾的子数组中，可能会导致整个子数组乘积变为正，
所以此时我们直接记 neg[i] 为 1 。
如果 neg[i - 1] 大于 0，那么此时将 nums[i] 放入以 i - 1 结尾的子数组中，
整个子数组的乘积变为了正数，所以此时 pos[i] 的值应该更新为 neg[i - 1] + 1 ，
如果 neg[i - 1] 的值等于 0 ，那么应该将 pos[i] 置为 0。

if (nums[i] < 0) {
    neg[i] = pos[i - 1] + 1;
    pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
}

if (nums[i] > 0) {
    pos[i] = pos[i - 1] + 1;
    neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
} else if (nums[i] == 0) {
    pos[i] = neg[i] = 0;
} else {
    neg[i] = pos[i - 1] + 1;
    pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
}

public int getMaxLen(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0] > 0 ? 1 : 0;
    int[] pos = new int[nums.length];
    int[] neg = new int[nums.length];
    int max = Integer.MIN_VALUE;
    if (nums[0] > 0) {
        pos[0] = 1;
    } else if (nums[0] < 0) {
        neg[0] = 1;
    }
    for (int i = 1;i < nums.length;i++) {
        if (nums[i] > 0) {
            pos[i] = pos[i - 1] + 1;
            neg[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
        } else if (nums[i] == 0) {
            pos[i] = 0;
            neg[i] = 0;
        } else {
            neg[i] = pos[i - 1] + 1;
            pos[i] = neg[i - 1] > 0 ? neg[i - 1] + 1 : 0;
        }
        max = Math.max(max, pos[i]);
    }
    return max;
}

public int getMaxLen(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    if (nums.length == 1) return nums[0] > 0 ? 1 : 0;
    int posMax = 0;
    int negMax = 0;
    int max = Integer.MIN_VALUE;
    if (nums[0] > 0) {
        posMax = 1;
    } else if (nums[0] < 0) {
        negMax = 1;
    }
    int curPos = 0;
    int curNeg = 0;
    for (int i = 1;i < nums.length;i++) {
        if (nums[i] > 0) {
            curPos = posMax + 1;
            curNeg = negMax > 0 ? negMax + 1 : 0;
        } else if (nums[i] == 0) {
            curPos = 0;
            curNeg = 0;
        } else {
            curNeg = posMax + 1;
            curPos = negMax > 0 ? negMax + 1 : 0;
        }
        // 进行滚动
        negMax = curNeg;
        posMax = curPos;
        max = Math.max(max, curPos);
    }
    return max;
}

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

dp[i][j] = dp[i - 1][j]

dp[i][j] = dp[i - i][j - weight[i]] + value[i];

if (j < weight[i]) {
  dp[i][j] = dp[i - 1][j]
} else {
  dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])
}

if (j < weight[i]) {
  dp[j] = dp[j];
} else {
  dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
}

当 j 为 0 时，此时背包容量为 0 ，所以所能装的物品的最大价值也是 0 ，即 dp[0] = 0；
对于其他位置的值，我们同样将其初始化为 0 ，
避免因初始化值过大导致递推公式计算出来的值无法将初始值覆盖（将整个数组都初始化为 0 。

在二维数组中，无论是先遍历物品，还是先遍历背包都是可以的，
但是在一维 dp 数组中，我们需要先遍历物品，然后再遍历背包，
同时需要注意的是，我们在遍历背包时，需要进行倒序遍历。

这是为了保证物品只被添加一次，在使用二维数组时，
当前层和上一层的数据是完全隔离开的，所以正序遍历和倒序遍历都可以，
但当我们使用一维数组时， 如果先计算 dp[j - 1] ，那么它可能会影响到后面 dp [j] 的数据，
我们可以来举一个例子，其中 weight = {1,3,4} ，values = {15,20,30} ，同时最大容量 capacity = 4。

public static int knapsack(int number, int capacity, int[] weight, int[] values) {
    if (weight == null || values == null || weight.length != values.length) return 0;
    // 创建一个一维的 dp 数组，dp[j] 表示，当背包容量为 j 时，该背包能容纳物品的最大价值
    int[] dp = new int[capacity + 1];
    // 外层循环，先遍历物品
    for (int i = 0;i < number;i++) {
        // 内层循环，需要倒序遍历背包
        for (int j = capacity;j >= weight[i];j--) {
            // 使用递推公式，从右至左计算 dp[j] 的值
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + values[i]);
        }
    }
    // 最后返回 dp[capacity] ，就是 capacity 容量的背包所能容纳的物品的最大价值
    return dp[capacity];
}

给你一个整数数组 nums 和一个整数 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

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

public int findTargetSumWays(int[] nums, int target) {
    if (nums == null || nums.length == 0) return 0;
    //1 计算数组元素和
    int sum = gengerateSumByArray(nums);
    //2 如果 sum 小于 target 或者 （sum + target） 不是偶数，那么直接返回 0 
    if (sum < target || (sum + target) % 2 == 1) return 0;
    //3 使用一个变量保存 (sum + target) / 2;
    target = (sum + target) / 2;
    //这里需要进行判断，如果计算出来的 target 小于 0 ，那么需要将其变为相反数
    target = Math.abs(target);
    //4 创建一个长度为 target + 1 的数组，并进行初始化
    int[] dp = new int[target + 1];
    // 当 j == 0 时，此时在 nums 中，只能找出一种方案凑出 0 ，所以 dp[0] = 1
    dp[0] = 1;
    //5 外层循环遍历物品
    for (int num : nums) {
        //6 内层循环倒序遍历背包
        for (int j = target;j >= num;j--) {
            // 使用递推公式累加 dp[j] 的值
            dp[j] += dp[j - num];
        }
    }
    return dp[target];
}
private int gengerateSumByArray(int[] nums) {
    int sum = 0;
    for (int num: nums) sum += num;
    return sum;
}

dp[j] = dp[j] || dp[j - nums[i]]

/**
 * 这道题可以看为，在 nums 中，是否可以找到几个数，这几个数的和为 sum / 2 ，其中 sum 为数组元素和
 */
public boolean canPartition(int[] nums) {
    if (nums == null || nums.length == 0) return true;
    //1 计算数组元素和
    int sum = gengerateSumByArray(nums);
    // 如果数组元素和不是一个偶数，那么直接返回 false
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    //2 我们需要在数组 nums 中，找到是否存在几个数字，满足这几个数字的和为 target
    // dp[j] 表示在数组 nums 中，是否存在几个数字，满足这几个数字的和为 j
    boolean[] dp = new boolean[target + 1];
    // 初始化 dp 数组，当 j == 0 时，此时可以找到几个数字，满足这几个数字的和为 0 
    dp[0] = true;
    for (int num : nums) {
        for (int j = target;j >= num;j--) {
            // 如果 dp[j] 或 dp[j - num] 有一个为真，那么 dp[j] 即为真，此时代表存在...
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}
private int gengerateSumByArray(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    return sum;
}

在上面有提到，这道题其实就是尽量将石头分成重量相同的两堆，然后让相撞之后剩下的石头最小。
这道题其实就是求，给你一个大小为 sum / 2 的背包，其中 sum 为 nums 的元素和，
然后尽可能地往背包中装东西，我们假设最多往背包中装了 maxWeight 重量的石头，
那么我们要求的结果就是 sum - 2 * maxWeight;

使用一个一维的 boolean 类型的 dp 数组，
其中 dp[j] 的含义、状态转移方程与 分割等和子集 问题中 dp 数组的含义相同，即在数组 nums 中，
能否找到一个子集，使得这个子集的元素和的值等于 j 。

public int lastStoneWeightII(int[] stones) {
    if (stones == null || stones.length == 0) return 0;
    int sum = generateSumByArray(stones);
    // 计算出 target 的值，我们要尽可能装满这个容量为 target 的包
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    // 外层循环遍历物品
    for (int stone : stones) {
        // 内层循环反向遍历背包
        for (int j = target;j >= stone;j--) {
            dp[j] = dp[j] || dp[j - stone];
        }
    }
    // 填完表后，我们需要找到最接近 target 的一个 j 值
    for (int j = target;;j--) {
        // 找到第一个为 true 的j
        if (dp[j]) {
            return sum - 2 * j;
        }
    }
}
private int generateSumByArray(int[] stones) {
    int sum = 0;
    for (int stone : stones) sum += stone;
    return sum;
}

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)

public int findMaxForm(String[] strs, int m, int n) {
    if (strs == null || strs.length == 0) return 0;
    // 创建一个二维数组，其中 dp[i][j] 表示子集最多能有 i 个 0 ，j 个 1 时，最大子集的长度
    int[][] dp = new int[m + 1][n + 1];
    // 外层循环遍历物品，在这道题中，一个字符串就是一件物品
    for (String str : strs) {
        // 获取这个字符串中 1 的个数和 0 的个数
        int zeroNum = countCharNum(str, '0');
        int oneNum = countCharNum(str, '1');
        // 内层循环遍历背包，这里有两个背包需要进行遍历，分别为容量为 m 的背包和 容量为 n 的背包，倒序遍历
        for (int i = m;i >= zeroNum;i--) {
            for (int j = n;j >= oneNum;j--) {
                // 使用递推公式计算 dp[i][j] 的值
                dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
            }
        }
    }
    return dp[m][n];
}
private int countCharNum(String str, char ch) {
    int num = 0;
    for (int i = 0;i < str.length();i++) {
        if (str.charAt(i) == ch) {
            num++;
        }
    }
    return num;
}

/**
 * 求解完全背包问题
 * @param number 物品个数
 * @param capacity 背包容量
 * @param weight 物品重量数组
 * @param value 物品价值数组
 * @return 能获取到的最大收益
 */
public int completeBackpack(int number, int capacity, int[] weight, int[] value) {
    if (weight == null || value == null || weight.length != value.length) {
        return 0;
    }
    // 创建一个一维数组 dp
    int[] dp = new int[capacity + 1];
    // 外层数组遍历物品
    for (int i = 0;i < number;i++) {
        // 内层物品遍历背包，这里需要从左往右遍历
        for (int j = weight[i];j <= capacity;j++) {
            // 使用递推公式
            dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    return dp[capacity];
}

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

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

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

dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
// 注意，这里需要当子问题有解时才进行状态转移，即 dp[j - coins[i]] 不为 Integer.MAX_VALUE 时

public int coinChange(int[] coins, int amount) {
    if (coins == null || coins.length == 0) return -1;
    if (amount == 0) return 0;
    // 创建一个 dp 数组，长度为 amount + 1 ，其中 dp[amount] 就是在 coins 数组中，凑出 amount 所需的最少硬币数，也就是我们要求的结果
    int[] dp = new int[amount + 1];
    // 初始化 dp 数组，dp[0] = 1，这一步可以省略，我们需要将 dp 数组中非 0 位置的元素 初始化为 Integer.MAX_VALUE
    for (int i = 1;i < dp.length;i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    // 外层遍历，遍历物品，也即硬币
    for (int coin : coins) {
        // 内层遍历，正向遍历背包，
        for (int j = coin;j <= amount;j++) {
            //  dp[j - coin] 不为 Integer.MAX_VALUE 时，证明此时 j - coin 可以被凑出，即这个问题有解，此时才需要进行求解。
            if (dp[j - coin] != Integer.MAX_VALUE) {
                // 使用状态转移方程求解 dp[j] 的值，这里求得是最小值
                dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

dp[j] += dp[j - nums[i]]

dp[0] = 1;

public int change(int amount, int[] coins) {
    if (coins == null || coins.length == 0) return 0;
    // 创建一个 dp 数组，其中 dp[j] 表示在 coins 中，能凑出数额为 j 的方案数
    int[] dp = new int[amount + 1];
    // 初始化 dp 数组，当 j 为 0 时， dp[j] == 1
    dp[0] = 1;
    // 外层遍历，遍历物品
    for (int i = 0;i < coins.length;i++) {
        // 内层遍历，对于完全背包问题，我们需要正向遍历背包
        for (int j = coins[i];j <= amount;j++) {
            // 使用递推公式计算出 dp[j]
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

给你一个由 不同 整数组成的数组 `nums` ，和一个目标整数 `target` 。
请你从 `nums` 中找出并返回总和为 `target` 的元素组合的个数。
请注意，顺序不同的序列被视作不同的组合。

输入：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)
请注意，顺序不同的序列被视作不同的组合。

输入：nums = [9], target = 3
输出：0

dp[i] += dp[i - nums[j]];

   public int combinationSum4(int[] nums, int target) {
       if (nums == null || nums.length == 0) return 0;
       // 创建一个 dp 数组，其中 dp[i] 表示能在 nums 中能组成 i 的排列数
       int[] dp = new int[target + 1];
// 初始化 dp[0] = 1 ，这个 dp[0] 是没有含义的
       dp[0] = 1;
       // 外层循环遍历背包
       for (int i = 0;i <= target;i++) {
           // 内层循环遍历物品
           for (int j = 0;j < nums.length;j++) {
               // 只有当背包容量大于第 j 件物品时，才需要进行分割子问题
               if (i >= nums[j]) {
                   dp[i] += dp[i - nums[j]];
               }
           }
       }
       return dp[target];
   }

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

dp[i] += dp[i - nums[j]];

public int climbStairs(int n) {
    if (n == 1 || n == 2) return n;
    // 初始化一个 dp 数组，长度为 n + 1，其中 dp[i] 表示爬上 i 阶楼梯的方案排列数
    int[] dp = new int[n + 1];
    // 初始化 dp 数组
    dp[0] = 1;
    // 外层循环，在求排列的过程中需要遍历背包
    for (int i = 0;i <= n;i++) {
        // 内层循环，需要遍历物品，这里只有两件物品，其中第一件物品的重量为 1 ，第二件物品的重量为 2 
        for (int j = 1;j <= 2;j++) {
            // 如果当前背包的容量大于物品重量，这里为 j 
            if (i >= j) {
                dp[i] += dp[i - j];
            }
        }
    }
    return dp[n];
}

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

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

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

private int getSizeByN(int n) {
    int size = 0;
    // 比如说 size 为 10 ，那么比 10 小的平方数有 1、4和9，可供选择的物品有 1 2 3 
    while (true) {
        // 如果 size + 1 的平方大于 n ，那么此时直接 break ，得到的 size 就是我们要寻找的值，当前物品的个数就是 1 - n 
        if ((size + 1) * (size + 1) > n) {
            break;
        }
        size++;
    }
    return size;
}

public int numSquares(int n) {
    if (n == 1) return 1;
    // 创建一个 dp 数组，其中 dp[i] 表示和为 i 的完全平方数的最少数量
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    // 初始化 dp 数组
    dp[0] = 0;
    // 计算出当前物品的个数，即 size 
    int size = getSizeByN(n);
    // 外层循环遍历物品
    for (int i = 1;i <= size;i++) {
        // 内层循环正序遍历背包，只有当当前背包容量大于等于物品重量的平方时且子问题有解时，才能进行状态转移
        for (int j = 0;j <= n;j++) {
            if (j >= i * i && dp[j - i * i] != Integer.MAX_VALUE) {
                // 此时可以进行状态转移
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
    }
    return dp[n];
}

dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);

dp[j] = dp[j] || dp[j - nums[i]];

dp[j] += dp[j - nums[i]];

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

如果 s[0, i - 1] 已经是 t[0, j - 2] 的子序列，那么 s[0, i - 1] 也必定为 t[0, j - 1] 的子序列。
如果 s[0, i - 1] 并不是 t[0, j - 2] 的子序列，
那么此时 t[j - 1] 这个字符于事无补，所以 s[0, i - 1] 也一定不为 t[0, j - 1] 的子序列。

if (s[i - 1] == t[i - 1]) {
  dp[i][j] = dp[i - 1][j - 1]
} else {
  dp[i][j] = dp[i][j - 1]
}

if (s[i - 1] == t[i - 1]) {
  dp[i][j] = dp[i - 1][j - 1];
} else {
  dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 2);
}

if (s[i - 1] == t[i - 1]) {
  dp[i][j] = dp[i - 1][j - 1];
} else {
  dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}

if (s[i - 1] == t[i - 1]) {
  dp[i][j] = dp[i - 1][j - 1];
} else {
  dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
}