在算法領(lǐng)域，記憶化搜索和動(dòng)態(tài)規(guī)劃是兩種非常重要的算法。Java 語(yǔ)言可以非常方便地實(shí)現(xiàn)這兩種算法，因此在 Java 中應(yīng)用廣泛。下面我們來(lái)分別介紹記憶化搜索和動(dòng)態(tài)規(guī)劃。

記憶化搜索是一種依賴于遞歸的算法。大多數(shù)情況下，遞歸會(huì)產(chǎn)生很多重復(fù)的計(jì)算，導(dǎo)致程序效率低下。記憶化搜索將計(jì)算過(guò)的結(jié)果保存在一個(gè)數(shù)組或哈希表中，避免了重復(fù)計(jì)算。

public static int fib(int n) {
if (n<= 1) {
return n;
}
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
memo[0] = 0;
memo[1] = 1;
return fibHelper(n, memo);
}
private static int fibHelper(int n, int[] memo) {
if (memo[n] != -1) {
return memo[n];
}
memo[n] = fibHelper(n - 1, memo) + fibHelper(n - 2, memo);
return memo[n];
}

上面的代碼是斐波那契數(shù)列的記憶化搜索實(shí)現(xiàn)。現(xiàn)在我們來(lái)看看動(dòng)態(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃是一種自底向上的算法。它將問(wèn)題分解成子問(wèn)題，先計(jì)算子問(wèn)題的解，然后利用子問(wèn)題的解計(jì)算原問(wèn)題的解。與記憶化搜索不同的是，動(dòng)態(tài)規(guī)劃使用循環(huán)而不是遞歸。

public static int rob(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int[] dp = new int[nums.length];
dp[0] = 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];
}

上面的代碼是打家劫舍問(wèn)題的動(dòng)態(tài)規(guī)劃實(shí)現(xiàn)。我們先判斷輸入數(shù)組的長(zhǎng)度，然后創(chuàng)建一個(gè)長(zhǎng)度為數(shù)組長(zhǎng)度的數(shù)組 dp，用于保存最大金額。我們利用循環(huán)逐個(gè)填充 dp 數(shù)組，最終返回 dp[nums.length - 1]。