动态规划-递归到记忆化搜索

基础DP

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

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

递归

dfs(i)表示从0爬到第i阶楼梯一共有多少种方法。最后一步可以爬1阶或者2阶，则dfs(i)等于dfs(i - 1) 和dfs(i - 2)之和

class Solution {
    public int climbStairs(int n) {
        return dfs(n);
    }

    public int dfs(int i) {
        if (i <= 1) {
            return 1;
        }
        return dfs(i - 1) + dfs(i - 2);
    }
}

dfs 的搜索过程为一颗二叉树，树高为$n$，节点个数为$2^n$，故搜索时间为$O(2^n)$，空间复杂度为$O(n)$，递归需要$O(n)$个栈空间

记忆化搜索

上面的做法会超时，太慢了，可以引入记忆化数组优化

class Solution {
    public int climbStairs(int n) {
        int []memo = new int[n + 1];
        return dfs(n, memo);
    }

    public int dfs(int i, int []memo) {
        if (i <= 1) {
            return 1;
        }
        if (memo[i] != 0) {
            return memo[i];
        }
        return memo[i] = dfs(i - 1, memo) + dfs(i - 2, memo);
    }
}

因为递归是由上至下展开、由下至上收敛的过程。当递归到最小的问题（i <= 1）时，逐步返回计算结果，并将这些结果存储在 memo 数组中。当递归回到较高层级时，已经计算过的结果保存在 memo 中，可以直接访问，避免重复计算。

递推

class Solution {
    public int climbStairs(int n) {
        int[] f = new int[n + 1];
        f[0] = f[1] = 1;
        for (int i = 2; i <= n; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }
        return f[n];
    }
}

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。具体来说，$f[i]$ 的定义和 $dfs(i)$ 的定义是一样的，都表示从 0 爬到 i 有多少种不同的方法。

相应的递推式（状态转移方程）也和 $dfs$ 一样：$f[i]=f[i−1]+f[i−2]$

递推方法的核心在于通过自底向上的迭代计算，避免了递归中的重复计算和函数调用开销，达到了高效解决问题的目的。

当然，转换为三个变量滚动计算这里就不写了

打家劫舍

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

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

示例 1：

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

递归

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        return dfs(n - 1, nums);
    }

    public int dfs(int i, int []nums) {
        if (i < 0) {
            return 0;
        }
        return Math.max(dfs(i - 1, nums), dfs(i - 2, nums) + nums[i]);
    }
}

超时，记忆化搜索

记忆化搜索

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

    public int dfs(int i, int []nums, int[] memo) {
        if (i < 0) {
            return 0;
        }
        if (memo[i] != -1) {
            return memo[i];
        }
        return memo[i] = Math.max(dfs(i - 1, nums, memo), dfs(i - 2, nums, memo) + nums[i]);
    }
}

memo 数组的初始值一定不能等于要记忆化的值！上一题的方案数不可能为0，故没有初始化数组，但是这道题要记忆化的值是金额可以为0，故要初始化数组为-1

递推

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int []f = new int[n + 2];
        for (int i = 0; i < n; ++ i) {
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n + 1];
    }
}//f下标加2，即可避免越界

//换成三个变量滚动，节约空间
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int pre = 0, cur = pre;
        for (int i = 0; i < n; ++ i) {
            int t = Math.max(cur, pre + nums[i]);
            pre = cur;
            cur = t;
        }
        return cur;
    }
}

使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

1
2
3

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。

递归+记忆化搜索

class Solution {
    int []cost; int []memo;
    public int minCostClimbingStairs(int[] cost) {
        this.cost = cost;
        memo = new int[cost.length + 1];
        Arrays.fill(memo, -1);
        return dfs(cost.length);
    }

    public int dfs(int i) {
        if (i <= 1) return 0;
        if (memo[i] != -1) return memo[i];
        return memo[i] = Math.min(dfs(i - 1) + cost[i - 1], dfs(i - 2) + cost[i - 2]);
    }
}

递推

public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int []f = new int[n + 2];
    for (int i = 0; i < n - 1; ++ i) {
        f[i + 2] = Math.min(f[i + 1] + cost[i + 1], f[i] + cost[i]);
    }
    return f[n];
}
//滚动
public int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int pre = 0, cur = pre;
    for (int i = 0; i < n - 1; ++ i) {
        int t = Math.min(cur + cost[i + 1], pre + cost[i]);
        pre = cur;
        cur = t;
    }
    return cur;
}

组合总和 Ⅳ

给你一个由不同整数组成的数组 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)
请注意，顺序不同的序列被视作不同的组合。

dfs + 记忆化搜索

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int []memo = new int[target + 1];
        Arrays.fill(memo, -1);
        return dfs(nums, target, memo);
    }

    public int dfs(int[] nums, int target, int[] memo) {
        if (target < 0) return 0;
        if (target == 0) {
            return 1;
        }
        if (memo[target] != -1) {
            return memo[target];
        }
        int res = 0;
        for (int i : nums) {   
            res += dfs(nums, target - i, memo);
        }
        return memo[target] = res;
    }
}

递推

public int combinationSum4(int[] nums, int target) {
    int n = nums.length;
    int f[] = new int[target + 1];
    f[0] = 1;
    for (int i = 1; i <= target; i ++) {
        for (int x : nums) {
            if (x <= i) {
                f[i] += f[i - x];
            }
        }
    }
    return f[target];
}

统计构造”好”字符串的方案数

递推

public int countGoodStrings(int low, int high, int zero, int one) {
    int f[] = new int[high + 1];
    int mod = 1_000_000_007, ans = 0;
    f[0] = 1;
    for (int i = 1; i <= high; i ++) {
        if (i >= zero) f[i] = (f[i] + f[i - zero]) % mod;
        if (i >= one) f[i] = (f[i] + f[i - one]) % mod;
        if (i >= low) ans = (ans + f[i]) % mod;
    }
    return ans;
}

统计打字方案数

分段 dfs + 记忆化搜索

class Solution {
    final int mod = 1_000_000_007;
    public int countTexts(String pressedKeys) {
        int []index = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4}; //每个号码对应的字符串长度
        long res = 1; //debug半天，res必须为long，不然乘法过程中可能溢出
        int i = 0, n = pressedKeys.length(); 
        while (i < n) {
            int len = 1;
            while (i + 1 < n && pressedKeys.charAt(i) == pressedKeys.charAt(i + 1)) {
                i ++; 
                len ++; //统计每一段相同操作的长度，例如22255中222长度为3
            }
            int []memo = new int[len + 1];
            int s = index[pressedKeys.charAt(i) - '0'];
            res = (res * dfs(s, len, memo)) % mod; //乘法原理，222和55是独立的，分别统计222和55各自的可能，再相乘即为答案
            i ++;
        }
        return (int) res;
    }

    // 常规dfs记忆化搜索
    public int dfs(int s, int len, int []memo) {
        if (len == 0) {
            return 1;
        }
        if (memo[len] != 0) return memo[len];
        long res = 0;
        for (int i = 1; i <= s; i ++) {
            if (len >= i) {
                res = (res + dfs(s, len - i, memo)) % mod;
            }
        }
        return memo[len] = (int) res;
    }
}

删除并获得点数

给你一个整数数组 nums ，你可以对它进行一些操作。

每次操作中，选择任意一个 nums[i] ，删除它并获得 nums[i] 的点数。之后，你必须删除所有等于 nums[i] - 1 和 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 2：

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

dfs + 记忆化搜索

class Solution {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i : nums) {
            mp.put(i, mp.getOrDefault(i, 0) + 1);
            //mp.merge(i, 1, Integer::sum);
        }
        int n = mp.size(), k = 0;
        int []a = new int[n];
        for (int x : mp.keySet()) {
            a[k ++] = x;
        }        
        Arrays.sort(a);
        int []memo = new int[n];
        return dfs(a, n - 1, mp, memo);
    }

    public int dfs(int []a, int i, Map<Integer, Integer> mp, int[]memo) {
        if (i < 0) return 0;
        if (memo[i] != 0) return memo[i];
        int j = i; 
        while (j > 0 && a[j - 1] >= a[i] - 1) -- j;
        return memo[i] = Math.max(dfs(a, i - 1, mp, memo), a[i] * mp.get(a[i]) + dfs(a, j - 1, mp, memo));
    }
}

一个细节：a[j - 1] >= a[i] - 1 和 dfs(a, j - 1, mp, memo) 这里的 j - 1 不能为 j ，否则可能因为 j 未减小导致无限递归。

递推

class Solution {
    public int deleteAndEarn(int[] nums) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i : nums) {
            mp.put(i, mp.getOrDefault(i, 0) + 1);
        }
        int n = mp.size(), k = 0;
        int []a = new int[n];
        for (int x : mp.keySet()) {
            a[k ++] = x;
        }        
        Arrays.sort(a);
        int []f = new int[n + 1];
        int j = 0;
        for (int i = 0; i < n; ++ i) {
            while (a[j] < a[i] - 1) ++ j;
            f[i + 1] = Math.max(f[i], f[j] + a[i] * mp.get(a[i]));
        }
        return f[n];
    }
}

施咒的最大总伤害

一个魔法师有许多不同的咒语。

给你一个数组 power ，其中每个元素表示一个咒语的伤害值，可能会有多个咒语有相同的伤害值。

已知魔法师使用伤害值为 power[i] 的咒语时，他们就不能使用伤害为 power[i] - 2 ，power[i] - 1 ，power[i] + 1 或者 power[i] + 2 的咒语。

每个咒语最多只能被使用一次。

请你返回这个魔法师可以达到的伤害值之和的 最大值 。

dfs + 记忆化搜索

class Solution {
    public long maximumTotalDamage(int[] nums) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i : nums) {
            mp.put(i, mp.getOrDefault(i, 0) + 1); // 去重
        }
        int n = mp.size(), k = 0;
        int []a = new int[n];
        for (int x : mp.keySet()) {
            a[k ++] = x;
        }        
        Arrays.sort(a);  // 排序
        long []memo = new long[n];
        return dfs(a, n - 1, mp, memo);
    }
    public long dfs(int []a, int i, Map<Integer, Integer> mp, long[]memo) {
        if (i < 0) return 0;
        if (memo[i] != 0) return memo[i];
        int j = i; 
        while (j > 0 && a[j - 1] >= a[i] - 2) -- j;  // 找到第一个能使用咒语的位置（第一个小于power[i] - 2的位置）
        return memo[i] = Math.max(dfs(a, i - 1, mp, memo), (long) a[i] * mp.get(a[i]) + dfs(a, j - 1, mp, memo));
    }
}

递推

class Solution {
    public long maximumTotalDamage(int[] nums) {
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i : nums) {
            mp.merge(i, 1, Integer::sum);
        }
        int n = mp.size(), k = 0;
        int []a = new int[n];
        for (int x : mp.keySet()) {
            a[k ++] = x;
        }        
        Arrays.sort(a);
        long []f = new long[n + 1];
        int j = 0;
        for (int i = 0; i < n; ++ i) {
            while (a[j] < a[i] - 2) ++ j;
            f[i + 1] = Math.max(f[i], f[j] + (long) a[i] * mp.get(a[i]));
        }
        return f[n];
    }
}

统计放置房子的方式数

dfs + 记忆化搜索

class Solution {
    final int mod = 1_000_000_007;
    public int countHousePlacements(int n) {
        long []memo = new long[n + 1];
        long res = dfs(n, memo);
        return (int) (res % mod * res % mod) % mod;
    }

    public long dfs (int i, long []memo) {
        if (i == 0) return 1;
        if (i == 1) return 2;
        if (memo[i] != 0) return memo[i];
        return memo[i] = (dfs(i - 1, memo) + dfs(i - 2, memo)) % mod;
    }
}

递推

class Solution {
    final int mod = 1_000_000_007;
    public int countHousePlacements(int n) {
        if (n == 1) return 4;
        long []f = new long[n + 1];
        f[0] = 1;
        f[1] = 2;
        for (int i = 2; i <= n; ++ i) {
            f[i] = (f[i - 1]  + f[i - 2]) % mod;
        }
        return (int) (f[n] % mod * f[n] % mod) % mod;
    }
}

优化空间

class Solution {
    public int countHousePlacements(int n) {
        int mod = 1_000_000_007;
        if (n == 1) return 4;
        long pre = 1, cur = 2;
        for (int i = 1; i < n; i ++) {
            long t = (pre + cur) % mod;
            pre = cur;
            cur = t;
        }
        return (int) (cur % mod * cur % mod) % mod;
    }
}

打家劫舍 II

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

class Solution {
    int []memo;
    public int rob(int[] nums) {
        int n = nums.length;
        memo = new int[n];
        Arrays.fill(memo, -1);
        return Math.max(nums[0] + dfs(nums, 2, n - 2), dfs(nums, 1, n - 1)); //考虑第1间和不考虑第一间
    }

    public int dfs(int []nums, int k, int i) {
        if (i < k) return 0;
        if (memo[i] != -1) return memo[i];
        return Math.max(dfs(nums, k, i - 1), dfs(nums, k, i - 2) + nums[i]);
    }
}

递推（按照上面一比一翻译）

class Solution {
    int []memo;
    public int rob(int[] nums) {
        return Math.max(nums[0] + dfs(nums, 2), dfs(nums, 1));
    }

    public int dfs(int []nums, int start) {
        int n = nums.length;
        int []f = new int[n + 2];
        
        for (int i = start; i < n; i ++) {
            f[i + 2] = Math.max(f[i + 1], f[i] + nums[i]);
        }
        return f[n - start + 2];
    }
}

空间优化

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        return Math.max(nums[0] + dfs(nums, 2, n - 1), dfs(nums, 1, n));
    }

    public int dfs(int []nums, int start, int end) {
        int n = nums.length;
        int pre = 0, cur = pre;
        for (int i = start; i < end; i ++) {
            int t = Math.max(nums[i] + pre, cur);
            pre = cur;
            cur = t;
        }
        return cur;
    }
}

最大子数组和

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

子数组是数组中的一个连续部分。

示例 1：

1
2
3

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

动态规划，空间优化版

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int pre = 0, res = Integer.MIN_VALUE;
    for (int i = 0; i < n; ++ i) {
        pre = Math.max(pre, 0) + nums[i];
        res = Math.max(res, pre);
    }
    return res;
}

前缀和：从前往后遍历过程中维护一个最小的前缀和值，用当前前缀和减去最小前缀和即为可能答案

public int maxSubArray(int[] nums) {
    int n = nums.length;
    int mi = 0, sum = 0, res = Integer.MIN_VALUE;
    for (int i = 0; i < n; ++ i) {
        sum += nums[i];
        res = Math.max(sum - mi, res);
        mi = Math.min(sum, mi);

    }
    return res;
}

找到最大开销的子字符串

先映射，确定字符串s中每一个字符的cost，接下来就是最大子数组和的做法了

public int maximumCostSubstring(String s, String chars, int[] vals) {
    int n = s.length();
    int []mapping = new int[26];
    for (int i = 0; i < 26; ++ i) {
        mapping[i] = i + 1;
    }
    for (int i = 0; i < vals.length; ++ i) {
        mapping[chars.charAt(i) - 'a'] = vals[i];
    }
    int res = 0, pre = 0;
    for (char c : s.toCharArray()) {
        pre = Math.max(pre, 0) + mapping[c - 'a'];
        res = Math.max(res, pre);
    }
    return res;
}

任意子数组和的绝对值的最大值

请你找出 nums 中 和的绝对值 最大的任意子数组（可能为空），并返回该 最大值 。

多维护一个任意子数组的最小值变量mm

public int maxAbsoluteSum(int[] nums) {
    int mm = 0, mx = 0, res = 0, n = nums.length;
    for (int i = 0; i < n; ++ i) {
        mx = Math.max(mx, 0) + nums[i];
        mm = Math.min(mm, 0) + nums[i];
        res = Math.max(Math.max(mx, - mm), res);
    }
    return res;
}

K 次串联后最大子数组之和

给定一个整数数组 arr 和一个整数 k ，通过重复 k 次来修改数组。

例如，如果 arr = [1, 2] ， k = 3 ，那么修改后的数组将是 [1, 2, 1, 2, 1, 2] 。

返回修改后的数组中的最大的子数组之和。注意，子数组长度可以是 0，在这种情况下它的总和也是 0。

由于 结果可能会很大，需要返回的 109 + 7 的模。

别被一个小小的变形吓跑

public int kConcatenationMaxSum(int[] arr, int k) {
    int mod = 1_000_000_007, sum = 0;
    long res;
    for (int i : arr) sum += i;
    res = kadane(arr, 1); // k = 1,直接返回答案
    if (k > 1) {
        res = kadane(arr, 2); // sum <= 0,串联两次res最大
        if (sum > 0) { //只有数组和大于0，串联k次才会使res增大，否则就是串联两次的最大子数组和最大
            res += (long) sum * (k - 2) % mod; //最大子数组和就是在串联两次的数组中间插入k-2个arr
        } 
    }
    return (int) res % mod;
}

public int kadane(int []arr, int k) { //用来计算重复一次或者两次的最大子数组和
    int n = arr.length;
    int pre = 0, res = 0;
    for (int i = 0; i < n * k; i ++) {
        pre = (Math.max(pre, 0) + arr[i % n]);
        res = Math.max(res, pre);
    }
    return res;
}

环形子数组的最大和

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

示例 1：

1
2
3

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

思路：同时维护最小子数组和mi，与最大子数组和mx，以及数组总和sum，sum - mi就是跨过边界的子数组最大和

public int maxSubarraySumCircular(int[] nums) {
    int n = nums.length, pmx = 0, pmi = 0, mx = Integer.MIN_VALUE, mi = Integer.MAX_VALUE;
    int sum = 0;
    for (int i = 0; i < n; ++ i) {
        sum += nums[i];
        pmx = Math.max(pmx, 0) + nums[i];
        pmi = Math.min(pmi, 0) + nums[i];
        mi = Math.min(mi, pmi);
        mx = Math.max(mx, pmx);
    }
    if (mi == sum) return mx; //特殊情况数组全部元素为负，返回mx代表数组中最大的一个负数
    else return Math.max(mx, sum - mi);
}

拼接数组的最大分数

就是求两个数组的差集数组nums2 - nums1的最大子数组和，再加上nums1的和；对于nums2再来一次该操作，最后返回二者最大的即可

public int maximumsSplicedArray(int[] nums1, int[] nums2) {
    int n = nums1.length, sum1 = 0, sum2 = 0;
    for (int i = 0; i < n; ++ i) {
        int t1 = nums1[i], t2 = nums2[i];
        sum1 += t1;
        sum2 += t2;
        nums2[i] = t2 - t1;
        nums1[i] = t1 - t2;
    }

    int mx1 = 0, res1 = 0, mx2 = 0, res2 = 0;
    for (int i : nums1) {
        mx1 = Math.max(mx1 + i, 0) ;
        res1 = Math.max(res1, mx1);
    }
    for (int i : nums2) {
        mx2 = Math.max(mx2 + i, 0);
        res2 = Math.max(res2, mx2);
    }
    return Math.max(sum2 + res1, sum1 + res2);
}

封装成函数

public int maximumsSplicedArray(int[] nums1, int[] nums2) {
    return Math.max(kadane(nums1, nums2), kadane(nums2, nums1));
}

public int kadane(int []nums1, int []nums2) {
    int mx = 0, res = 0, sum = 0;
    for (int i = 0; i < nums1.length; ++ i) {
        sum += nums1[i];
        mx = Math.max(mx + nums2[i] - nums1[i], 0) ;
        res = Math.max(res, mx);
    }
    return res + sum;
}

乘积最大子数组

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

示例 1:

1
2
3

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

思路就是维护一个乘积的最大值 mx 一个最小值 mi，每次遇到负数就交换最大最小值，遇到0就把 mx 和 mi 置为1，计算下一段

public int maxProduct(int[] nums) {
    int n = nums.length, mi = 1, mx = 1, res = Integer.MIN_VALUE;
    for (int i : nums) {
        if (i == 0) {
            mx = 1;
            mi = 1;
            res = Math.max(res, 0);
        } else if (i < 0) {
            int t = mx;
            mx = Math.max(i * mi, i);
            mi = Math.min(i * t, i);
            res = Math.max(res, mx);
        } else {
            mx = Math.max(i * mx, i);
            mi = Math.min(i * mi, i);
            res = Math.max(res, mx);
        }
    }
    return res;
}

网格图DP

珠宝的最高价值

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

只能从架子的左上角开始拿珠宝
每次可以移动到右侧或下侧的相邻位置
到达珠宝架子的右下角时，停止拿取

dfs + 记忆化

class Solution {
    int [][] frame;
    int [][]memo;
    public int jewelleryValue(int[][] frame) {
        this.frame = frame;
        int n = frame.length, m = frame[0].length;
        memo = new int[n][m];
        for (int []a : memo) Arrays.fill(a, -1);
        return dfs(n - 1, m - 1);
    }

    public int dfs(int x, int y) {
        if (x < 0 || y < 0) return 0;
        if (memo[x][y] != -1) return memo[x][y]; // 用 > 0判断也行
        return memo[x][y] = Math.max(dfs(x - 1, y), dfs(x, y - 1)) + frame[x][y];
    }
}

递推

public int jewelleryValue(int[][] frame) {
    int n = frame.length, m = frame[0].length;
    var f = new int[n + 1][m + 1];
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            f[i + 1][j + 1] = Math.max(f[i][j + 1], f[i + 1][j]) + frame[i][j];
        }
    } 
    return f[n][m];
}

空间优化，

public int jewelleryValue(int[][] frame) {
    int n = frame.length, m = frame[0].length;
    var f = new int[2][m + 1];
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            f[(i + 1) % 2][j + 1] = Math.max(f[i % 2][j + 1], f[(i + 1) % 2][j]) + frame[i][j];
        }
    } 
    return f[n % 2][m];
}

public int jewelleryValue(int[][] frame) {
    int n = frame.length, m = frame[0].length;
    var f = new int[m + 1];
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j < m; ++ j) {
            f[j + 1] = Math.max(f[j + 1], f[j]) + frame[i][j];
        }
    } 
    return f[m];
}

不同路径

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

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

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

dfs + memo

public int uniquePaths(int m, int n) {
    int [][]memo = new int[m][n];
    return dfs(m - 1, n - 1, memo);
}

public int dfs(int m, int n, int [][]memo) {
    if (m == 0 || n == 0) return 1;
    if (memo[m][n] > 0) return memo[m][n];
    return memo[m][n] = dfs(m - 1, n, memo) + dfs(m, n - 1, memo);
}

空间优化

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

不同路径 II

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

dfs + memo

class Solution {
    int [][]obstacleGrid;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        this.obstacleGrid = obstacleGrid;
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int [][]memo = new int[m][n];
        return dfs(m - 1, n - 1, memo);
    }

    public int dfs(int x, int y, int [][]memo) {
        if (x >= 0 && y >= 0 && obstacleGrid[x][y] == 1) return 0;
        if (x == 0 && y == 0) return 1;
        if (x < 0 || y < 0) return 0;
        if (memo[x][y] > 0) return memo[x][y];
        return memo[x][y] = dfs(x - 1, y, memo) + dfs(x, y - 1, memo);
    }
}

递推

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) {
                if (i == 0 && j == 0) dp[i][j] = 1;
                else if (i == 0) dp[i][j] = dp[i][j - 1];
                else if (j == 0) dp[i][j] = dp[i - 1][j];
                else 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];
    dp[0] = obstacleGrid[0][0] == 0 ? 1 : 0;
    for (int i = 0; i < m; ++ i) {
        for (int j = 0; j < n; ++ j) {
            if (obstacleGrid[i][j] == 1) {
                dp[j] = 0;
            } else if (j > 0) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n - 1];
}

最小路径和

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

说明：每次只能向下或者向右移动一步。

原地修改

1	3	1		1	4	5
1	5	1	修改后–>	2	7	6
4	2	1		6	8	7

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

三角形最小路径和

dfs + memo

class Solution {
    List<List<Integer>> triangle;
    int n;
    int [][]memo;
    public int minimumTotal(List<List<Integer>> triangle) {
        this.triangle = triangle;
        this.n = triangle.size();
        this.memo = new int[n][n];
        for(int []a : memo) Arrays.fill(a, Integer.MAX_VALUE);
        return dfs(0, 0);
    }

    public int dfs(int r, int c) {    
        if (r == n) return 0;
        if (memo[r][c] != Integer.MAX_VALUE) return memo[r][c];
        return memo[r][c] = Math.min(dfs(r + 1, c), dfs(r + 1, c + 1)) + triangle.get(r).get(c);
    }
}

递推

public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int [][]dp = new int[n + 1][n + 1];
    for (int []a : dp) Arrays.fill(a, Integer.MAX_VALUE);
    dp[0][0] = 0;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j <= i; ++ j) {
            dp[i + 1][j + 1] = Math.min(dp[i][j + 1], dp[i][j]) + triangle.get(i).get(j);
        }
    }
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; ++ i) {
        // System.out.print(dp[n][i]);
        if (dp[n][i + 1] < res) res = dp[n][i + 1];
    }
    return res;
}

空间优化

//自顶向下
public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int []dp = new int[n];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = triangle.get(0).get(0);
    for (int i = 1; i < n; ++ i) {
        for (int j = i; j >= 0; -- j) {
            if (j > 0) {
                dp[j] = Math.min(dp[j], dp[j - 1]) + triangle.get(i).get(j);
            } else {
                dp[j] += triangle.get(i).get(j); 
            }

        }
    }
    int res = Integer.MAX_VALUE;
    for (int i = 0; i < n; ++ i) {
        if (dp[i] < res) res = dp[i];
    }
    return res;
}

//自底向上
public int minimumTotal(List<List<Integer>> triangle) {
    int n = triangle.size();
    int[] dp = new int[n];
    // Initialize dp array with the last row of the triangle
    for (int i = 0; i < n; i++) {
        dp[i] = triangle.get(n - 1).get(i);
    }
    // Start from the second last row and move upwards
    for (int i = n - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
        }
    }
    // The top element of dp array will have the minimum total
    return dp[0];
}

下降路径最小和

dfs + memo

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length, m = matrix[0].length;
        int [][]memo = new int[n][m];
        for (int []a : memo) Arrays.fill(a, Integer.MAX_VALUE);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < m; ++ i) {
            int t = dfs(n - 1, i, matrix, memo);
            if (res > t) res = t;
        }
        return res;
    }

    public int dfs(int x, int y, int [][]matrix, int [][]memo) {
        if (x < 0) return 0;
        if (y < 0 || y >= matrix[0].length) return Integer.MAX_VALUE;
        if (memo[x][y] != Integer.MAX_VALUE) return memo[x][y];
        return memo[x][y] = Math.min(Math.min(dfs(x-1, y, matrix, memo), dfs(x-1, y-1, matrix, memo)), 		                             dfs(x-1, y+1, matrix, memo)) + matrix[x][y];
    } 
}

递推

public int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;  
    int res = Integer.MAX_VALUE;            
    int [][]dp = new int[n][n + 2];
    System.arraycopy(matrix[0], 0, dp[0], 1, n);
    for (int i = 1; i < n; ++ i) {
        dp[i - 1][0] = dp[i - 1][n + 1] = Integer.MAX_VALUE; //左右边界同样初始化为MAX
        for (int j = 1; j <= n; ++ j) {
            dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1])
             + matrix[i][j - 1];
        }
    }
    for (int i = 1; i <= n; ++ i) {
        if (res > dp[n - 1][i]) res = dp[n - 1][i];
    }
    return res;
}

网格中的最小路径代价

题目太复杂，建议去原链接里读

dfs + memo

// 正序遍历
class Solution {
    int [][]grid; int [][]moveCost;
    int m, n;
    public int minPathCost(int[][] grid, int[][] moveCost) {
        this.grid = grid;
        this.moveCost = moveCost;
        this.m = grid.length;
        this.n = grid[0].length;
        int res = Integer.MAX_VALUE;
        int [][]memo = new int[m][n];
        for (int i = 0; i < n; ++ i) {
            int t = dfs(0, i, memo);
            // System.out.print(t + " ");
            if (t < res) res = t;
        }
        return res;
    }

    public int dfs(int x, int y, int [][]memo) {
        if (x == m - 1) return grid[x][y];
        if (memo[x][y] != 0) return memo[x][y];
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < n; ++ i) {
            int t = dfs(x + 1, i, memo) + grid[x][y] + moveCost[grid[x][y]][i];
            res = Math.min(res, t);
        }
        return memo[x][y] = res;
    }
}

递推

// 正序遍历
public int minPathCost(int[][] grid, int[][] moveCost) {
    int m = grid.length;
    int n = grid[0].length;
    int ans = Integer.MAX_VALUE;
    int [][]dp = new int[m][n];
    for (int i = 0; i < n; ++ i) dp[0][i] = grid[0][i];
    for (int i = 1; i < m; ++ i) {
        for (int j = 0; j < n; ++ j) {
            int res = Integer.MAX_VALUE;
            for (int k = 0; k < n; ++ k) {
                int t = dp[i - 1][k] + moveCost[grid[i - 1][k]][j];
                if (res > t) res = t;
            }
            dp[i][j] = grid[i][j] + res;
        }
    }
    for (int i = 0; i < n; ++ i) {
        if (ans > dp[m - 1][i]) ans = dp[m - 1][i];
    }
    return ans;
}

空间优化

//倒序遍历，可以原地修改
public int minPathCost(int[][] grid, int[][] moveCost) {
    int m = grid.length;
    int n = grid[0].length;
    int ans = Integer.MAX_VALUE;
    for (int i = m - 2; i >= 0; -- i) {
        for (int j = 0; j < n; ++ j) {
            int res = Integer.MAX_VALUE;
            for (int k = 0; k < n; ++ k) {
                int t = grid[i + 1][k] + moveCost[grid[i][j]][k];
                if (res > t) res = t;
            }
            grid[i][j] += res;
        }

    }
    for (int i = 0; i < n; ++ i) {
        if (ans > grid[0][i]) ans = grid[0][i];
    }
    return ans;
}

下降路径最小和 II

给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

dfs + memo

class Solution {
    int [][]grid;
    public int minFallingPathSum(int[][] grid) {
        this.grid = grid;
        int res = Integer.MAX_VALUE;
        int [][]memo = new int[grid.length][grid[0].length];
        for (int []a : memo) Arrays.fill(a, Integer.MAX_VALUE);
        for (int i = 0; i < grid[0].length; ++ i) {
            res = Math.min(res, dfs(0, i, memo));
        }
        return res;
    }

    public int dfs(int x, int y, int [][]memo) {
        if (x == grid.length - 1) return grid[x][y];
        if (memo[x][y] != Integer.MAX_VALUE) return memo[x][y];
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < grid[0].length; ++ i) {
            if (i != y) {
                res = Math.min(dfs(x + 1, i, memo) + grid[x][y], res);
            }
        }
        return memo[x][y] = res;
    }
}

递推 + 原地修改

public int minFallingPathSum(int[][] grid) {
    int n = grid.length;
    int ans = Integer.MAX_VALUE;
    int [][]dp = new int[n][n];
    for (int i = n - 2; i >= 0; -- i) {
        for (int j = 0; j < n; ++ j) {
            int res = Integer.MAX_VALUE;
            for (int k = 0; k < n; ++ k) {
                if (k != j) {
                    res = Math.min(res, grid[i+1][k]);
                }
            }
            grid[i][j] += res;
        }
    }
    for (int a : grid[0]) {
        ans = Math.min(ans, a);
    }
    return ans;
}

矩阵的最大非负积

给你一个大小为 m x n 的矩阵 grid 。最初，你位于左上角 (0, 0) ，每一步，你可以在矩阵中向右或向下移动。

在从左上角 (0, 0) 开始到右下角 (m - 1, n - 1) 结束的所有路径中，找出具有 最大非负积 的路径。路径的积是沿路径访问的单元格中所有整数的乘积。

返回 最大非负积 对 109 + 7 取余的结果。如果最大积为负数，则返回 -1 。

注意，取余是在得到最大积之后执行的。

直接上来就动态规划递推解决，但是在两个地方被卡了一个小时

(int) (mx[m - 1][n - 1] % mod) 取模操作优先级低于类型转换，必须加括号
不认真读题，在每一步更新 mx[i][j] 的同时就对其取模，导致后续下一层比较大小时出问题

public int maxProductPath(int[][] grid) {
    int mod = 1_000_000_007;
    int m = grid.length;
    int n = grid[0].length;
    long [][]mx = new long[m + 1][n + 1];
    long [][]mi = new long[m + 1][n + 1];
    mx[0][0] = mi[0][0] = grid[0][0];
    for (int i = 1; i < m; ++ i) {
        mx[i][0] = (mx[i - 1][0] * grid[i][0]);
        mi[i][0] = mx[i][0];
    }
    for (int i = 1; i < n; ++ i) {
        mx[0][i] = (mx[0][i - 1] * grid[0][i]);
        mi[0][i] = mx[0][i];
    }
    for (int i = 1; i < m; ++ i) {
        for (int j = 1; j < n; ++ j) {
            mx[i][j] = (grid[i][j] * Math.max(mx[i][j - 1], mx[i - 1][j]));
            mi[i][j] = (grid[i][j] * Math.min(mi[i][j- 1], mi[i - 1][j]));
            if (grid[i][j] < 0) {
                mx[i][j] = (grid[i][j] * Math.min(mi[i][j - 1], mi[i - 1][j]));
                mi[i][j] = (grid[i][j] * Math.max(mx[i][j - 1], mx[i - 1][j]));
            }
        }
    }
    return mx[m - 1][n - 1] < 0 ? -1 : (int) (mx[m - 1][n - 1] % mod);
}

矩阵中和能被 K 整除的路径

给你一个下标从 0 开始的 m x n 整数矩阵 grid 和一个整数 k 。你从起点 (0, 0) 出发，每一步只能往下或者往右，你想要到达终点 (m - 1, n - 1) 。

请你返回路径和能被 k 整除的路径数目，由于答案可能很大，返回答案对 109 + 7 取余的结果。

dfs + memo，区别在于多考虑一个维度，memo的第三维存 x、y 点当前路径和 s 的状态信息

具体来说， memo[x][y][s] 表示从 (x, y) 开始，路径和对 k 取模为 s 的路径数量。

class Solution {
    final int mod = 1_000_000_007;
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length;
        long [][][]memo = new long[m][n][k];
        for (long [][]a : memo) {
            for (long []b : a) {
                Arrays.fill(b, -1);
            }
        }
        long res = dfs(m - 1, n - 1, grid, k, 0, memo); //正向反向开始都可以
        return (int) (res % mod);
    }

    public long dfs(int x, int y, int [][]grid, int k, int s, long [][][]memo) {
        int m = grid.length, n = grid[0].length;
        if (x < 0 || y < 0) return 0;
        s = (s + grid[x][y]) % k;
        if (x == 0 && y == 0) {
            return s % k == 0 ? 1 : 0;
        }
        if (memo[x][y][s] != -1) return memo[x][y][s];
        return memo[x][y][s] = (dfs(x - 1, y, grid, k, s, memo) + dfs(x, y - 1, grid, k, s, memo)) % mod;
    }
}

递推

class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        int mod = 1_000_000_007;
        int m = grid.length; 
        int n = grid[0].length; 
        
        long[][][] dp = new long[m+1][n+1][k];
     
        dp[0][1][0] = 1;
  
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                for (int r = 0; r < k; ++ r) {
                    dp[i+1][j+1][(r + grid[i][j]) % k] = (dp[i][j + 1][r] + dp[i + 1][j][r]) % mod;
                }
            }
        }
        return (int) (dp[m][n][0] % mod);
    }
}

矩阵中的最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

dfs + memo

class Solution {
    int []dx = new int[]{1, 0, -1, 0};
    int []dy = new int[]{0, 1, 0, -1};
    int [][]matrix;
    int [][]memo;
    int m, n;
    public int longestIncreasingPath(int[][] matrix) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.matrix = matrix;
        memo = new int[m][n];
        int res = 0;
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                int t = dfs(i, j);
                if (t > res) res = t;
            }
        }
        return res;
    }

    public int dfs(int x, int y) {
        if (memo[x][y] != 0) return memo[x][y];
        int t = 1; //初始长度为1
        for (int i = 0; i < 4; ++ i) {
            int x1 = x + dx[i], y1 = y + dy[i];
            if (x1 < 0 || x1 == m || y1 < 0 || y1 == n) continue;
            if (matrix[x1][y1] > matrix[x][y]) {
                t = Math.max(t, 1 + dfs(x1, y1));
            }
        }
        return memo[x][y] = t;
    }
}

网格图中递增路径的数目

给你一个 m x n 的整数网格图 grid ，你可以从一个格子移动到 4 个方向相邻的任意一个格子。

请你返回在网格图中从任意格子出发，达到任意格子，且路径中的数字是 严格递增 的路径数目。由于答案可能会很大，请将结果对 109 + 7 取余后返回。

如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。

dfs + memo 把上道题的代码简单改造一下就好了

class Solution {
    int []dx = new int[]{1, 0, -1, 0};
    int []dy = new int[]{0, 1, 0, -1};
    int [][]matrix;
    int [][]memo;
    int m, n, mod = 1_000_000_007;
    public int countPaths(int[][] matrix) {
        this.m = matrix.length;
        this.n = matrix[0].length;
        this.matrix = matrix;
        memo = new int[m][n];
        long res = 0;
        for (int i = 0; i < m; ++ i) {
            for (int j = 0; j < n; ++ j) {
                res += dfs(i, j);
                res %= mod;
            }
        }
        return (int) res % mod;
    }

    public int dfs(int x, int y) {
        if (memo[x][y] != 0) return memo[x][y];
        int t = 1; //初始长度为1
        for (int i = 0; i < 4; ++ i) {
            int x1 = x + dx[i], y1 = y + dy[i];
            if (x1 < 0 || x1 == m || y1 < 0 || y1 == n) continue;
            if (matrix[x1][y1] > matrix[x][y]) {
                t += dfs(x1, y1);
                t %= mod;
            }
        }
        return memo[x][y] = t;
    }
}

检查是否有合法括号字符串路径

dfs + memo

//抄的
class Solution {
    int m, n;
    char [][]grid;
    boolean [][][]memo;
    public boolean hasValidPath(char[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        memo = new boolean[m][n][(m + n + 1) / 2];
        if (grid[0][0] == ')' || grid[m-1][n-1] == '(' || (m + n) % 2 == 0) return false;
        return dfs(0, 0, 0);
    }
    public boolean dfs(int x, int y, int u) {
        if (u > m - x + n - y - 1) return false; //如果从起点到当前位置的左括号数已经很大，大到从当前位置到结尾全是右括号都无法匹配完
        if (x == m - 1 && y == n - 1) return u == 1; //抵达终点，左括号还剩1个
        if (memo[x][y][u]) return false; 
        memo[x][y][u] = true;
        if (grid[x][y] == '(') {
            ++ u;
        } else {
            -- u;
        }
        return u >= 0 && (x < m - 1 && dfs(x + 1, y, u) || y < n - 1 && dfs(x, y + 1, u));
    }
}

//自己写了个反向的
class Solution {
    int m, n;
    char [][]grid;
    boolean [][][]memo;
    public boolean hasValidPath(char[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        memo = new boolean[m][n][(m + n + 1) / 2];
        if (grid[0][0] == ')' || grid[m - 1][n - 1] == '(' || (m + n) % 2 == 0) return false;
        return dfs(m - 1, n - 1, 0);
    }
    public boolean dfs(int x, int y, int u) {
        if (u > x + y + 1) return false;
        if (x == 0 && y == 0) {
            return u == 1;
        }
        if (memo[x][y][u]) return false;
        memo[x][y][u] = true;
        if (grid[x][y] == ')') {
            ++ u;
        } else {
            -- u;
        }
        return u >= 0 && (x > 0 && dfs(x - 1, y, u) || y > 0 && dfs(x, y - 1, u));
    }
}

扣分后的最大得分

给你一个 m x n 的整数矩阵 points （下标从 0 开始）。一开始你的得分为 0 ，你想最大化从矩阵中得到的分数。

你的得分方式为：每一行 中选取一个格子，选中坐标为 (r, c) 的格子会给你的总得分增加 points[r][c] 。

然而，相邻行之间被选中的格子如果隔得太远，你会失去一些得分。对于相邻行 r 和 r + 1 （其中 0 <= r < m - 1），选中坐标为 (r, c1) 和 (r + 1, c2) 的格子，你的总得分减少 abs(c1 - c2) 。

请你返回你能得到的最大得分。

dfs+memo也会超时

class Solution {
    int m, n;
    int [][]points;
    long [][]memo;
    public long maxPoints(int[][] points) {
        this.m = points.length;
        this.n = points[0].length;
        this.points = points;
        memo = new long[m][n];
        long res = 0;
        for (int i = 0; i < n; ++ i) {
            long t = dfs(m - 1, i);
            if (res < t) res = t;
        }
        return res;
    }

    public long dfs(int x, int y) {
        if (x == 0) return points[x][y];
        if (memo[x][y] != 0) return memo[x][y];
        long t = 0;
        for (int i = 0; i < n; ++ i) {
            long d = dfs(x - 1, i) ;
            d = d + points[x][y] - (i - y < 0 ? y - i : i - y);
            if (t < d) t = d;
        }
        return memo[x][y] = t;
    }
}

上面的时间复杂度是O(m*n^2)，超时，下面优化成O(m*n)

class Solution {
    public long maxPoints(int [][]points) {
        int m = points.length, n = points[0].length;
        long [][]dp = new long[m][n];
        long res = 0;
        for (int j = 0; j < n; ++ j) {
            dp[0][j] = points[0][j];
        }
        for (int i = 1; i < m; ++ i) {
            long []leftMax = new long[n];
            long []rightMax = new long[n];
            leftMax[0] = dp[i - 1][0];
            for (int j = 1; j < n; ++ j) {
                leftMax[j] = Math.max(dp[i - 1][j], leftMax[j - 1] - 1);
            }
            rightMax[n - 1] = dp[i - 1][n - 1];
            for (int j = n - 2; j >= 0; -- j) {
                rightMax[j] = Math.max(dp[i - 1][j], rightMax[j + 1] - 1);
            }
            for (int j = 0; j < n; ++ j) {
                dp[i][j] = points[i][j] + Math.max(leftMax[j], rightMax[j]);
                
            }
        }
        for (int j = 0; j < n; ++ j) {
            if (res < dp[m - 1][j]) res = dp[m - 1][j];
        }
        return res;
    }
}

上面的空间复杂度是O(m*n)，下面优化为滚动数组，空间复杂度O(n)

class Solution {
    public long maxPoints(int [][]points) {
        int m = points.length, n = points[0].length;
        long []pre = new long[n];
        long []cur = new long[n];
        long res = 0;
        for (int i = 0; i < m; ++ i) {
            long max = 0;
            for (int j = 0; j < n; ++ j) {
                max = Math.max(max - 1 , pre[j]);
                cur[j] = max;
            }
            for (int j = n - 1; j >= 0; -- j) {
                cur[j] = Math.max(cur[j], max = Math.max(max - 1, pre[j])) + points[i][j];
            }
            pre = cur;
        }
        for (long t : cur) {
            if (res < t) res = t;
        }
        return res;
    }
}

摘樱桃 II

给你一个 rows x cols 的矩阵 grid 来表示一块樱桃地。 grid 中每个格子的数字表示你能获得的樱桃数目。

你有两个机器人帮你收集樱桃，机器人 1 从左上角格子 (0,0) 出发，机器人 2 从右上角格子 (0, cols-1) 出发。

请你按照如下规则，返回两个机器人能收集的最多樱桃数目：

从格子 (i,j) 出发，机器人可以移动到格子 (i+1, j-1)，(i+1, j) 或者 (i+1, j+1) 。
当一个机器人经过某个格子时，它会把该格子内所有的樱桃都摘走，然后这个位置会变成空格子，即没有樱桃的格子。
当两个机器人同时到达同一个格子时，它们中只有一个可以摘到樱桃。
两个机器人在任意时刻都不能移动到 grid 外面。
两个机器人最后都要到达 grid 最底下一行。

dfs + memo

class Solution {
    int m, n;
    int [][]grid;
    int []dy = new int[]{-1, 0, 1};
    int [][][]memo;
    public int cherryPickup(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        memo = new int[m][n][n];
        for (int [][]a : memo) {
            for (int []b : a) {
                Arrays.fill(b, -1);
            }
        }
        return dfs(0, 0, n - 1);
    }

    public int dfs(int x, int y1, int y2) {
        if (y1 < 0 || y2 < 0 || y1 == n || y2 == n) return 0;
        if (y1 == y2) return grid[x][y1];
        if (x == m - 1) return grid[x][y1] + grid[x][y2];
        if (memo[x][y1][y2] != -1) return memo[x][y1][y2];
        int t = 0;
        for (int i = 0; i < 3; ++ i) {
            for (int j = 0; j < 3; ++ j) {
                t = Math.max(t, dfs(x + 1, y1 + dy[i], y2 + dy[j]));
            }
        }
        return memo[x][y1][y2] = t + grid[x][y1] + grid[x][y2];
    }
}

灵神这个版本好理解一些

class Solution {
    int m, n;
    int [][]grid;
    int []dy = new int[]{-1, 0, 1};
    int [][][]memo;
    public int cherryPickup(int[][] grid) {
        this.grid = grid;
        m = grid.length;
        n = grid[0].length;
        memo = new int[m][n][n];
        for (int [][]a : memo) {
            for (int []b : a) {
                Arrays.fill(b, -1);
            }
        }
        return dfs(0, 0, n - 1);
    }

    public int dfs(int x, int y1, int y2) {
        if (x == m || y1 < 0 || y2 < 0 || y1 == n || y2 == n) return 0;
        if (memo[x][y1][y2] != -1) return memo[x][y1][y2];        
        int t = 0;
        for (int i = 0; i < 3; ++ i) {
            for (int j = 0; j < 3; ++ j) {
                t = Math.max(t, dfs(x + 1, y1 + dy[i], y2 + dy[j]));
            }
        }
        return memo[x][y1][y2] = t + (y1 == y2 ? grid[x][y1] : grid[x][y1] + grid[x][y2]);
    }
}

摘樱桃

给你一个 n x n 的网格 grid ，代表一块樱桃地，每个格子由以下三种数字的一种来表示：

0 表示这个格子是空的，所以你可以穿过它。
1 表示这个格子里装着一个樱桃，你可以摘到樱桃然后穿过它。
-1 表示这个格子里有荆棘，挡着你的路。

请你统计并返回：在遵守下列规则的情况下，能摘到的最多樱桃数：

从位置 (0, 0) 出发，最后到达 (n - 1, n - 1) ，只能向下或向右走，并且只能穿越有效的格子（即只可以穿过值为 0 或者 1 的格子）；
当到达 (n - 1, n - 1) 后，你要继续走，直到返回到 (0, 0) ，只能向上或向左走，并且只能穿越有效的格子；
当你经过一个格子且这个格子包含一个樱桃时，你将摘到樱桃并且这个格子会变成空的（值变为 0 ）；
如果在 (0, 0) 和 (n - 1, n - 1) 之间不存在一条可经过的路径，则无法摘到任何一个樱桃。

dfs + memo

public class Solution {
    int n;
    int[][] grid;
    int[][][][] memo;

    public int cherryPickup(int[][] grid) {
        this.grid = grid;
        n = grid.length;
        memo = new int[n][n][n][n];
        for (int[][][] a : memo) {
            for (int[][] b : a) {
                for (int[] c : b)
                    Arrays.fill(c, -1);
            }
        }
        int t = dfs(0, 0, 0, 0);
        return t < 0 ? 0 : t;
    }

    public int dfs(int x1, int y1, int x2, int y2) {
        if (x1 == n || y1 == n || x2 == n || y2 == n || grid[x1][y1] == -1 || grid[x2][y2] == -1) return Integer.MIN_VALUE; // 如果碰到障碍或者越界返回最小值
        if (x1 == n - 1 && y1 == n - 1)
            return grid[x1][y1]; // 如果到达终点返回终点的樱桃数
        if (memo[x1][y1][x2][y2] != -1) return memo[x1][y1][x2][y2];
        int res = Math.max(
            Math.max(dfs(x1 + 1, y1, x2 + 1, y2), dfs(x1 + 1, y1, x2, y2 + 1)),
            Math.max(dfs(x1, y1 + 1, x2 + 1, y2), dfs(x1, y1 + 1, x2, y2 + 1))
        ) + grid[x1][y1] + (x1 == x2 && y1 == y2 ? 0 : grid[x2][y2]);
        return memo[x1][y1][x2][y2] = res;
    }

}

灵神，减少到三个状态表示，t：每个人走的总步数，j：第一个人走到的纵坐标，k：第二个人走到的纵坐标

import java.util.Arrays;

public class Solution {
    int n;
    int[][] grid;
    int[][][] memo;

    public int cherryPickup(int[][] grid) {
        this.grid = grid;
        n = grid.length;
        memo = new int[2 * n - 1][n][n];
        for (int[][] a : memo) {
            for (int[] b : a) {
                Arrays.fill(b, -1);
            }
        }
        int t = dfs(0, 0, 0);
        return t < 0 ? 0 : t;
    }

    public int dfs(int t, int j, int k) {
        if (j == n || k == n || t - j == n || t - k == n || grid[t - j][j] == -1 || grid[t - k][k] == -1) return Integer.MIN_VALUE;
        if (t == 2 * n - 2) return grid[n - 1][n - 1]; 
        if (memo[t][j][k] != -1) return memo[t][j][k];
        int res = Math.max(
            Math.max(dfs(t + 1, j + 1, k), dfs(t + 1, j, k + 1)),
            Math.max(dfs(t + 1, j + 1, k + 1), dfs(t + 1, j, k)))
            + grid[t - j][j] + (j == k ? 0 : grid[t - k][k]);
        return memo[t][j][k] = res;
    }

}

0-1背包

目标和

给你一个非负整数数组 nums 和一个整数 target 。

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

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

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

dfs + memo: 假设要凑成target，需要添加+号的所有数的和为p，则需要添加负号的为sum(nums) - p，target = p + (p - s)

解得p = (s + target) / 2，因此 s + target 小于0以及为奇数均不合法，题目转化为从n个数组元素中选取元素刚好填满容量为p的背包

class Solution {
    // p: 添加+号的部分的和，q: 添加-号的部分的和
    // p + q = sum
    // p - q = t
    // sum + t = 2 * p
    // sum - t = 2 * q
    // p = (sum + t) / 2
    int []nums;
    public int findTargetSumWays(int[] nums, int target) {
        this.nums = nums;
        int sum = Arrays.stream(nums).sum();
        target += sum;
        if (target < 0 || target % 2 != 0) return 0;
        int n = nums.length;
        target /= 2;
        int [][]memo = new int[n][target + 1];
        return dfs(n - 1, target, memo);
    }

    public int dfs(int i, int c, int [][]memo) {
        if (i < 0) { // 没有元素可选，检查背包是否刚好填满
            if (c == 0) return 1; // 刚好填满，方案数 +1
            else return 0;
        }
        if (memo[i][c] > 0) return memo[i][c]; 
        if (c < nums[i]) return memo[i][c] = dfs(i - 1, c, memo);// 容量小于当前元素体积，不能选
        return memo[i][c] = (dfs(i - 1, c, memo) + dfs(i - 1, c - nums[i], memo));// 总方案数为选与不选当前元素的方案数之和
    }
}

递推

public int findTargetSumWays(int[] nums, int target) {
    int sum = Arrays.stream(nums).sum();
    target += sum;
    if (target < 0 || target % 2 != 0) return 0;
    int n = nums.length;
    target /= 2;
    int [][]f = new int[n + 1][target + 1];
    f[0][0] = 1;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j <= target; ++ j) {
            if (j >= nums[i]) {
                f[i + 1][j] = f[i][j] + f[i][j - nums[i]];
            } else {
                f[i + 1][j] = f[i][j];
            }
        }
    }
    return f[n][target];
}

空间优化，倒着枚举

public int findTargetSumWays(int[] nums, int target) {
    int sum = Arrays.stream(nums).sum();
    target += sum;
    if (target < 0 || target % 2 != 0) return 0;
    int n = nums.length;
    target /= 2;
    int []f = new int[target + 1];
    f[0] = 1;
    for (int x : nums) {
        for (int j = target; j >= x; -- j) {
            f[j] = f[j] + f[j - x];
        }
    }
    return f[target];
}

分割等和子集

给你一个 只包含正整数 的非空数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

dfs + memo，最初把memo数组设为boolean，只有两种状态，无法表示是还未访问到还是访问到了但是结果为false

故使用Integer数组，初始为null表示还未被访问，1表示true，0表示false

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        sum /= 2;
        Integer [][]memo = new Integer[n][sum + 1];
        return dfs(nums, memo, sum, 0);
    }

    public boolean dfs(int []nums, Integer [][]memo, int sum, int u) {
        int n = nums.length;
        if (sum == 0) return true;
        if (u == n || sum < 0) {
            return false;
        }
        if (memo[u][sum] != null) return memo[u][sum] == 1;
        boolean result = dfs(nums, memo, sum, u + 1) || dfs(nums, memo, sum - nums[u], u + 1);
        memo[u][sum] = result ? 1 : 0;
        return result;
    }
}

递推，空间优化，逆序遍历。

为什么逆序？正序的话，因为是用到背包容量 j 减去当前物品体积 i 的状态，是在 j 之前就更新过了的，所以会出错，因为用到新值了，我们要用的是上一层的旧值。逆序就不会出现这种问题，你细想。

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        sum /= 2;
        boolean []dp = new boolean[sum + 1];
        dp[0] = true;
        for (int i : nums) {
            for (int j = sum; j >= i; -- j) {
                dp[j] = dp[j] || dp[j - i];
            }
        }
        return dp[sum];
    }
}

和为目标值的最长子序列的长度

给你一个下标从 0 开始的整数数组 nums 和一个整数 target 。

返回和为 target 的 nums 子序列中，子序列 长度的最大值 。如果不存在和为 target 的子序列，返回 -1 。

子序列 指的是从原数组中删除一些或者不删除任何元素后，剩余元素保持原来的顺序构成的数组。

示例 1：

1
2
3

输入：nums = [1,2,3,4,5], target = 9
输出：3
解释：总共有 3 个子序列的和为 9 ：[4,5] ，[1,3,5] 和 [2,3,4] 。最长的子序列是 [1,3,5] 和 [2,3,4] 。所以答案为 3 。

dfs + memo

class Solution {
    int[][] memo; 
    public int lengthOfLongestSubsequence(List<Integer> nums, int target) {
        int n = nums.size();
        memo = new int[n][target + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        int t = dfs(nums, n - 1, target);
        return t < 0 ? -1 : t;
    }

    //前i个元素和为target的子序列长度的最大值
    public int dfs(List<Integer> nums, int i, int target) {
        if (target == 0) return 0; // 找到一个合法的子序列
        if (i < 0) return Integer.MIN_VALUE / 2; // 没有更多元素可选
        if (memo[i][target] != -1) {
            return memo[i][target];
        }
        int t = nums.get(i);
        if (target < t) {
            return memo[i][target] = dfs(nums, i - 1, target);
        }
        return memo[i][target] = Math.max(dfs(nums, i - 1, target), dfs(nums, i - 1, target - t) + 1);
    }
}

将一个数字表示成幂的和的方案数

给你两个正整数 n 和 x 。

请你返回将 n 表示成一些 互不相同 正整数的 x 次幂之和的方案数。换句话说，你需要返回互不相同整数 [n1, n2, ..., nk] 的集合数目，满足 n = n1x + n2x + ... + nkx 。

由于答案可能非常大，请你将它对 109 + 7 取余后返回。

比方说，n = 160 且 x = 3 ，一个表示 n 的方法是 n = 23 + 33 + 53 。

递推：越来越熟练了

class Solution {
    public int numberOfWays(int n, int x) {
        int mod = 1_000_000_007;
        int m = (int) Math.pow(n, 1d / x) + 1; //物品就从1-m中选，代表的是物品的体积，背包容量是n
        long []dp = new long[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= m; ++ i) {
            int t = (int) Math.pow(i, x);
            for (int j = n; j >= t; -- j) { 
                dp[j] = dp[j] + dp[j - t];
            }
        }
        return (int) (dp[n] % mod);
    }
}

执行操作可获得的最大总奖励 I

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是 未标记 的。你可以执行以下操作 任意次 ：

从区间 [0, n - 1] 中选择一个 未标记 的下标 i。
如果 rewardValues[i] 大于你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并标记下标 i。

以整数形式返回执行最优操作能够获得的最大总奖励。

这道题太抽象了，建议多思考思考怎么抽象成01背包的

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        int n = rewardValues.length;
        Arrays.sort(rewardValues);
        int s = rewardValues[n - 1] * 2;//最大价值不会超过最大reward的二倍，因为如果最大reward能选，那前面的所有和就应该小于最大reward。
        boolean dp[] = new boolean[s + 1];//背包容量就应该初始化为这个“可能”的最大价值，而答案就应该是dp数组为true的最大下标，也就是能达到的最大价值
        dp[0] = true;
        for (int i = 0; i < n; ++ i) {
            int t = rewardValues[i];
            for (int j = s; j >= t; -- j) {
                if (j < 2 * t) { //比普通的01背包多了一个判断，根据题意：如果t大于你当前的总奖励x才能选，选了t的状态就是从j-t这个价值的状态转移过来，x=j-t，t>j-t, j<2*t。不选t的状态就是dp[j]
                    dp[j] = dp[j] || dp[j - t];
                }
            }
        }
        int res = 0;
        for (int j = 0; j <= s; ++ j) {
            if (dp[j]) res = j;
        }
        return res;
    }
}

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1 。

示例 1：

输入：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 。

二维，背包有两个

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int s = strs.length;
        int [][][]dp = new int[s + 1][m + 1][n + 1];
        dp[0][0][0] = 0;
        for (int i = 0; i < s; ++ i) {
            int zero = 0, one = 0;
            for (char c : strs[i].toCharArray()) {
                if (c == '1') one ++;
                else zero ++;
            }
            for (int j = 0; j <= m; ++ j) {
                for (int k = 0; k <= n; ++ k) {
                    dp[i + 1][j][k] = dp[i][j][k];
                    if (zero <= j && one <= k) {
                        dp[i + 1][j][k] = Math.max(dp[i][j][k], dp[i][j - zero][k - one] + 1);
                    }
                }
            }
        }
        return dp[s][m][n];
    }
}

优化

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int s = strs.length;
        int [][]dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        for (int i = 0; i < s; ++ i) {
            int zero = 0, one = 0;
            for (char c : strs[i].toCharArray()) {
                if (c == '1') one ++;
                else zero ++;
            }
            for (int j = m; j >= zero; -- j) {
                for (int k = n; k >= one; -- k) {
                    dp[j][k] = Math.max(dp[j][k], dp[j - zero][k - one] + 1);
                }
            }
        }
        return dp[m][n];
    }
}

最后一块石头的重量 II

有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

怎么转化为01背包？你真是一个一点就通的天才少年

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = Arrays.stream(stones).sum();
        int t = sum / 2;
        int n = stones.length;
        boolean []dp = new boolean[t + 1];
        dp[0] = true;
        for (int s : stones) {
            for (int j = t; j >= s; -- j) {
                dp[j] = dp[j] || dp[j - s];
            }
        }
        int i;
        for (i = t; i >= 0; -- i) {
            if (dp[i]) break;
        }
        return (sum - i) > i ? sum - 2 * i : 2 * i - sum;
    }
}

最高的广告牌

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。

返回 广告牌的最大可能安装高度 。如果没法安装广告牌，请返回 0 。

class Solution {
    int [][]memo;
    int sum;
    public int tallestBillboard(int[] rods) {
        int n = rods.length;
        sum = Arrays.stream(rods).sum();
        memo = new int[n][sum + 1];
        for (int []a : memo) Arrays.fill(a, -1);
        return dfs(rods, n - 1, 0) / 2;
    }

    //前i个支架(包含i)高度差为j时的最大高度和
    public int dfs(int []rods, int i, int j) {// i:前i个支架，j：高度差
        if (j > sum) {
            return Integer.MIN_VALUE;
        }
        if (i == 0) {
            if (rods[i] == j) return j;
            if (j == 0) return 0;
            return Integer.MIN_VALUE;
        }
        if (memo[i][j] != -1) return memo[i][j];
        int d = 0;
        int t1 = dfs(rods, i - 1, j);
        int t2 = dfs(rods, i - 1, j + rods[i]) + rods[i];
        int t3 = dfs(rods, i - 1, Math.abs(j - rods[i])) + rods[i];
        return memo[i][j] = Math.max(Math.max(t1, t2), t3);
    }
}

class Solution {
    public int tallestBillboard(int[] rods) {
        int n = rods.length;
        int sum = Arrays.stream(rods).sum();
        int [][]dp = new int[n + 1][sum + 1];
        for (int i = 0; i <= n; ++i) {
            Arrays.fill(dp[i], Integer.MIN_VALUE);
        }
        dp[0][0] = 0;
        int d = 0;
        for (int i = 0; i < n; ++ i) {
            d += rods[i];
            for (int j = 0; j <= d; ++ j) {    
                if (rods[i] + j <= sum) {
                     dp[i + 1][j] = Math.max(dp[i][j], Math.max(dp[i][Math.abs(rods[i] - j)], dp[i][rods[i] + j]) + rods[i]);
            	}
        	}      
        }
        return dp[n][0] / 2;
    }
}

盈利计划

集团里有 n 名员工，他们可以完成各种各样的工作创造利润。

第 i 种工作会产生 profit[i] 的利润，它要求 group[i] 名成员共同参与。如果成员参与了其中一项工作，就不能参与另一项工作。

工作的任何至少产生 minProfit 利润的子集称为 盈利计划 。并且工作的成员总数最多为 n 。

有多少种计划可以选择？因为答案很大，所以 返回结果模 10^9 + 7 的值。

dfs + memo

class Solution {
    int[][][] memo;
    int []group;
    int []profit;
    int mod = 1_000_000_007;
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int m = group.length;
        this.group = group;
        this.profit = profit;
        memo = new int[m][n + 1][minProfit + 1];
        for (int[][] a : memo) {
            for (int[] b : a) {
                Arrays.fill(b, -1);
            }
        }
        return dfs(m - 1, n, minProfit) % mod;
    }

    //前i个工作，前j个员工，产生k的利润的方案数
    public int dfs(int i, int j, int k) {
        if (j < 0) return 0; //没有员工可选，不管多少个工作都产生不了利润
        if (i < 0) { //没有工作可选
            if (k == 0) return 1; //产生0的利润有一个方案
            else return 0;
        }
        if (memo[i][j][k] != -1) return memo[i][j][k];
        int gro = group[i], pro = profit[i];
        return memo[i][j][k] = (dfs(i - 1, j, k) + dfs(i - 1, j - gro, Math.max(0, k - pro))) % mod;
    }
}

递推

class Solution {
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int m = group.length, p = profit.length, mod = 1_000_000_007;
        int [][][]dp = new int[m + 1][n + 1][minProfit + 1];//前i种工作，前j个员工，至少产生k的利润的方案数
        for (int j = 0; j <= n; ++ j) dp[0][j][0] = 1;
        for (int i = 0; i < m; ++ i) { //工作
            int rs = group[i], lr = profit[i];
            for (int j = 0; j <= n; ++ j) { //人数
                for (int k = 0; k <= minProfit; ++ k) { //利润
                    if (j < rs) {
                        dp[i + 1][j][k] = dp[i][j][k];
                    } else {
                        dp[i + 1][j][k] = (dp[i][j][k] + dp[i][j - rs][Math.max(0, k - lr)]) % mod;
                    }
                }
            }
        }
        return dp[m][n][minProfit];
    }
}

空间优化

class Solution {

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int m = group.length, p = profit.length, mod = 1_000_000_007;
        int [][]dp = new int[n + 1][minProfit + 1];//前i种工作，前j个员工，至少产生k的利润的方案数
        for (int j = 0; j <= n; ++ j) dp[j][0] = 1;
        for (int i = 0; i < m; ++ i) { //工作
            int rs = group[i], lr = profit[i];
            for (int j = n; j >= rs; -- j) { //人数
                for (int k = 0; k <= minProfit; ++ k) { //利润
                    dp[j][k] = (dp[j][k] + dp[j - rs][Math.max(0, k - lr)]) % mod;
                }
            }
        }
        return dp[n][minProfit];
    }
}

求出所有子序列的能量和

给你一个长度为 n 的整数数组 nums 和一个正整数 k 。

一个整数数组的能量定义为和等于 k 的子序列的数目。

请你返回 nums 中所有子序列的 能量和 。

由于答案可能很大，请你将它对 109 + 7 取余后返回。

dp(i，j，k)表示前i个数中长度为j且和为k的子序列的数目

class Solution {
    public int sumOfPower(int[] nums, int s) {
        int n = nums.length, mod = 1_000_000_007;
        int [][][]dp = new int[n + 1][n + 1][s + 1];//前i个数中长度为j和为k的子序列的能量
        dp[0][0][0] = 1;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j <= i + 1; ++ j) {
                for (int k = 0; k <= s; ++ k) {
                    if (nums[i] > k) { //不能选第i个数
                        dp[i + 1][j][k] = dp[i][j][k];
                    } else if (j > 0) {
                        dp[i + 1][j][k] = (dp[i][j][k] + dp[i][j - 1][k - nums[i]]) % mod;
                    }
                }
            }
        }
        long res = 0;
        for (int j = 1; j <= n; ++ j) { //枚举每一个长度j中和等于s的子序列的数目,该长度的子序列对答案的贡献为：数目 * 2^(n-j)
            res += Math.pow(2, n - j) * dp[n][j][s] % mod;
        }
        return (int) (res % mod);
    }

}

空间优化

class Solution {
    public int sumOfPower(int[] nums, int s) {
        int n = nums.length, mod = 1_000_000_007;
        int [][]dp = new int[n + 1][s + 1];//前i个数中长度为j和为k的子序列的个数
        dp[0][0] = 1;
        for (int i = 0; i < n; ++ i) {
            for (int j = i + 1; j > 0; -- j) {
                for (int k = s; k >= nums[i]; -- k) {
                    dp[j][k] = (dp[j][k] + dp[j - 1][k - nums[i]]) % mod;
                }
            }
        }
        long res = 0;
        for (int j = 0; j <= n; ++ j) {
            res += Math.pow(2, n - j) * dp[j][s] % mod;
        }
        return (int) (res % mod);
    }
}

另一种定义

dp(i, j)表示前i个元素，从中选出的子序列和为j时的能量和

class Solution {
    public int sumOfPower(int[] nums, int k) {
        int n = nums.length, mod = 1_000_000_007;
        int [][]dp = new int[n + 1][k + 1];//前i个元素，从中选出的子序列和为j时的能量和
        dp[0][0] = 1;
        for (int i = 0; i < n; ++ i) {
            for (int j = k; j >= 0; -- j) {
                dp[i + 1][j] = dp[i][j] * 2 % mod;
                if (j >= nums[i]) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - nums[i]]) % mod;
                }
            }
        }
        return dp[n][k];
    }
}

好分区的数目

给你一个正整数数组 nums 和一个整数 k 。

分区的定义是：将数组划分成两个有序的组，并满足每个元素恰好存在于 某一个 组中。如果分区中每个组的元素和都大于等于 k ，则认为分区是一个好分区。

返回不同的好分区的数目。由于答案可能很大，请返回对 109 + 7 取余后的结果。

如果在两个分区中，存在某个元素 nums[i] 被分在不同的组中，则认为这两个分区不同。

dfs + memo; 和大于等于k，不太好用背包，转化为求和小于k的分区数

class Solution {
    private static final int  mod = 1_000_000_007;
    public int countPartitions(int[] nums, int s) {
        long sum = 0;
        for (int num : nums) {//妈的用stream流只支持int类型，会爆int
            sum += num;
        }//long sum = Arrays.stream(nums).mapToLong(o -> (long) o).sum();可以这样,但是没for快
        int n = nums.length;
        if (sum / 2 < s) return 0;
        long [][]memo = new long[n + 1][s + 1];
        for (long []a : memo) Arrays.fill(a, -1);
        long res = (dfs(nums, memo, n - 1, s)) % mod;
        long total = 1L;
        for (int i = 0; i < n; ++ i) {//妈的用Math.pow也会爆，得用快速幂
            total = (total * 2) % mod;
        }
        return (int) ((total - 2 * res + mod) % mod);//妈的不多加一个mod又会减成负数
    }

    //前i个数中,选出和小于k的组合个数
    public long dfs(int []nums, long [][]memo, int i, int k) {
        if (i < 0) return k > 0 ? 1 : 0;
        if (memo[i][k] != -1) return memo[i][k];
        long res = dfs(nums, memo, i - 1, k);
        if (k > nums[i]) {
            res = (res + dfs(nums, memo, i - 1, k - nums[i])) % mod;
        }
        return memo[i][k] = res;
    }
}

递推

class Solution {
    private static final int  mod = 1_000_000_007;
    public int countPartitions(int[] nums, int s) {
        long sum = Arrays.stream(nums).mapToLong(o -> (long) o).sum();
        int n = nums.length;
        if (sum / 2 < s) return 0;
        long [][]dp = new long[n + 1][s + 1];//从前i个数中选择若干元素，和为j的分区数，所以j小于s，表示坏分区
        dp[0][0] = 1;
        long ans = 1L;
        for (int i = 0; i < n; ++ i) {
            ans = ans * 2 % mod;
            for (int j = 0; j < s; ++ j) {
                dp[i + 1][j] = dp[i][j];
                if (j >= nums[i]) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - nums[i]]) % mod;
                }
            }
        }
        long res = 0L;
        for (int i = 0; i < s; ++ i) {
            res = (res + dp[n][i]) % mod;
        }
        return (int) (ans - res * 2 % mod + mod) % mod;
    }
}

空间优化

class Solution {
    private static final int  mod = 1_000_000_007;
    public int countPartitions(int[] nums, int s) {
        long sum = Arrays.stream(nums).mapToLong(o -> (long) o).sum();
        int n = nums.length;
        if (sum / 2 < s) return 0;
        long []dp = new long[s + 1];//从前i个数中选择若干元素，和为j的分区数，所以j小于s，表示坏分区
        dp[0] = 1L;
        long ans = 1L;
        for (int i = 0; i < n; ++ i) {
            ans = ans * 2 % mod;
            for (int j = s - 1; j >= nums[i]; -- j) {
                dp[j] = (dp[j] + dp[j - nums[i]]) % mod;
            }
        }
        long res = 0L;
        for (int i = 0; i < s; ++ i) {
            res = (res + dp[i]) % mod;
        }
        return (int) (ans - res * 2 % mod + mod) % mod;
    }
}

完全背包

零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

dfs + memo

class Solution {
    int [][]memo;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        memo = new int[n][amount + 1];
        for (int []a : memo) Arrays.fill(a, -1);
        int t = dfs(coins, amount, n - 1);
        return t >= Integer.MAX_VALUE / 2 ? -1 : t;
    }

    public int dfs(int []coins, int amount, int u) {
        if (u < 0) {
            if (amount == 0) return 0;
            else return Integer.MAX_VALUE / 2;
        }
        if (memo[u][amount] != -1) return memo[u][amount];
        int res = dfs(coins, amount, u - 1);
        if (amount >= coins[u]) {
            res = Math.min(res, dfs(coins, amount - coins[u], u) + 1);
        }   
        return memo[u][amount] = res;
    }
}

递推

class Solution {
    int [][]dp;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        dp = new int[n + 1][amount + 1];
        Arrays.fill(dp[0], Integer.MAX_VALUE / 2);
        dp[0][0] = 0;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j <= amount; ++ j) {
                dp[i + 1][j] = dp[i][j];
                if (j >= coins[i]) {
                    dp[i + 1][j] = Math.min(dp[i][j], dp[i + 1][j - coins[i]] + 1);
                }
            }
        }
        return dp[n][amount] == Integer.MAX_VALUE / 2 ? -1 : dp[n][amount];
    }
}
// 1 2 3 4 5
// 1 2 3 4 5

空间优化，正序

class Solution {
    int []dp;
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        for (int i : coins) {
            for (int j = i; j <= amount; ++ j) {
                dp[j] = Math.min(dp[j], dp[j - i] + 1);
            }
        }
        return dp[amount] == Integer.MAX_VALUE / 2 ? -1 : dp[amount];
    }
}

零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

class Solution {
    int [][]memo;
    public int change(int amount, int[] coins) {
        int n = coins.length;
        memo = new int[n][amount + 1];
        for (int []a : memo) Arrays.fill(a, -1);
        return dfs(coins, amount, n - 1);
    }

    public int dfs(int []coins, int amount, int u) {
        if (u < 0) {
            if (amount == 0) return 1;
            else return 0;
        }
        if (memo[u][amount] != -1) return memo[u][amount];
        int res = dfs(coins, amount, u - 1);
        if (amount >= coins[u]) {
            res += dfs(coins, amount - coins[u], u);
        }   
        return memo[u][amount] = res;
    }
}

class Solution {
    int []dp;
    public int change(int amount, int[] coins) {
        int n = coins.length;
        dp = new int[amount + 1];
        dp[0] = 1;
        for (int i : coins) {
            for (int j = i; j <= amount; ++ j) {
                dp[j] += dp[j - i];
            }
        }
        return dp[amount];
    }
}

完全平方数

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {
    int [][]memo;
    public int numSquares(int n) {
        int t = (int) Math.sqrt(n);
        memo = new int[t + 1][n + 1];
        for (int []a : memo) Arrays.fill(a, -1);
        return dfs(t, n);
    }
    //n = 11, sqrt = 3,只有1,2,3的完全平方数能参与凑11的过程中
    //1-t中他们的完全平方数凑够n的最小数量
    public int dfs(int t, int n) {
        if (t < 1) {
            if (n == 0) return 0;
            else return Integer.MAX_VALUE / 2;
        }
        if (memo[t][n] != -1) return memo[t][n];
        int res = dfs(t - 1, n);
        if (n >= t * t) {
            res = Math.min(res, dfs(t, n - t * t) + 1);
        }   
        return memo[t][n] = res;
    }
}

class Solution {
    int []dp;
    public int numSquares(int n) {
        dp = new int[n + 1];
        int t = (int) Math.sqrt(n);
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;
        for (int i = 1; i <= t; ++ i) {
            for (int j = i * i; j <= n; j ++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}

数位成本和为目标值的最大数字

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的最大整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

dfs + memo,先通过dfs枚举最长答案（完全背包）最长的字符串一定是最大的整数，接着使用dfs记录下的转移信息，倒着枚举数字，找出最长的字符串。

class Solution {
    int [][]memo;
    public String largestNumber(int[] cost, int target) {
        int n = cost.length;
        memo = new int[n + 1][target + 1];
        for (int []a : memo) Arrays.fill(a, -1);
        int result = dfs(n - 1, cost, target);
        String res = "";
        if (result < 0) {
            return "0";
        }
        for (int i = 9, j = target; i >= 1; -- i) {
            int u = cost[i - 1];
            while (j >= u && memo[i - 1][j] == memo[i - 1][j - u] + 1) {
                res += String.valueOf(i);
                j -= u;
            }
        }
        return res;
    }

    public int dfs(int i, int[] cost, int target) {
        if (i < 0) {
            if (target == 0) return 0;
            else return Integer.MIN_VALUE;
        }
        if (memo[i][target] != -1) return memo[i][target];
        int res = dfs(i - 1, cost, target);
        if (target >= cost[i]) {
            res = Math.max(res, dfs(i, cost, target - cost[i]) + 1);
        }
        return memo[i][target] = res;
    }
}

分组背包

掷骰子等于目标和的方法数

这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。

给定三个整数 n、k 和 target，请返回投掷骰子的所有可能得到的结果（共有 kn 种方式），使得骰子面朝上的数字总和等于 target。

由于答案可能很大，你需要对 109 + 7 取模。

dfs + memo

class Solution {
    private int mod = 1_000_000_007;
    int [][][]memo;
    public int numRollsToTarget(int n, int k, int target) {
        memo = new int[n + 1][k + 1][target + 1];
        for (int [][]a : memo) {
            for (int []b : a) Arrays.fill(b, -1);
        }
        return dfs(n, k, target) % mod;
    }

    public int dfs(int n, int k, int target) {
        if (n == 0) return target == 0 ? 1 : 0;
        if (memo[n][k][target] != -1) return memo[n][k][target];
        int res = 0;
        for (int i = 1; i <= k; ++ i) {
            if (target >= i) {
                res = (res + dfs(n - 1, k, target - i)) % mod;
            }
        }
        return memo[n][k][target] = res;
    }
}

递推

class Solution {
    private int mod = 1_000_000_007;
    int [][]memo;
    public int numRollsToTarget(int n, int k, int target) {
        if (target < n || target > n * k) {
            return 0; // 无法组成 target
        }
        memo = new int[n + 1][target + 1];
        memo[0][0] = 1;
        for (int i = 0; i < n; ++ i) {
            for (int l = 0; l <= target; ++ l) {
                int res = 0;
                for (int j = 1; j <= k; ++ j) {
                    if (l >= j) {
                        res = (res + memo[i][l - j]) % mod;
                    }
                }
                memo[i + 1][l] = res;
            }
        }
        return memo[n][target] % mod;
    }
}

空间优化

class Solution {
    private int mod = 1_000_000_007;
    int []memo;
    public int numRollsToTarget(int n, int k, int target) {
        if (target < n || target > n * k) {
            return 0; // 无法组成 target
        }
        memo = new int[target + 1];
        memo[0] = 1;
        for (int i = 0; i < n; ++ i) {
            for (int l = target; l >= 0; -- l) {
                int res = 0;
                for (int j = 1; j <= k; ++ j) {
                    if (l >= j) {
                        res = (res + memo[l - j]) % mod;
                    }
                }
                memo[l] = res;
            }
        }
        return memo[target] % mod;
    }
}

最小化目标值与所选元素的差

给你一个大小为 m x n 的整数矩阵 mat 和一个整数 target 。

从矩阵的 每一行 中选择一个整数，你的目标是 最小化 所有选中元素之和与目标值 target 的 绝对差 。

返回 最小的绝对差 。

a 和 b 两数字的 绝对差 是 a - b 的绝对值。

class Solution {
    boolean[][] memo;
    int n;
    int[][] mat;
    int res = Integer.MAX_VALUE;
    public int minimizeTheDifference(int[][] mat, int target) {
        int m = mat.length;
        this.n = mat[0].length;
        this.mat = mat;
        int MAX = Math.max(70 * m, target);
        memo = new boolean[m][MAX + 1];
        dfs(m - 1, 0, target);
        return res;
    }

    public void dfs(int x, int sum, int t) {
        if (x < 0) {
            res = Math.min(res, Math.abs(sum - t));
            return;
        }
        if (memo[x][sum]) return;
        memo[x][sum] = true;
        for (int j = 0; j < n; ++ j) {
            dfs(x - 1, sum + mat[x][j], t);
        }
    }
}

从栈中取出 K 个硬币的最大面值和

一张桌子上总共有 n 个硬币栈。每个栈有 正整数 个带面值的硬币。

每一次操作中，你可以从任意一个栈的顶部取出 1 个硬币，从栈中移除它，并放入你的钱包里。

给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ，请你返回在恰好进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。

class Solution {
    List<List<Integer>> piles;
    int [][]memo;
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        this.piles = piles;
        memo = new int[n][k + 1];
        for (int []a : memo) Arrays.fill(a, -1);
        return dfs(n - 1, k);
    }

    public int dfs(int i, int k) {
        if (i < 0) {
            return 0;
        }
        if (memo[i][k] != -1) return memo[i][k];
        List<Integer> l = piles.get(i);
        int t = l.size(), sum = 0;
        int res = dfs(i - 1, k);
        for (int j = 0; j < t; ++ j) {
            sum += l.get(j);
            if (j + 1 <= k) {
                res = Math.max(res, dfs(i - 1, k - j - 1) + sum);
            }
        }
        return memo[i][k] = res;
    }
}

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i < n; ++ i) {
            List<Integer> l = piles.get(i);
            int m = l.size();
            for (int j = 0; j <= k; ++ j) {
                dp[i + 1][j] = dp[i][j];
                int sum = 0;
                for (int o = 0; o < m; ++ o) {
                    sum += l.get(o);
                    if (o + 1 <= j) {
                        dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - o - 1] + sum);
                    }
                }
            }
        }
        return dp[n][k];
    }
}

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        int[] dp = new int[k + 1];
        for (int i = 0; i < n; ++ i) {
            List<Integer> l = piles.get(i);
            int m = l.size();
            for (int j = k; j >= 0; -- j) {
                int sum = 0;
                for (int t = 0; t < m; ++ t) {
                    sum += l.get(t);
                    if (t + 1 <= j) {
                        dp[j] = Math.max(dp[j], dp[j - t - 1] + sum);
                    }
                }
            }
        }
        return dp[k];
    }
}

经典线性 DP

最长公共子序列

class Solution {
    int[][] memo;
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        memo = new int[n][m];
        for (int []a : memo) Arrays.fill(a, -1);
        return dfs(n - 1, m - 1, text1, text2);
    }

    public int dfs(int i, int j, String s1, String s2) {
        if (i < 0 || j < 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int res = Math.max(dfs(i - 1, j, s1, s2), dfs(i, j - 1, s1, s2));
        if (s1.charAt(i) == s2.charAt(j)) {
            res = Math.max(res, dfs(i - 1, j - 1, s1, s2) + 1);
        }
        return memo[i][j] = res;
    }
}

class Solution {
    int[][] memo;
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        memo = new int[n + 1][m + 1];
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                memo[i + 1][j + 1] = Math.max(memo[i][j + 1], memo[i + 1][j]);
                if (s1.charAt(i) == s2.charAt(j)) {
                    memo[i + 1][j + 1] = memo[i][j] + 1;
                }
            }
        }
        return memo[n][m];
    }
}

一维数组，我们可以发现，当前的状态由他的左边，上边和左上的状态转移过来，一维数组的话左上的状态就会在计算时被覆盖掉，导致我们计算当前状态时拿到的是错误的（被更新过的）左上状态来比较，所以需要用一个变量保存左上状态

class Solution {
    int[] memo;
    public int longestCommonSubsequence(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        memo = new int[m + 1];
        for (int i = 0; i < n; ++ i) {
            for (int j = 0, pre = 0; j < m; ++ j) {
                int tmp = memo[j + 1];//保存左上状态
                memo[j + 1] = Math.max(memo[j + 1], memo[j]);
                if (s1.charAt(i) == s2.charAt(j)) {
                    memo[j + 1] = pre + 1;//左上状态+1
                }
                pre = tmp;
            }
        }
        return memo[m];
    }
}

通过给定词典构造目标字符串的方案数

dp[i][j] 表示words中的word的前 i 个字符构造出 target 中的前 j 个字符的方案数，dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * cnt 其中cnt是word的第i位等于target的第j位的word个数，可以先预处理出来。

class Solution {
    private int mod = 1_000_000_007;
    int[][] idx;
    public int numWays(String[] words, String target) {
        int n = words[0].length();
        int m = target.length();
        int[][] memo = new int[n][m];
        idx = new int[n][26];
        for (int[] a : memo) Arrays.fill(a, -1);
        for (int i = 0; i < n; ++ i) {
            for (String s : words) {
                idx[i][s.charAt(i) - 'a'] ++;//预处理第i位为某个字符的word的个数
            }
        }
        return dfs(words, target, memo, n - 1, m - 1) % mod;
    }

    public int dfs(String[] words, String target, int[][] memo, int i, int j) {
        if (j < 0) return 1;//构造成功一个target
        if (i < 0) return 0;//target还没构造完word就已经遍历完了每一位
        if (memo[i][j] != -1) return memo[i][j];
        int cnt = idx[i][target.charAt(j) - 'a'];//第i位为target.charAt(j)的word的个数
        long res = dfs(words, target, memo, i - 1, j); 
        long t = dfs(words, target, memo, i - 1, j - 1);
        res = (res + t * cnt % mod) % mod;//如果cnt是0返回的就是不选word的第i位，否则就是用word的第i位成功构造target的第j位
        return memo[i][j] = (int) res;
    }
}

class Solution {
    private int mod = 1_000_000_007;
    int[][] idx;
    public int numWays(String[] words, String target) {
        int n = words[0].length();
        int m = target.length();
        long[][] memo = new long[n + 1][m + 1];
        idx = new int[n][26];
        for (int i = 0; i < n; ++ i) {
            for (String s : words) {
                idx[i][s.charAt(i) - 'a'] ++;
            }
        }
        for (int i = 0; i < n; ++ i) memo[i][0] = 1;
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                int cnt = idx[i][target.charAt(j) - 'a'];
                memo[i + 1][j + 1] = (memo[i][j + 1] + cnt * memo[i][j] % mod) % mod;
            }
        }
        return (int) memo[n][m];
    }
}

class Solution {
    private int mod = 1_000_000_007;
    int[][] idx;
    public int numWays(String[] words, String target) {
        int n = words[0].length();
        int m = target.length();
        long[] memo = new long[m + 1];
        idx = new int[n][26];
        for (int i = 0; i < n; ++ i) {
            for (String s : words) {
                idx[i][s.charAt(i) - 'a'] ++;
            }
        }
        memo[0] = 1;
        for (int i = 0; i < n; ++ i) {
            for (int j = m - 1; j >= 0; -- j) {
                int cnt = idx[i][target.charAt(j) - 'a'];
                memo[j + 1] = (memo[j + 1] + cnt * memo[j] % mod) % mod;
            }
        }
        return (int) memo[m];
    }
}

最短公共超序列

给你两个字符串 str1 和 str2，返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个，则可以返回满足条件的 任意一个 答案。

示例 1：

1 2	`输入：str1 = "abac", str2 = "cab" 输出："cabac"`

官方提示的思路，先求出两个字符串的最长公共子序列，再根据dp数组保存的值倒序拼接答案

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                if (str1.charAt(i) == str2.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]);
                }
            }
        }
        if (dp[n][m] == m && dp[n][m] == n) return str1;
        String res = "";
        int i = n - 1, j = m - 1;
        while (i >= 0 && j >= 0) {
            if (str1.charAt(i) == str2.charAt(j)) {
                res = str1.charAt(i) + res;
                i --; j--;
            } else if (dp[i + 1][j] > dp[i][j + 1]) {
                res = str2.charAt(j) + res;
                j --;
            } else {// dp[i + 1][j] <= dp[i][j + 1]
                res = str1.charAt(i) + res;
                i --;
            }
        }
        if (i >= 0) {
            res = str1.substring(0, i + 1) + res;
        }
        if (j >= 0) {
            res = str2.substring(0, j + 1) + res;
        }
        return  res;
    }
}

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

class Solution {
    int[] memo;
    public int lengthOfLIS(int[] nums) {
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        int ans = 0;
        for (int i = 0; i < nums.length; ++ i) {
            ans = Math.max(ans, dfs(nums, i));
        }
        return ans;
    }
    public int dfs(int[] nums, int i) {
        if (i < 0) return 0;
        if (memo[i] != -1) return memo[i];
        int res = 0;
        for (int j = i; j >= 0; -- j) {
            if (nums[j] < nums[i]) {
                res = Math.max(res, dfs(nums, j)); 
            }            
        }
        return memo[i] = res + 1;
    }
}

class Solution {
    int[] dp;
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        dp = new int[n];
        int ans = 0;
        for (int i = 0; i < n; ++ i) {
            int res = 0; 
            for (int j = i; j >= 0; -- j) {
                if (nums[j] < nums[i]) {
                    res = Math.max(res, dp[j]);
                }
            }     
            dp[i] = res + 1;       
        }
        for (int i = 0; i < n; ++ i) {
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}

贪心+二分

维护的dp数组，dp[i]表示长度为 i + 1 时的递增子序列末尾元素的最小值

class Solution {
    int[] dp;
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        dp = new int[n];
        int idx = 0;
        for (int i = 0; i < n; ++ i) {
            int t = bis(dp, 0, idx, nums[i]);//二分寻找nums[i]应该放在哪个位置
            if (t == idx) {//大于dp数组中的所有元素，添加到末尾，数组长度++
                dp[idx ++] = nums[i];
            } else {//放到该放的位置
                dp[t] = nums[i];
            }
        }
        return idx;
    }
	//二分算法
    public int bis(int[] nums, int l, int r, int x) {
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] < x) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

划分型DP

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

dfs + memo

class Solution {
    int []memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return dfs(s, n, wordDict);
    }

    public boolean dfs(String s, int i, List<String> wordDict) {
        if (i == 0) return true;
        if (memo[i] != -1) return memo[i] == 1;
        boolean res = false;
        for (int j = i - 1; j >= 0; -- j) {
            if (wordDict.contains(s.substring(j, i))) {
                res = res || dfs(s, j, wordDict);
            }
        }
        memo[i] = (res ? 1 : 0);
        return res;
    }
}

递推

public boolean wordBreak(String s, List<String> wordDict) {
    int n = s.length();
    boolean []dp = new boolean[n + 1];//dp[i]: s中前i个字符能否由wordDict拼接出
    dp[0] = true;
    for (int i = 0; i < n; ++ i) {
        for (int j = 0; j <= i; ++ j) {
            if (wordDict.contains(s.substring(j, i + 1))) {
                dp[i + 1] = dp[j] || dp[i + 1];
            }
        }
    }
    return dp[n];
}

编辑距离

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

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

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

class Solution {
    int[][] memo;
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        memo = new int[n][m];
        for (int []a : memo) Arrays.fill(a, -1);
        return dfs(n - 1, m - 1, word1, word2);
    }

    public int dfs(int i, int j, String word1, String word2) {
        if (i < 0) return j + 1;
        if (j < 0) return i + 1;
        if (memo[i][j] != -1) return memo[i][j];
        int res = Math.min(dfs(i - 1, j - 1, word1, word2), Math.min(dfs(i - 1, j, word1, word2), dfs(i, j - 1, word1, word2))) + 1;
        if (word1.charAt(i) == word2.charAt(j)) res = dfs(i - 1, j - 1, word1, word2);
        return memo[i][j] = res;
    }
}

状态压缩DP

优美的排列

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件之一，该数组就是一个 优美的排列 ：

perm[i] 能够被 i 整除
i 能够被 perm[i] 整除

给你一个整数 n ，返回可以构造的 优美排列 的数量。

集合S是已选择的数字

class Solution {
    public int countArrangement(int n) {
        int[] memo = new int[1 << n];
        Arrays.fill(memo, -1);
        return dfs(0, n, memo);
    }

    public int dfs(int s, int n, int[] memo) {
        if (s == (1 << n) - 1) return 1;
        if (memo[s] != -1) return memo[s];
        int i = Integer.bitCount(s) + 1;
        int res = 0;
        for (int j = 1; j <= n; ++ j) {
            if ((s >> (j - 1) & 1) == 0 && (i % j == 0 || j % i == 0)) {
                res += dfs(s | (1 << (j - 1)), n, memo);
            }
        }
        return memo[s] = res;
    }
}

集合S为还未选择的数字

class Solution {
    public int countArrangement(int n) {
        int[] memo = new int[1 << n];
        Arrays.fill(memo, -1);
        return dfs((1 << n) - 1, n, memo);
    }

    public int dfs(int s, int n, int[] memo) {
        if (s == 0) return 1;
        if (memo[s] != -1) return memo[s];
        int i = n - Integer.bitCount(s) + 1;
        int res = 0;
        for (int j = 1; j <= n; j ++) {
            if ((s >> (j - 1) & 1) == 1 && (i % j == 0 || j % i == 0)) {
                res += dfs(s ^ (1 << (j - 1)), n, memo);
            }
        }
        return memo[s] = res;
    }
}

选择矩阵中单元格的最大得分

给你一个由正整数构成的二维矩阵 grid。

你需要从矩阵中选择 一个或多个 单元格，选中的单元格应满足以下条件：

所选单元格中的任意两个单元格都不会处于矩阵的 同一行。
所选单元格的值 互不相同。

你的得分为所选单元格值的总和。

返回你能获得的最大得分。

class Solution {
    public int maxScore(List<List<Integer>> grid) {
        int m = grid.size();
        Map<Integer, Integer> mp = new HashMap<>();
        for (int i = 0; i < m; ++ i) {
            for (int j : grid.get(i)) {
                mp.merge(j, 1 << i, (a, b) -> a | b);//存储值对应的行号，使用二进制保存
            }
        }
        int n = mp.size();
        int[][] memo = new int[101][1 << m];//[值][行号的集合]
        for (int[] a : memo) Arrays.fill(a, -1);
        return dfs(100, 0, mp, memo);//题目范围最大值为100，直接从100开始枚举
    }
    //从值[1~i]中选数字，所选数字的行号不能在集合j中，每行至多选一个元素且没有重复值，所选元素和的最大值
    public int dfs(int i, int j, Map<Integer, Integer> mp, int[][] memo) {
        if (i == 0) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        int res = dfs(i - 1, j, mp, memo);
        if (mp.containsKey(i)) {
			for (int t = mp.get(i), lb; t > 0; t ^= lb) {
    			lb = t & -t;
            	if ((j & lb) == 0) {
                	res = Math.max(res, dfs(i - 1, j | lb, mp, memo) + i);
            	}
        	}
        }
        return memo[i][j] = res;
    }
}

//二进制集合表示，遍历集合的另一种写法，看看你脑壳会不会昏
public int dfs(int i, int j, Map<Integer, Integer> mp, int[][] memo) {
    if (i == 0) return 0;
    if (memo[i][j] != -1) return memo[i][j];
    int res = dfs(i - 1, j, mp, memo);
    if (mp.containsKey(i)) {
        for (int t = mp.get(i); t > 0; t &= (t - 1)) {
            int k = Integer.numberOfTrailingZeros(t);
            if ((j & (1 << k)) == 0) {
                res = Math.max(res, dfs(i - 1, j | (1 << k), mp, memo) + i);
            }
        }
    }
    return memo[i][j] = res;
}

不知道什么DP

单调数组对的数目 I

给你一个长度为 n 的正整数数组 nums 。

如果两个非负整数数组 (arr1, arr2) 满足以下条件，我们称它们是单调数组对：

两个数组的长度都是 n 。
arr1 是单调 非递减 的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
arr2 是单调 非递增 的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有单调数组对的数目。

由于答案可能很大，请你将它对 109 + 7 取余后返回。

dfs + memo

class Solution {
    int [][]memo;
    int []nums;
    int mod = 1_000_000_007;
    public int countOfPairs(int[] nums) {
        this.nums = nums;
        int max = Arrays.stream(nums).max().getAsInt();
        int n = nums.length;
        memo = new int[n + 1][max + 1];
        for (int []a : memo) Arrays.fill(a, -1);
        int res = 0;
        for (int i = 0; i <= nums[n - 1]; ++ i) {
            res = (res + dfs(n - 1, i)) % mod;
        }
        return res;
    }

    //考虑前i个元素的单调数组对的数目，其中arr1的第i位值为j
    public int dfs(int i, int j) {
        if (i == 0) {
            return 1;
        }
        if (memo[i][j] != -1) return memo[i][j];
        int res = 0;
        int mi = Math.min(Math.min(j, nums[i - 1]), nums[i - 1] - nums[i] + j);
        for (int k = 0; k <= mi; ++ k) {
            res = (res + dfs(i - 1, k)) % mod;
        }
        return memo[i][j] = res;
    }
}

1:1翻译成递推，真的是完全1:1

class Solution {
    int [][]dp;
    int []nums;
    int mod = 1_000_000_007;
    public int countOfPairs(int[] nums) {
        this.nums = nums;
        int max = Arrays.stream(nums).max().getAsInt();
        int n = nums.length;
        dp = new int[n + 1][max + 1];
        for (int j = 0; j <= nums[0]; ++ j) {//根据dfs初始条件1:1翻译
            dp[0][j] = 1;
        }
        for (int i = 1; i < n; ++ i) {
            for (int j = 0; j <= nums[i]; ++ j) {//dp[i][j]表示前i个元素，其中arr1的第i位为j，所产生的单调 数组对个数
                int res = 0;
                int mi = Math.min(Math.min(j, nums[i - 1]), nums[i - 1] - nums[i] + j);
                //由于arr1的第i位为j，而限定了arr1的第i-1位的取值范围
                for (int k = 0; k <= mi; ++ k) {//枚举i-1位的每一种可能取值
                    res = (res + dp[i - 1][k]) % mod;
                }
                dp[i][j] = res;
            }
        }
        int ans = 0;
        for (int i = 0; i <= nums[n - 1]; ++ i) {
            ans = (ans + dp[n - 1][i]) % mod;
        }
        return ans;
    }
}

前缀和优化

class Solution {
    int [][]dp;
    int []nums;
    int mod = 1_000_000_007;
    public int countOfPairs(int[] nums) {
        this.nums = nums;
        int max = Arrays.stream(nums).max().getAsInt();
        int n = nums.length;
        dp = new int[n + 1][max + 1];
        for (int j = 0; j <= nums[0]; ++ j) {//根据dfs初始条件1:1翻译
            dp[0][j] = 1;
        }
        for (int i = 1; i < n; ++ i) {
            int []preS = new int[nums[i - 1] + 1];
            preS[0] = dp[i - 1][0];
            for (int x = 1; x <= nums[i - 1]; ++ x) {
                preS[x] = (preS[x - 1] + dp[i - 1][x]) % mod;
            }
            for (int j = 0; j <= nums[i]; ++ j) {//dp[i][j]表示前i个元素，其中arr1的第i位为j，所产生的单调 数组对个数
                int mi = Math.min(Math.min(j, nums[i - 1]), nums[i - 1] - nums[i] + j);
                // int res = 0;
                // 由于arr1的第i位为j，而限定了arr1的第i-1位的取值范围
                // for (int k = 0; k <= mi; ++ k) {//枚举i-1位的每一种可能取值
                //     res = (res + dp[i - 1][k]) % mod;
                // }
                dp[i][j] = mi >= 0 ? preS[mi] : 0;
            }
        }
        int ans = 0;
        for (int i = 0; i <= nums[n - 1]; ++ i) {
            ans = (ans + dp[n - 1][i]) % mod;
        }
        return ans;
    }
}

算法

#动态规划

动态规划-递归到记忆化搜索

https://payfish.github.io/2024/07/06/动态规划-递归到记忆化搜索/

作者

fu1sh

发布于

2024年7月6日

许可协议

IOC与AOP 上一篇

Netty实现RPC框架实战下一篇