题目
题目链接:
https://www.nowcoder.com/practice/d195a735f05b46cf8f210c4ad250681c
几乎完全相同的题目:
https://www.lintcode.com/problem/92/description
思路
动态规划都是递归递推而来。php答案是动态规划版本,递归版本有
测试用例超时,C++/.JAVA/GO 递归版本能通过所有测试用例
参考答案C++
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param V int整型
* @param num int整型vector
* @return int整型
*/
int boxin(int V, vector<int>& num) {
int maxStore = dfs(num, 0, V);
return V - maxStore;
}
int dfs(vector<int>& arr, int idx, int rest) {
if (rest < 0) return -1;
if (idx == arr.size()) {
return 0;
}
int p1 = dfs(arr, idx + 1, rest);
int p2 = 0;
int next = dfs(arr, idx + 1, rest - arr[idx]);
if (next != -1) {
p2 = next + arr[idx];
}
if (p1 > p2) {
return p1;
}
return p2;
}
};
参考答案Java
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param V int整型
* @param num int整型ArrayList
* @return int整型
*/
public int boxin (int V, ArrayList<Integer> num) {
int maxstore = dfs(num, 0, V);
return V - maxstore;
}
public int dfs(ArrayList<Integer> ll, int idx, int rest) {
if (rest < 0)
return -1;
if (idx == ll.size()) {
return 0;
}
int p1 = dfs(ll, idx + 1, rest);
int p2 = 0;
int next = dfs(ll, idx + 1, rest - ll.get(idx));
if (next != -1) {
p2 = next + ll.get(idx);
}
return Math.max(p1, p2);
}
}
参考答案Go
package main
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param V int整型
* @param num int整型一维数组
* @return int整型
*/
func boxin(V int, num []int) int {
maxStore := dfs(num, 0, V)
return V - maxStore
}
func dfs(num []int, idx int, rest int) int {
if rest < 0 {
return -1
}
if idx == len(num) {
return 0
}
p1 := dfs(num, idx+1, rest)
p2 := 0
next := dfs(num, idx+1, rest-num[idx])
if next != -1 {
p2 = next + num[idx]
}
if p1 > p2 {
return p1
}
return p2
}
参考答案PHP
<?php
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param V int整型
* @param num int整型一维数组
* @return int整型
*/
function boxin( $V , $num )
{
$n = count($num);
$dp=[];
for($i=0;$i<=$n;$i++){
for($j=0;$j<=$V;$j++){
$dp[$i][$j] = 0;
}
}
for($i=$n-1;$i>=0;$i--){
for($rest = 0;$rest<=$V;$rest++){
$p1 = $dp[$i+1][$rest];
$p2 =0;
$next = $rest-$num[$i] <0 ? -1: $dp[$i+1][$rest-$num[$i]];
if($next!=-1){
$p2 = $next+$num[$i];
}
$dp[$i][$rest] = $p1>$p2? $p1:$p2;
}
}
return $V- $dp[0][$V];
}