BestSum记忆化Java
创始人
2024-12-01 00:30:51
0

BestSum问题是一个经典的动态规划问题,它要求在给定的一组数中找到一个和为给定数的组合。为了解决这个问题,我们可以使用记忆化的方法来优化计算。

具体而言,我们可以定义一个HashMap来存储已经求解过的子问题,以避免重复计算。在每次递归调用时,我们可以首先检查该问题是否已经求解,如果是,则直接返回存储的结果。否则,我们执行原始递归函数,并将结果存储在HashMap中,以供以后使用。

以下是BestSum问题的Java代码示例,其中使用了记忆化:

import java.util.*;

public class BestSumMemoization {

    public static List bestSum(int targetSum, int[] numbers) {
        return bestSumHelper(targetSum, numbers, new HashMap>());
    }

    private static List bestSumHelper(int targetSum, int[] numbers, Map> memo) {
        if (memo.containsKey(targetSum)) {
            return memo.get(targetSum);
        }
        if (targetSum == 0) {
            return new ArrayList();
        }
        if (targetSum < 0) {
            return null;
        }
        List shortestCombination = null;
        for (int number : numbers) {
            int remainder = targetSum - number;
            List remainderCombination = bestSumHelper(remainder, numbers, memo);
            if (remainderCombination != null) {
                List combination = new ArrayList(remainderCombination);
                combination.add(number);
                if (shortestCombination == null || combination.size() < shortestCombination.size()) {
                    shortestCombination = combination;
                }
            }
        }
        memo.put(targetSum, shortestCombination);
        return shortestCombination;
    }

    public static void main(String[] args) {
        int[] arr1 = {2, 3, 4};
        int[] arr2 = {2, 4};
        int[] arr3 = {7, 14};
        int[] arr4 = {25, 3, 4, 7};
        System.out.println(bestSum(7, arr1));   // [3, 2, 2]
        System.out.println(bestSum(7, arr2));   // [3, 2, 2]
        System.out.println(bestSum(300, arr3)); // null
        System.out.println(bestSum(100, arr4)); // [25, 25

相关内容

热门资讯

2026版教学!蜂娱辅助(辅助... 2026版教学!蜂娱辅助(辅助)好像真的是有辅助方法(有挂工具)在进入蜂娱辅助软件靠谱后,参与本局比...
做出回应!家乡大二的技巧(辅助... 做出回应!家乡大二的技巧(辅助)其实真的有辅助技巧(有挂猫腻)家乡大二的技巧是不是有人用挂微扑克wp...
连日来!四川麻将血战到底定制插... 连日来!四川麻将血战到底定制插件辅助(辅助)好像是真的有辅助软件(确实有挂)1、全新机制【四川麻将血...
第三方插件!微乐自建房辅助可信... 第三方插件!微乐自建房辅助可信吗(辅助)原来真的有辅助工具(有挂技巧)运微乐自建房辅助可信吗辅助工具...
近日!大唐麻将开挂软件(辅助)... 近日!大唐麻将开挂软件(辅助)好像是有辅助方法(有挂方式)1、下载好大唐麻将开挂软件脚本下载之后点击...
值得注意的是!拼十app辅助(... 值得注意的是!拼十app辅助(辅助)都是存在有辅助教程(有挂教程)1、游戏颠覆性的策略玩法,独创攻略...
事发当天!全民内蒙古辅助器(辅... 事发当天!全民内蒙古辅助器(辅助)总是是真的有辅助技巧(有挂攻略)1、上手简单,内置详细流程视频教学...
最新消息!皇豪互众插件(辅助)... 最新消息!皇豪互众插件(辅助)其实真的有辅助方法(详细教程)小薇(辅助器软件下载)致您一封信;亲爱皇...
此事引发广泛关注!点点长牌源码... 此事引发广泛关注!点点长牌源码(辅助)都是真的是有辅助攻略(有挂秘籍)进入游戏-大厅左侧-新手福利-...
备受关注的!桃乐甘肃麻将辅助器... 备受关注的!桃乐甘肃麻将辅助器(辅助)果然真的是有辅助器(有挂透明挂)1)桃乐甘肃麻将辅助器免费钻石...