s + w[idx], W, memo) + v[idx])
return memo[idx][s]
def solve(self, w, v, W):
n = len(w)
memo = [[-1 for i in range(W + 1)] for j in range(n)]
return self.search(0, w, v, n, 0, W, memo)
这就是dp了，我们把它改一下，改成递推形式的就是我们经常写的dp了
递推式记忆化搜索(dp)
java版
public int solve(int[] w, int[] v, int W) {
int n = w.length;
int[][] dp = new int[n + 1][W + 1];
for (int i = 0; i < n; i++) {
for (int j = 0; j <= W; j++) {
if (j < w[i]) {
dp[i + 1][j] = dp[i][j];
} else {
dp[i + 1][j] = Math.max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
return dp[n][W];
}
python版
def solve(self, w, v, W):
n = len(w)
dp = [[0 for i in range(W + 1)] for j in range(n + 1)]
for i in range(n):
for j in range(W + 1):
if j < w[i]:
dp[i + 1][j] = dp[i][j]
else:
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
return dp[n][W]
至于递推的顺序，从前到后还是从后到前，都是可以的，这个取决于个人的习惯！