Memorization Search

自顶向下的动态规划——记忆化搜索

记忆化搜索好解决不常见状态转移方程的dp问题

198. 打家劫舍

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        // 1.dp[j]: 到达标号为j的房屋可获得的最大价值
        // 2.状态转移：dp[j] = max(dp[j - 1], dp[j - 2] + nums[j])
        // 3.初始化：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
        // 4.遍历顺序：从前往后
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if (nums.length == 1)
            return nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

方法二：DP + 滚动数组

由状态转移方程可以看出，dp[i]由前面两个状态得出，所以dp数组的长度只需要为3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        // 1.dp[j]: 到达标号为j的房屋可获得的最大价值
        // 2.状态转移：dp[j] = max(dp[j - 1], dp[j - 2] + nums[j])
        // 3.初始化：dp[0] = nums[0], dp[1] = max(nums[0], nums[1])
        // 4.遍历顺序：从前往后
        if (nums.length == 1)
            return nums[0];
        int[] dp = new int[3];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; ++i) {
            dp[i % 3] = Math.max(dp[(i - 1) % 3], dp[(i - 2) % 3] + nums[i]);
        }
        return dp[(nums.length - 1) % 3];
    }
}

方法三：记忆化搜索

自顶向下，举个例子nums=[1,2,3,1]

  1. 返回的答案为dfs(3, nums)

  2. 要求，需要知道dfs(3-1,nums)与dfs(3-2,nums)+nums[3]，然后取最大值

  3. 求dfs(2,nums)，需要知道dfs(2-1,nums)与dfs(2-2,nums)+nums[2]，然后取最大值

    .......

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    int[] dp;

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

    private int dfs(int index, int[] nums) {
        if (index < 0)
            return 0;
        if (dp[index] != -1)
            return dp[index];
//        int dont = dfs(index - 1, nums);
//        int steal = dfs(index - 2, nums) + nums[index];
//        return dp[index] = Math.max(dont, steal);
        return dp[index] = Math.max(dfs(index - 1, nums), dfs(index - 2, nums) + nums[index]);
    }
}

二刷记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int rob(int[] nums) {
        dp = new int[nums.length];
        Arrays.fill(dp, -1);
        return dfs(nums, 0);
    }

    int[] dp;

    private int dfs(int[] nums, int index) {
        if (index >= nums.length)
            return 0;
        if (dp[index] != -1)
            return dp[index];
        return dp[index] = Math.max(dfs(nums, index + 1), dfs(nums, index + 2) + nums[index]);
    }
}

方法四：回溯

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int rob(int[] nums) {
        return dfs(nums, 0);
    }

    private int dfs(int[] nums, int index) {
        if (index >= nums.length)
            return 0;
        return Math.max(dfs(nums, index + 1), dfs(nums, index + 2) + nums[index]);
    }
}

213. 打家劫舍 II

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        if (nums.length == 2) 
            return Math.max(nums[0], nums[1]);
        return Math.max(process(nums, 0, nums.length - 1), process(nums, 1, nums.length));
    }

    private int process(int[] nums, int start, int end) {
        int[] dp = new int[end - start];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);
        for (int i = 2; i < end - start; ++i) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i + start]);
        }
        return dp[end - start - 1];
    }
}

方法二：DP + 滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        if (nums.length == 2) 
            return Math.max(nums[0], nums[1]);
        return Math.max(process(nums, 0, nums.length - 1), process(nums, 1, nums.length));
    }

    private int process(int[] nums, int start, int end) {
        int[] dp = new int[3];
        dp[0] = nums[start];
        dp[1] = Math.max(nums[start], nums[start + 1]);
        for (int i = 2; i < end - start; ++i) {
            dp[i % 3] = Math.max(dp[(i - 1) % 3], dp[(i - 2) % 3] + nums[i + start]);
        }
        return dp[(end - start - 1) % 3];
    }
}

方法三：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    int[] dp;
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        if (nums.length == 2)
            return Math.max(nums[0], nums[1]);
        dp = new int[nums.length];
        Arrays.fill(dp, -1);
        int res1 = dfs(nums, 0, nums.length - 2);
        Arrays.fill(dp, -1);
        int res2 = dfs(nums, 1,  nums.length - 1);
        return Math.max(res1, res2);
    }

    private int dfs(int[] nums, int start, int index) {
        if (index < start)
            return 0;
        if (dp[index] != -1)
            return dp[index];
       return dp[index] = Math.max(dfs(nums, start, index - 1), dfs(nums, start, index - 2) + nums[index]);
    }
}

二刷记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int rob(int[] nums) {
        if (nums.length == 1)
            return nums[0];
        this.nums = nums;
        dp = new int[nums.length];
        Arrays.fill(dp, -1);
        int res1 =  dfs(0, nums.length - 1);
        Arrays.fill(dp, -1);
        return Math.max(res1, dfs(1, nums.length));
    }

    int[] dp, nums;

    private int dfs(int start, int end) {
        if (start >= end)
            return 0;
        if (dp[start] != -1)
            return dp[start];
        return dp[start] = Math.max(dfs(start + 1, end), dfs(start + 2, end) + nums[start]);
    }
}

337. 打家劫舍 III

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // steal: 偷当前节点能获得的最大金额
    // pass: 不偷当前节点能获得的最大金额
    // steal(cur) = cur.val + pass(cur.left) + pass(cur.right)
    // pass(cur) = max(steal(cur.left), pass(steal.right)) + max(steal(cur.right), pass(steal.right))
    Map<TreeNode, Integer> steal = new HashMap<>();
    Map<TreeNode, Integer> pass = new HashMap<>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(steal.getOrDefault(root, 0), pass.getOrDefault(root, 0));
    }
    public void dfs(TreeNode root) {
        if (root == null)
            return;
        dfs(root.left);
        dfs(root.right);
        steal.put(root, root.val + pass.getOrDefault(root.left, 0) + pass.getOrDefault(root.right, 0));
        pass.put(root, Math.max(steal.getOrDefault(root.left, 0), pass.getOrDefault(root.left, 0)) + Math.max(steal.getOrDefault(root.right, 0), pass.getOrDefault(root.right, 0)));
    }
}

方法二：乱写的的dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    // steal: 偷当前节点能获得的最大金额
    // pass: 不偷当前节点能获得的最大金额
    // steal(cur) = cur.val + pass(cur.left) + pass(cur.right)
    // pass(cur) = max(steal(cur.left), pass(steal.right)) + max(steal(cur.right), pass(steal.right))
    Map<TreeNode, Integer> steal = new HashMap<>();
    Map<TreeNode, Integer> pass = new HashMap<>();
    public int rob(TreeNode root) {
        int steal = dfs(root, 0);
        int pass = dfs(root, 1);
        return Math.max(steal, pass);
    }
    public int dfs(TreeNode root, int flag) {
        if (root == null)
            return 0;
        if (flag == 1 && pass.get(root) != null) {
            return pass.get(root);
        }
        else if (flag == 0 && steal.get(root) != null) {
            return steal.get(root);
        }
        steal.put(root, root.val + pass.getOrDefault(root.left, dfs(root.left, 1)) + pass.getOrDefault(root.right, dfs(root.right, 1)));
        pass.put(root, Math.max(steal.getOrDefault(root.left, dfs(root.left, 0)), pass.getOrDefault(root.left, dfs(root.left, 1))) + Math.max(steal.getOrDefault(root.right, dfs(root.right, 0)), pass.getOrDefault(root.right, dfs(root.right, 1))));
        if (flag == 0)
            return steal.getOrDefault(root, 0);
        else 
            return pass.getOrDefault(root, 0);
    }
}

方法三：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int rob(TreeNode root) {
        return dfs(root);    
    }

    Map<TreeNode, Integer> map = new HashMap<>();
    
    public int dfs(TreeNode root) {
        if (root == null)
            return 0;
        if (map.containsKey(root))
            return map.get(root);
        int left = 0, right = 0;
        if (root.left != null)
            left = dfs(root.left.left) + dfs(root.left.right);
        if (root.right != null)
            right = dfs(root.right.left) + dfs(root.right.right);
        int steal = root.val + left + right;
        int pass = dfs(root.left) + dfs(root.right);
        int max = Math.max(steal, pass);
        map.put(root, max);
        return max;
    }
}

494. 目标和

方法一：01背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int diff = sum - target;
        if (diff % 2 == 1 || diff < 0)
            return 0;
        target = diff / 2;
        // dp[j]:装满容量为j的方法数
        // dp[0] = 1,装满容量为0的背包有一种
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; ++i) {
            for (int j = target; j >= nums[i]; --j) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }
}

方法二：回溯

使用sum，对sum作加操作，相当于对target作减操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int res = 0;
    public int findTargetSumWays(int[] nums, int target) {
        backtracking(nums, target, 0);
        return res;
    }

    private void backtracking(int[] nums, int target, int start) {
        if (start == nums.length) {
            if (target == 0)
                ++res;
            return;
        }
        backtracking(nums, target + nums[start], start + 1);
        backtracking(nums, target - nums[start], start + 1);
    }
}

方法三：回溯的另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, target, 0, 0);
    }

    private int dfs(int[] nums, int target, int start, int sum) {
        if (start == nums.length) {
            return target == sum ? 1 : 0;
        }
        return dfs(nums, target, start + 1, sum - nums[start]) + dfs(nums, target, start + 1, sum + nums[start]);
    }
}

更加精简的回溯

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
       return dfs(nums, target, 0);
    }

    private int dfs(int[] nums, int target, int index) {
        if (index == nums.length)
            return target == 0 ? 1 : 0;
        return dfs(nums, target - nums[index], index + 1) + dfs(nums, target + nums[index], index + 1);
    }
}

方法四：记忆化搜索

  1. 相比回溯，使用数组记录已经计算过的结果，return前先赋值给数组memo
  2. 每次遍历时，首先检查memo中是否已经有结果(已经计算过了)，有结果直接返回结果
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int[][] memo;
    public int findTargetSumWays(int[] nums, int target) {
        memo = new int[nums.length][2001];
        for (int[] m : memo)
            Arrays.fill(m, -1);
        return dfs(nums, target, nums.length - 1, 0);
    }

    private int dfs(int[] nums, int target, int start, int sum) {
        if (start < 0) {
            return target == sum ? 1 : 0;
        }
        if (memo[start][sum + 1000] != -1)
            return memo[start][sum + 1000];
        return memo[start][sum + 1000] = dfs(nums, target, start - 1, sum - nums[start]) + dfs(nums, target, start - 1, sum + nums[start]);
    }
}

二刷记忆化搜索

需要多开辟一点数组空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        dp = new int[3001][nums.length + 1];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(nums, target, 0);
    }

    int[][] dp;

    private int dfs(int[] nums, int target, int index) {
        if (index == nums.length)
            return target == 0 ? 1 : 0;
        if (dp[target + 1000][index] != -1)
            return dp[target + 1000][index];
        return dp[target + 1000][index] = dfs(nums, target - nums[index], index + 1) + dfs(nums, target + nums[index], index + 1);
    }
}

64. 最小路径和

方法一：回溯超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    int[][] dirs = new int[][]{ {1, 0}, {0, 1}};
    int res = Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        dfs(grid, m, n, 0, 0, grid[m - 1][n - 1]); // 最后一次答案没有计算，所以在遍历前加上
        return res;
    }

    private void dfs(int[][] grid, int m, int n, int i, int j, int sum) {
        if(i == m - 1 && j == n - 1) {
            res = Math.min(res, sum);
            return;
        }
        sum += grid[i][j];
        if (isValid(i + 1, j, m, n))
            dfs(grid, m, n, i + 1, j, sum);
        if (isValid(i, j + 1, m, n))
            dfs(grid, m, n, i, j + 1, sum);
    }
    private boolean isValid(int row, int col, int m, int n) {
        return row >= 0 && col >= 0 && row < m && col < n;
    }

}

方法二：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    int res = Integer.MAX_VALUE;
    int dp[][];
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        // dp[i][j]:grid[i][j]到右下角的最小距离
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(grid, m - 1, n - 1);
    }

    private int dfs(int[][] grid, int i, int j) {
        if (i == 0 && j == 0)
            return grid[0][0];
        if (i < 0 || j < 0)
            return 8000000;
        if (dp[i][j] != -1)
            return dp[i][j];
        return dp[i][j] = grid[i][j] + Math.min(dfs(grid, i - 1, j), dfs(grid, i, j - 1));
    }

    private boolean isValid(int row, int col) {
        return row >= 0 && col >= 0;
    }
}

二刷记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int minPathSum(int[][] grid) {
        dp = new int[grid.length][grid[0].length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(grid, 0, 0);
    }

    int[][] dirs = new int[][]{{1, 0}, {0, 1}};
    int[][] dp;

    private int dfs(int[][] grid, int i, int j) {
        if (i == grid.length - 1 && j == grid[0].length - 1)
            return grid[i][j];
        if (dp[i][j] != -1)
            return dp[i][j];
        int res = 40000;
        for (int[] dir : dirs) {
            int sum = grid[i][j];
            int row = i + dir[0], col = j + dir[1];
            if (row < grid.length && col < grid[0].length) {
                sum += dfs(grid, row, col);
                dp[i][j] = res = Math.min(res, sum);
            }
        }
        return res;
    }
}

62. 不同路径

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int[][] dp;
    public int uniquePaths(int m, int n) {
        dp = new int[m + 1][n + 1];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(m, n);
    }

    private int dfs(int i, int j) {
        if (i == 1 && j == 1)
            return 1;
        if (i < 1 || j < 1)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        return dp[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
    }
}

二刷记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
   public int uniquePaths(int m, int n) {
        dp = new int[m + 1][n + 1];
        return dfs(1, 1, m, n);
    }

    int[][] dp;

    private int dfs(int i, int j, int m, int n) {
        if (i == m && j == n)
            return 1;
        if (i > m || j > n)
            return 0;
        if (dp[i][j] != 0)
            return dp[i][j];
        return dp[i][j] = dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
}

63. 不同路径 II

方法一：记忆化搜索

obstacleGrid[i][j] == 1的判断要在if (i == 0 && j == 0)上面，不然会报如下错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int[][] dp;
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(obstacleGrid, m - 1, n - 1);
    }

    private int dfs(int[][] obstacleGrid, int i, int j) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1)
            return 0;
        if (i == 0 && j == 0)
            return 1;
        if (dp[i][j] != -1)
            return dp[i][j];
        return dp[i][j] = dfs(obstacleGrid,i - 1, j) + dfs(obstacleGrid, i, j - 1);
    }
}

image-20230524190551578

二刷记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        m = obstacleGrid.length;
        n = obstacleGrid[0].length;
        dp = new int[m][n];
        return dfs(obstacleGrid, 0, 0);
    }

    int[][] dp;
    int m, n;
    private int dfs(int[][] obstacleGrid, int i, int j) {
        if (i == m || j == n || obstacleGrid[i][j] == 1)
            return 0;
        if (i == m - 1 && j == n - 1)
            return 1;
        if (dp[i][j] != 0)
            return dp[i][j];
        return dp[i][j] = dfs(obstacleGrid, i + 1, j) + dfs(obstacleGrid, i, j + 1);
    }
}

139. 单词拆分

方法一：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    // dp[i]:前i个字符是否能被字典中的单词拼接出
    // 状态转移：dp[i] = dp[j] && set.contains(s.substring(j, i)) (j < i)
    boolean[] dp;
    Set<String> set;
    public boolean wordBreak(String s, List<String> wordDict) {
        dp = new boolean[s.length() + 1];
        set = new HashSet<>(wordDict);
        dp[0] = true;
        for (int i = 1; i <= s.length(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && set.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

方法二：回溯(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    Set<String> set;
    public boolean wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        return dfs(s, 0);
    }

    private boolean dfs(String s, int index) {
        if (index == s.length())
            return true;
        for (int i = index; i < s.length(); ++i) {
            String str = s.substring(index, i + 1);
            if (set.contains(str) && dfs(s, i + 1)) 
                return true;
        }
        return false;
    }
}

方法二：记忆化搜索

dp[i]：从下标i到结尾，是否拼接出单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    Set<String> set;
    int[] dp;
    public boolean wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        dp = new int[s.length() + 1];
        Arrays.fill(dp, -1);
        return dfs(s, 0);
    }

    private boolean dfs(String s, int index) {
        if (index == s.length())//能走到这，说明之前的字符串全能被单词拼接
            return true;
        if (dp[index] != -1)
            return dp[index] == 0 ? false : true;
        for (int i = index; i < s.length(); ++i) {
            String str = s.substring(index, i + 1);
            if (set.contains(str)) {
                dp[i + 1] = dfs(s, i + 1) ? 1 : 0;
                if (dp[i + 1] == 1)
                    return true; // 找到一个答案就返回true
            }
        }
        return false;
    }
}

397. 整数替换

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    
    Map<Long, Integer> map = new HashMap<>();
    public int integerReplacement(int n) {
        return dfs(n);
    }

    private int dfs(long n) {
        if (n == 1)
            return 0;
        if (map.containsKey(n))
            return map.get(n);
        int count = 0;
        if (n % 2 == 0) {
            count = dfs(n >> 1) + 1;
        }
        else {
            count = Math.min(dfs(n + 1), dfs(n - 1)) + 1;
        }
        map.put(n, count);
        return count;
    }
}

55. 跳跃游戏

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    int[] dp;
    public boolean canJump(int[] nums) {
        dp = new int[nums.length];
        return dfs(nums, 0);
    }

    private boolean dfs(int[] nums, int index) {
        if (index >= nums.length - 1)
            return true;
        if (dp[index] != 0)
            return dp[index] == 1;
        for (int i = 1; i <= nums[index]; ++i) {
            if (dfs(nums, index + i)) {
                dp[index] = 1;
                return true;
            }
        }
        dp[index] = -1;
        return false;
    }
}

方法二：贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean canJump(int[] nums) {
        int n = nums.length;
        int rightmost = 0;
        for (int i = 0; i < n; ++i) {
            if (i <= rightmost) {
                rightmost = Math.max(rightmost, i + nums[i]);
                if (rightmost >= n - 1)
                    return true;
            }                
        }
        return false;
    }
}

方法三：回溯(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canJump(int[] nums) {
        return dfs(nums, 0);
    }

    private boolean dfs(int[] nums, int index) {
        if (index >= nums.length - 1)
            return true;
        for (int i = 1; i <= nums[index]; ++i) 
            if (dfs(nums, index + i))
                return true;
        return false;
    }
    
}

二刷记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {

    int[] dp;
    
    public boolean canJump(int[] nums) {
        dp = new int[nums.length];
        return dfs(nums, 0);
    }

    private boolean dfs(int[] nums, int index) {
        if (index >= nums.length - 1)
            return true;
        if (dp[index] != 0)
            return dp[index] == 1;
        for (int i = 1; i <= nums[index]; ++i) {
            dp[index] = dfs(nums, index + i) == true ? 1 : -1;
            if (dp[index] == 1)
                return true;
        }
        return false;
    }
    
}

45. 跳跃游戏 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    
    public int jump(int[] nums) {
        dp = new int[nums.length];
        return dfs(nums, 0);
    }

    int[] dp;
    int res = 10001;

    private int dfs(int[] nums, int index) {
        if (index >= nums.length - 1) {
            return 0;
        }
        if (dp[index] != 0)
            return dp[index];
        int min = 10001;
        for (int i = 1; i <= nums[index]; ++i) {
            min = Math.min(min, dfs(nums, index + i) + 1);
        }
        return dp[index] = min;
    }
    
}

方法二：贪心

322. 零钱兑换

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int coinChange(int[] coins, int amount) {
        dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        int res = dfs(coins, amount);
        return res == 10001 ? -1 : res;
    }

    int[] dp;

    private int dfs(int[] coins, int amount) {
        if (amount == 0)
            return 0;
        if (dp[amount] != -1)
            return dp[amount];
        int min = 10001;
        for (int i = 0; i < coins.length; ++i) {
            if (amount - coins[i] < 0)
                continue;
            min = Math.min(min, dfs(coins, amount - coins[i]) + 1);
        }
        return dp[amount] = min;
    }
    
}

方法二：完全背包

518. 零钱兑换 II

方法一：完全背包

方法二：回溯(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int change(int amount, int[] coins) {
        Arrays.sort(coins);
        dfs(amount, coins, 0);
        return res;
    }
    
    int res = 0;

    public void dfs(int amount, int[] coins, int index) {
        if (amount == 0) {
            ++res;
            return;
        }
        for (int i = index; i < coins.length; ++i) {
            if (amount < coins[i])
                break;
            dfs(amount - coins[i], coins, i);
        }
    }
    
}

回溯另一种写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int change(int amount, int[] coins) {
    Arrays.sort(coins);
    return dfs(amount, coins, 0);
}


public int dfs(int amount, int[] coins, int index) {
    if (amount == 0) {
        return 1;
    }
    int count = 0;
    for (int i = index; i < coins.length; ++i) {
        if (amount < coins[i])
            break;
        count += dfs(amount - coins[i], coins, i);
    }
    return count;
}

方法三：记忆化搜索

需要用二位数组存储当前amount，与遍历到的下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int change(int amount, int[] coins) {
        dp = new int[amount + 1][coins.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        Arrays.sort(coins);
        return dfs(amount, coins, 0);
    }

    int[][] dp;

    public int dfs(int amount, int[] coins, int index) {
        if (amount == 0) {
            return 1;
        }
        if (dp[amount][index] != -1)
            return dp[amount][index];
        int count = 0;
        for (int i = index; i < coins.length; ++i) {
            if (amount < coins[i])
                break;
            count += dfs(amount - coins[i], coins, i);
        }
        return  dp[amount][index] = count;
    }
}

343. 整数拆分

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    int[] dp;
    public int integerBreak(int n) {
        // dp[i]:将i拆分成若干正整数，将他们相乘的最大值
        // dp[1] = 1; dp[2] = 1
        dp = new int[n + 1];
        dp[1] = 1;
        int res = dfs(n);
        return res;
    }

    private int dfs(int n) {
        if (n == 2)
            return 1;
        if (dp[n] != 0)
            return dp[n];
        int max = 0;
        for (int i = 1; i <= n - 1; ++i) {
            int k = n - i;
            max = Math.max(max, Math.max(k * dfs(i), k * i));
        }
        return dp[n] = max;
    }
}

image-20230526143817625

res = Math.max(res, Math.max(i * (n - i), dfs(n - i) * i));这一句后面为什么不是dfs(n - i) * dfs(i)

比如

如果dfs(i) * dfs(k)，那么6和2会被拆分成3， 3，1

121. 买卖股票的最佳时机

方法一：贪心

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxProfit(int[] prices) {
        int minStock = 10000, maxProfit = 0;
        for (int price : prices) {
            if (price < minStock) {
                minStock = price;
            }
            maxProfit = Math.max(maxProfit, price - minStock);
        }
        return maxProfit;
    }
}

方法二：回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProfit(int[] prices) {
    this.prices = prices;
    return dfs(0, 0);
}

int[] prices;

private int dfs(int index, int state) {
    if (index == prices.length || state == 2)
        return 0;
    if (state == 0)
        // 不操作 买入
        return Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) - prices[index]);
    // 不操作 卖出
    return Math.max(dfs(index + 1, state), dfs(index + 1, state + 1) + prices[index]);
}

如果摸不着头脑救去debug吧！

debug版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int maxProfit(int[] prices) {
    this.prices = prices;
    return dfs(0, 0);
}

int[] prices;
private int dfs(int index, int state) {
    if (index == prices.length || state == 2)
        return 0;
    if (state == 0) {
        int keep0 = dfs(index + 1, state);
        int buy = dfs(index + 1, state + 1) - prices[index];
        return Math.max(keep0, buy);
    }
    else {
        int keep1 = dfs(index + 1, state);
        int sell = dfs(index + 1, state + 1) + prices[index];
        return Math.max(keep1, sell);
    }
}

方法三：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        this.prices = prices;
        dp = new int[2][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;

    private int dfs(int index, int state) {
        if (index == prices.length || state == 2)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state == 0)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, 0), dfs(index + 1, 1) - prices[index]);
        // 不操作 卖出
        return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 1, 2) + prices[index]);
    }
}

122. 买卖股票的最佳时机 II

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        this.prices = prices;
        dp = new int[2][prices.length];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    int[] prices;
    int[][] dp;

    private int dfs(int index, int state) {
        if (index == prices.length)
            return 0;
        if (dp[state][index] != -1)
            return dp[state][index];
        if (state == 0)
            // 不操作 买入
            return dp[state][index] = Math.max(dfs(index + 1, 0), dfs(index + 1, 1) - prices[index]);
        // 不操作 卖出
        return dp[state][index] = Math.max(dfs(index + 1, 1), dfs(index + 1, 0) + prices[index]);
    }
}

123. 买卖股票的最佳时机 III

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        dp = new int[prices.length][4];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(prices, 0, 0);
    }
    int[][] dp;
    private int dfs(int[] prices, int index, int state) {
        if (index == prices.length || state == 4)
            return 0;
        if (dp[index][state] != -1)
            return dp[index][state];
        if (state == 0 || state == 2) // 不操作，买入
            return dp[index][state] = Math.max(dfs(prices, index + 1, state), dfs(prices, index + 1, state + 1) - prices[index]);
        return dp[index][state] = Math.max(dfs(prices, index + 1, state), dfs(prices, index + 1, state + 1) + prices[index]);
    }
}

188. 买卖股票的最佳时机 IV

记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int k, int[] prices) {
        dp = new int[prices.length][2 * k];
        this.k = k;
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(prices, 0, 0);
    }
    int[][] dp;
    int k;
    private int dfs(int[] prices, int index, int state) {
        if (index == prices.length || state == 2 * k)
            return 0;
        if (dp[index][state] != -1)
            return dp[index][state];
        if (state % 2 == 0) // 不操作，买入
            return dp[index][state] = Math.max(dfs(prices, index + 1, state), dfs(prices, index + 1, state + 1) - prices[index]);
        return dp[index][state] = Math.max(dfs(prices, index + 1, state), dfs(prices, index + 1, state + 1) + prices[index]);
    }
}

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

记忆化搜索

卖的时候 - fee 或者 买的时候 - fee都可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxProfit(int[] prices, int fee) {
        dp = new int[prices.length][2];
        this.fee = fee;
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(prices, 0, 0);
    }
    int[][] dp;
    int fee;
    private int dfs(int[] prices, int index, int state) {
        if (index == prices.length)
            return 0;
        if (dp[index][state] != -1)
            return dp[index][state];
        if (state == 0) // 不操作，买入
            return dp[index][state] = Math.max(dfs(prices, index + 1, 0), dfs(prices, index + 1, 1) - prices[index]);
        return dp[index][state] = Math.max(dfs(prices, index + 1, 1), dfs(prices, index + 1, 0) + prices[index] - fee);
    }
}

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

记忆化搜索

卖出:index + 2

base case : index >= prices.length

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int maxProfit(int[] prices) {
        dp = new int[prices.length][2];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(prices, 0, 0);
    }
    int[][] dp;
    private int dfs(int[] prices, int index, int state) {
        if (index >= prices.length)
            return 0;
        if (dp[index][state] != -1)
            return dp[index][state];
        if (state == 0) // 不操作，买入
            return dp[index][state] = Math.max(dfs(prices, index + 1, 0), dfs(prices, index + 1, 1) - prices[index]);
        return dp[index][state] = Math.max(dfs(prices, index + 1, 1), dfs(prices, index + 2, 0) + prices[index]);
    }
}

获得分数的方法数

方法一：记忆化搜索(分组背包)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    
    static final int MOD = (int) 1e9 + 7;
    int n ;
    int[][] types, dp;

    public int waysToReachTarget(int target, int[][] types) {
        this.types = types;
        n = types.length;
        dp = new int[n][1002];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, target);
    }

    private int dfs(int index, int target) {
        if (index == n)
            return target == 0 ? 1 : 0;
        if (dp[index][target] != -1)
            return dp[index][target];
        int res = 0, count = types[index][0], marks = types[index][1];
        for (int i = 0; i <= Math.min(target / marks, count); ++i)
            res = (res + (dfs(index + 1, target - i * marks) % MOD)) % MOD;
        return dp[index][target] = res;
    }
}

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

方法一：记忆化搜索

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int minimizeTheDifference(int[][] mat, int target) {
        m = mat.length;
        n = mat[0].length;
        this.target = target;
        this.mat = mat;
        dp = new boolean[80][5000];
        dfs(0,  0);
        return res;

    }

    private void dfs(int i, int sum) {
        if (i == m) {
            res = Math.min(res, Math.abs(sum - target));
            return;
        }
        if (sum - target > res || dp[i][sum])
            return;
        dp[i][sum] = true;
        for (int j = 0; j < n; ++j) {
            dfs(i + 1, sum + mat[i][j]);
        }

    }

    int m, n, res = Integer.MAX_VALUE;
    int[][] mat;
    boolean[][] dp;
    int target;
}

访问数组中的位置使分数最大

139. 单词拆分

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        this.s = s;
        n = s.length();
        set = new HashSet<>(wordDict);
        dp = new int[n];
        Arrays.fill(dp, -1);
        return dfs(0);
    }

    private boolean dfs(int index) {
        if (index == n)
            return true;
        if (dp[index] != -1)
            return dp[index] == 1 ? true : false;
        for (int i = index; i < n; ++i) {
            String sub = s.substring(index, i + 1);
            if (set.contains(sub)) { 
                dp[index] = dfs(i + 1) ? 1 : 0;
                if (dp[index] == 1)
                    return true;
            }
        }
        return false;
    }

    int n;
    String s;
    Set<String> set;
    int[] dp;
}

300. 最长递增子序列2

方法一：记忆化搜索(选或不选)

注意额外处理第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int lengthOfLIS(int[] nums) {
        n = nums.length;
        this.nums = new int[n + 1];
        this.nums[0] = -10001;
        for (int i = 0; i < n; ++i)
            this.nums[i + 1] = nums[i];
        dp = new int[n + 1][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(1, 0);
    }

    public int dfs(int index, int pre) {
        if (index == n + 1)
            return 0;
        if (dp[index][pre] != -1)
            return dp[index][pre];
        int x = nums[index];
        if (index == 0 || x > nums[pre])
            return dp[index][pre] = Math.max(dfs(index + 1, index) + 1, dfs(index + 1, pre));
        return dp[index][pre] = dfs(index + 1, pre);
    }

    int[][] dp;
    int[] nums;
    int n;
    
}

方法二：记忆化搜索(枚举选哪个)

dp不用重复初始化，因为记忆化的是增量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int lengthOfLIS(int[] nums) {
        n = nums.length;
        this.nums = nums;
        dp = new int[n];
        int res = 1;
        for (int i = 0; i < n; ++i) {
            res = Math.max(res, dfs(i));
        }
        return res;
    }

    public int dfs(int index) {
        if (dp[index] != 0)
            return dp[index];
        int res = 1;
        for (int i = index + 1; i < n; ++i) {
            if (nums[i] > nums[index])
                res = Math.max(res, dfs(i) + 1);
        }
        return dp[index] = res;
    }

    int[] dp;
    int[] nums;
    int n;
    
}

方法三：DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length, res = 1;
        // 以i为结尾，最长递增子序列的长度
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

416. 分割等和子集

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public boolean canPartition(int[] nums) {
        int target = 0, n = nums.length;
        for (int x : nums)
            target += x;
        if (target % 2 == 1)
            return false;
        target /= 2;
        dp = new int[n][target + 1];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, nums, target);
    }

    int[][] dp;
    
    public boolean dfs(int index, int[] nums, int target) {
        if (index == nums.length)
            return target == 0 ? true : false;
        if (dp[index][target] != -1)
            return dp[index][target] == 1 ? true : false;
        boolean choose = false, pass = false;
        int x = nums[index];
        if (target - x >= 0) {
            choose = dfs(index + 1, nums, target - x);
        }
        pass = dfs(index + 1, nums , target);
        dp[index][target] = (choose || pass) ? 1 : 0;
        return dp[index][target] == 1 ? true : false;
    }
}

115. 不同的子序列

二刷记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int numDistinct(String s, String t) {
        m = s.length();
        n = t.length();
        this.s = s;
        this.t = t;
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(0, 0);
    }

    public int dfs(int i, int j) {
        // t被匹配返回1
        if (j == n)
            return 1;
        // s到最后也没能匹配到t的最后一个字符，返回0
        if (i == m)
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        // 匹配：选：i，j往下递归；不选：i往下递归
        if (s.charAt(i) == t.charAt(j))
            return dp[i][j] = dfs(i + 1, j + 1) + dfs(i + 1, j);
        return dp[i][j] = dfs(i + 1, j);
    }

    int m, n;
    String s, t;
    int[][] dp;
}

方法三：滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        // s[:i]中t[:j]出现的次数
        int[] dp = new int[n + 1];
        // s,t为空串，匹配
        dp[0] = 1; 
        for (int i = 1; i <= m; ++i) {
            for (int j = n; j >= 1; --j) {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[j] += dp[j - 1];
            }
        }
        return dp[n];
    }
}

方法一：DP

注意初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int numDistinct(String s, String t) {
        /**
        s = "bagg", t = "bag"
        对于bag的最后一个'g'，可以使用它，或者不使用它
         */
         int m = s.length(), n = t.length();
        if (m < n)
            return 0;
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 1;
        for (int i = 1;i <= m; ++i)
            dp[i][0] = 1;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == t.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[m][n];
    }
}

方法二：记忆化搜索

优质题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numDistinct(String s, String t) {
        m = s.length();
        n = t.length();
        dp = new int[m][n];
        for (int[] arr : dp)
            Arrays.fill(arr, -1);
        return dfs(s, t, m - 1, n - 1);
    }

    int m, n;
    int[][] dp;

    private int dfs(String s, String t, int i, int j) {
        if (j < 0)	// base case 当j指针越界，此时t为空串，s不管是不是空串，匹配方式数都是1
            return 1;
        if (i < 0)	// base case i指针越界，此时s为空串，t不是，s怎么也匹配不了t，方式数0
            return 0;
        if (dp[i][j] != -1)
            return dp[i][j];
        if (s.charAt(i) == t.charAt(j))
            return dp[i][j] = dfs(s, t, i - 1, j - 1) + dfs(s, t, i - 1, j);
        else
            return dp[i][j] = dfs(s, t, i - 1, j);
    }
}

2896. 执行操作使两个字符串相等

方法一：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int minOperations(String s1, String s2, int x) {
        n = s1.length();
        int cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < n; ++i) {
            if (s1.charAt(i) == '1')
                ++cnt1;
            if (s2.charAt(i) == '1')
                ++cnt2;
        }
        if (cnt1 % 2 != cnt2 % 2)
            return -1;
        this.s1 = s1;
        this.s2 = s2;
        this.x = x;
        dp = new int[n][n + 1][2];
        for (int[][] a : dp)
            for (int[] b : a)
                Arrays.fill(b, -1);
        return dfs(0, 0, false);
    }

    public int dfs(int index, int key, boolean reverse) {
        if (index >= n)
            return key == 0 && !reverse ? 0 : inf;
        if (dp[index][key][reverse ? 1 : 0] != -1)
            return dp[index][key][reverse ? 1 : 0];
        char ch1 = s1.charAt(index), ch2 = s2.charAt(index);
        if ((ch1 == ch2) == !reverse)
            return dp[index][key][reverse ? 1 : 0] = dfs(index + 1, key, false);
        int res = Math.min(dfs(index + 1, key + 1, false) + x, dfs(index + 1, key, true) + 1);
        if (key > 0)
            res = Math.min(res, dfs(index + 1, key - 1, false));
        return dp[index][key][reverse ? 1 : 0] = res;
    }

    String s1, s2;
    int x, inf = Integer.MAX_VALUE >> 1, n;
    int[][][] dp;
    
}

2897. 对数组执行操作使平方和最大

方法一：位运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public int maxSum(List<Integer> nums, int k) {
        final long MOD = 1_000_000_007;
        int[] cnt = new int[30];
        for (int x : nums) {
            for (int i = 0; i < 30; i++) {
                cnt[i] += (x >> i) & 1;
            }
        }
        long ans = 0;
        while (k-- > 0) {
            int x = 0;
            for (int i = 0; i < 30; i++) {
                if (cnt[i] > 0) {
                    cnt[i]--;
                    x |= 1 << i;
                }
            }
            ans = (ans + (long) x * x) % MOD;
        }
        return (int) ans;
    }
}

Algorithms > Memorization Search
#记忆化搜索
Memorization Search
https://leopol1d.github.io/2023/05/24/memorization-searcch/
作者
Leopold
发布于
2023年5月24日
许可协议