微软苏州4面挂经

mazrim-- 发表于 2020-6-2 09:32
关键是有负数，怎么背包？

知道最小的负数是多少就行，假设最小负数是x，则

1. 
   
2. for(int i = 0; i < arr.length; i++)
   
3.     for(int j = x; j <= sum; j++)
   

复制代码

子轩不语 发表于 2020/06/01 20:21:53
combination sum ii? (答案里也有用dfs的）

是原题，但是combination sum ii求方案，这个问的只是可行性

补充内容 (2020-6-1 20:46):
啊，仔细一想就是combination sum ii啊，只写出来DFS也不至于是个挂点啊，不懂面试官是到了最后一轮应付一下还是有意刁难楼主，还是国内面试官默认candidates是刷过题见过原题的？

把所有数字和 target 加上 min(nums) 变成>=0

然后用 dp ?

dp[i][s]   代表 前 i 个数字 组成和为 s 的组合数量

dp[i][s]  = dp[i-1][s] + dp[i][s-n[i]]

感觉这样时空复杂度也不一定比 dfs 小吧

matthew_z 发表于 2020-6-2 14:06
把所有数字和 target 加上 min(nums) 变成>=0

然后用 dp ?

你这是多重背包问题解法吧，如果只能使用一次不知解法对不对
public static int sum(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = dp.length - 1; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[target];
    }

mazrim-- 发表于 2020-6-2 22:12
你这是多重背包问题解法吧，如果只能使用一次不知解法对不对
public static int sum(int[] nums, int ta ...

嗯是的  我递推式写错了 应该

1. dp[i][s]  = dp[i-1][s] + dp[i-1][s-n]  
   

复制代码

所以不用 i 的

请问面的哪个组，有英文面试吗

请问你人是在国内吗？

baihou 发表于 2020/06/03 00:29:15
请问面的哪个组，有英文面试吗

有自我介绍，和简单问答

题偏难啊，要达到最优解的话

最后一轮的题目如果全是非负数的话就是完全背包问题吧?负数的话的确写dp数组的时候会有点麻烦感觉。。