美团笔试

dfs3.33

用的dp，测试用例都过了，一交0%😡

乱写了一个记搜就过了

背包问题

递归做半天，0%

超时了，原本想把递归换成栈的，时间不够了

这个线性dp,和京东的第二题一样

直接记忆化搜索就可以过

我用的递归 测试用例都过了 提交为0

dp背包，3ms 400KB

蹲

维护长度为sum的数组做dp，dp[i]表示当前用i来满足自当前元素之后的所有元素的满足要求的数量，然后想办法从后到前遍历所有元素维护这个数组，最后输出dp[sum]

dp[i][j]：表示构建新数组来到i位置 此时数组的和还剩余j ==>dp[数组长度][0] = 1: ==>第一列，最后一行答案已知 ==>需要知道：dp[0][sum]的值 ==>dp[i][j] = dp[i + 1][j - k]的和 其中j-k>=0 但是我只能过6%，不知道哪的问题 我的代码，看看佬能看出来我哪有问题 // Scanner sc = new Scanner(System.in); // int n = sc.nextInt(); // int[] resource = new int[n]; // for (int i = 0; i < n; i++) { // resource[i] = sc.nextInt(); // } // int sum = Arrays.stream(resource).sum(); // long[][] dp = new long[n + 1][sum + 1]; // dp[n][0] = 1; // for(int i = n - 1;i >= 0;i--){ // for(int j = 1;j < dp[0].length;j++){ // long res = 0; // for(int k = 1;j - k >= 0;k++){ // if(resource[i] == k) // continue; // res = res + dp[i + 1][j - k] % 1000000007; // } // res += dp[i + 1][j - 1]; // dp[i][j] = res; // } // } // System.out.println(dp[0][sum]);

回溯3.33，超时

想到了是01背包问题，但还是用dfs做了，js简单优化了下3.33