java动态规划记忆化搜索

动态规划是一种解决问题的算法思想，它通常用于解决具有最优子结构和子问题重叠性质的问题。在动态规划中，我们将问题分解为更小的子问题，并通过解决子问题来解决原始问题。记忆化搜索是动态规划的一种优化技术，它通过使用内存来记录已经计算过的结果，避免重复计算，从而提高算法的效率。

在Java中，可以使用记忆化搜索来实现动态规划。例如，对于LeetCode上的问题135. 分发糖果，可以使用记忆化搜索来优化算法的时间复杂度。具体实现如下：

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

private int tryRob(int[] nums, int index, int[] memo) {
    if (index >= nums.length) {
        return 0;
    }
    if (memo[index] != -1) {
        return memo[index];
    }
    int res = 0;
    for (int i = index; i < nums.length; i++) {
        res = Math.max(res, nums[i] + tryRob(nums, i + 2, memo));
    }
    memo[index] = res;
    return res;
}

这段代码使用了记忆化搜索来避免重叠子问题的重复计算，提高了算法的效率。具体来说，它通过一个数组`memo`来记录已经计算过的结果，如果某个子问题已经计算过，就直接返回结果，否则进行递归计算并将结果存入`memo`数组中。

动态规划和记忆化搜索是解决复杂问题的有效方法，它们可以帮助我们优化算法的时间复杂度，并提高程序的执行效率。在实际应用中，我们可以根据问题的特点选择合适的算法思想和技巧来解决问题。