典型dp—背包问题

# 0-1背包

0-1背包：有 n个物品，第 i个物品的体积为 w[i]，价值为 v[i]。每个物品至多选一个，求体积和不超过capacity时最大价值和；

当前操作：枚举第 i个物品选 /不选；选，剩余容量减w[i]；不选，剩余容量不变；

子问题：剩余容量为 c时，从前 i个物品中得到最大价值和；

子问题操作：不选，剩余容量为 c时，从前 i-1个物品得到最大价值和；选，剩余容量为 c-w[i]时，从前 i-1个物品得到最大价值和；

递推公式：dfs(i,c)=max(dfs(i-1,c),dfs(i-1,c-w[i])+v[i])

# 494. 目标和 (opens new window)

记忆化搜索：

class Solution {
    int[] nums;
    int[][] memo;
    public int findTargetSumWays(int[] nums, int target) {
        for(int num:nums){
            target+=num;
        }
        if(target<0||target%2==1)
            return 0;
        target/=2;
        int n = nums.length;
        this.nums = nums;
        memo = new int[n][target+1];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(n-1,target);
    }
    int dfs(int i,int c){
        //当c==0则为一个合法方案
        if(i<0)
            return c==0?1:0;
        if(memo[i][c]!=-1)
            return memo[i][c];
        if(c<nums[i])
            return memo[i][c] = dfs(i-1,c);
        return memo[i][c] = dfs(i-1,c)+dfs(i-1,c-nums[i]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

动态规划：

状态定义：从下标 0到 i的数组元素中凑满 c的方法数；

状态转移：dp[i+1][c]=dp[i][c]+dp[i][c-w[i]]（为了防止递推公式下标为负）；

初始状态：根据递推公式，dp[0][0]=1；

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        for(int num:nums){
            target+=num;
        }
        if(target<0||target%2==1)
            return 0;
        target/=2;
        int n = nums.length;
        int[][] dp = new int[n+1][target+1];
        dp[0][0] = 1;
        for(int i=0;i<n;i++){
            for(int c=0;c<=target;c++){
                if(c<nums[i]){
                    dp[i+1][c] = dp[i][c];
                }else{
                    dp[i+1][c] = dp[i][c]+dp[i][c-nums[i]];
                }
            }
        }
        return dp[n][target];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

一维数组优化：可以将物品维度去掉，背包维度只能倒序遍历，否则会出现累加现象；（滚动数组见 LeetCode119.杨辉三角Ⅱ (opens new window)）

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        for(int num:nums){
            target+=num;
        }
        if(target<0||target%2==1)
            return 0;
        target/=2;
        int n = nums.length;
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int num:nums){
            for(int c=target;c>=num;c--){
                dp[c] += dp[c-num];
            }
        }
        return dp[target];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

回溯：

每个元素枚举是 + 或 -；

class Solution {
    int ans;
    int[] nums;
    public int findTargetSumWays(int[] nums, int target) {
        this.nums = nums;
        if(nums.length==0)
            return 0;
        dfs(0,target);
        return ans;
    }
    void dfs(int i,int remain){
        if(i==nums.length){
            if(remain==0)
                ans++;
            return ;
        }
        dfs(i+1,remain+nums[i]);
        dfs(i+1,remain-nums[i]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 416. 分割等和子集 (opens new window)

方法一：记忆化搜索

class Solution {
    int[] nums;
    Map<String,Boolean> memo = new HashMap<>();
    public boolean canPartition(int[] nums) {
        this.nums = nums;
        int sum = Arrays.stream(nums).sum();
        if(sum%2!=0)
            return false;
        int target = sum/2;
        return dfs(nums.length-1,target);
    }
    boolean dfs(int i,int c){
        String key = c+"&"+i;
        if(memo.containsKey(key)){
            return memo.get(key);
        }
        if(i<0)
            return c==0?true:false;
        if(c<nums[i])
            return dfs(i-1,c);
        boolean ret = dfs(i-1,c)||dfs(i-1,c-nums[i]);
        memo.put(key,ret);
        return ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二：动态规划

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if(sum%2!=0)
            return false;
        int target = sum/2;
        int n = nums.length;
        boolean[][] dp = new boolean[n+1][target+1];
        dp[0][0] = true;
        for(int i=0;i<n;i++){
            for(int c=0;c<=target;c++){
                if(c<nums[i])
                    dp[i+1][c] = dp[i][c];
                else
                    dp[i+1][c] = dp[i][c] || dp[i][c-nums[i]];
            }
        }
        return dp[n][target];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 完全背包

完全背包：有 n种物品，第i种物品的体积为 w[i]，价值为 v[i]。每种物品无限次重复选，体积不超过capacity时的最大价值和；

当前操作：枚举第 i个物品选 /不选；选，剩余容量减 w[i]；不选，剩余容量不变；

子问题：剩余容量为 c时，从前 i个物品中得到最大价值和；

子问题操作：不选，剩余容量为 c时，从前 i-1个物品得到最大价值和；选1个，剩余容量为 c-w[i]时，从前 i个物品得到最大价值和；

递推公式：dfs(i,c)=max(dfs(i-1,c),dfs(i,c-w[i])+v[i])

# 322. 零钱兑换 (opens new window)

记忆化搜索：

class Solution {
    int[] coins;
    int[][] memo;
    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        int n = coins.length;
        memo = new int[n+1][amount+1];
        for(int i=0;i<=n;i++){
            Arrays.fill(memo[i],-1);
        }
        int ans = dfs(n-1,amount);
        return ans<Integer.MAX_VALUE/2?ans:-1;
    }
    int dfs(int i,int c){
        if(i<0)
            //背包容量为0，选不了硬币
            return c == 0?0:Integer.MAX_VALUE/2;
        if(memo[i][c]!=-1) 
            return memo[i][c];
        if(c<coins[i]){
            return memo[i][c] = dfs(i-1,c);
        }else{
            memo[i][c] = Math.min(dfs(i-1,c),dfs(i,c-coins[i])+1);
        }
        return memo[i][c];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

动态规划：

状态定义：从下标 0到 i的数硬币中凑满 c的方法数；

递推公式：dp[i+1][c]=min(dp[i][c]+dp[i+1][c-w[i]]+v[i])（防止下标为负）；

初始状态：dp[0][0]=0，dp[0][i]=max/2；

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        Arrays.fill(dp[0],Integer.MAX_VALUE/2);
        dp[0][0] = 0;
        for(int i=0;i<n;i++){
            for(int c=0;c<=amount;c++){
                if(c<coins[i]){
                    dp[i+1][c] = dp[i][c];
                }else{
                    dp[i+1][c] = Math.min(dp[i][c],dp[i+1][c-coins[i]]+1);
                }
            }
        }
        int ans = dp[n][amount];
        return ans<Integer.MAX_VALUE/2?ans:-1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

一维数组优化：背包直接正序遍历，无累加情况；

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE/2);
        dp[0] = 0;
        for(int x:coins){
            for(int c=x;c<=amount;c++){
                dp[c] = Math.min(dp[c],dp[c-x]+1);
            }
        }
        int ans = dp[amount];
        return ans<Integer.MAX_VALUE/2?ans:-1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 518. 零钱兑换 II (opens new window)

记忆化搜索：

class Solution {
    int[][] memo;
    int[] coins;
    public int change(int amount, int[] coins) {
        this.coins = coins;
        int n = coins.length;
        this.memo = new int[n+1][amount+1];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        return dfs(n-1,amount);
    }
    int dfs(int i,int c){
        if(i<0)
            return c==0?1:0;
        if(memo[i][c]!=-1)
            return memo[i][c];
        if(c<coins[i]){
            return memo[i][c] = dfs(i-1,c);
        }else{
            return memo[i][c] = dfs(i-1,c)+dfs(i,c-coins[i]);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

动态规划：

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        dp[0][0] = 1;
        for(int i=0;i<n;i++){
            for(int c=0;c<=amount;c++){
                if(c<coins[i]){
                    dp[i+1][c] = dp[i][c];
                }else{
                    dp[i+1][c] = dp[i][c] + dp[i+1][c-coins[i]];
                }
            }
        }
        return dp[n][amount];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一维数组优化：

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount+1];
        dp[0] = 1;
        for(int x:coins){
            // c从x开始，省去判断逻辑
            for(int c=x;c<=amount;c++){
                dp[c] += dp[c-x];
            }
        }
        return dp[amount];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

# 139. 单词拆分 (opens new window)

方法一：记忆化搜索

class Solution {
    int[] memo;
    public boolean wordBreak(String s, List<String> wordDict) {
        this.memo = new int[s.length()];
        Arrays.fill(memo,-1);
        return dfs(s,wordDict,0);
    }
    boolean dfs(String s,List<String> wordDict,int i){
        if(i==s.length())
            return true;
        if(memo[i]!=-1)
            return memo[i]==1?true:false;
        for(String word:wordDict){
            int len = word.length();
            if(i+len>s.length()){
                continue;
            }
            String subStr = s.substring(i,i+len);
            if(!subStr.equals(word)){
                continue;
            }
            // 可以匹配，压栈
            if(dfs(s,wordDict,i+len)){
                memo[i] = 1;
                return true;
            }
        }
        // 不能匹配，标记为0
        memo[i] = 0;
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

方法二：动态规划

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n+1];// i之前的都能匹配
        dp[0] = true;
        for(int i=0;i<n;i++){
            for(String word:wordDict){
                int len =word.length();
                if(i-len+1>=0 && dp[i-len+1] && word.equals(s.substring(i-len+1,i+1))){
                    dp[i+1] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 279. 完全平方数 (opens new window)

方法一：记忆化搜索

class Solution {
    int ret = 10000;
    int[] memo;
    public int numSquares(int n) {
        if(n==1)
            return 1;
        this.memo = new int[n+1];
        Arrays.fill(memo,-1);
        dfs(n);
        return memo[n];
    }
    int dfs(int n){
        if(n==0)
            return 0;
        if(n==1)
            return 1;
        if(memo[n]!=-1)
            return memo[n];
        int tmp = (int) Math.sqrt(n);
        for(int i=1;i<=tmp;i++){
            ret = Math.min(ret,1+dfs(n-i*i));
        }
        return memo[n] = ret;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二：动态规划

class Solution {
    public int numSquares(int n) {
        int m = (int) Math.sqrt(n);
        int[][] dp = new int[m+1][n+1];
        Arrays.fill(dp[0],10000);
        dp[0][0] = 0;
        for(int i=0;i<m;i++){
            for(int c=0;c<=n;c++){
                if(c<(i+1)*(i+1)){
                    dp[i+1][c] = dp[i][c];
                }else{
                    dp[i+1][c] = Math.min(dp[i][c],dp[i+1][c-(i+1)*(i+1)]+1);
                }
            }
        }
        return dp[m][n];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

← 典型问题—斐波那契类型典型dp—子序列问题→