DP动态规划+贪心题目汇总

背包

01背包

416. 分割等和子集

//f[i][j]表示能否从 nums中前i个 选出一个和恰好等于 j 的子序列.这不就是01背包
f[i][j] = f[i-1][j - nums[i]] || f[i-1][j] 选和不选
01背包优化成一维形式，i维度不要，内层循环从target递减
也可以用记忆化搜索做

class Solution {
    public boolean canPartition(int[] nums) {
        //f[i][j]表示能否从 nums中前i个 选出一个和恰好等于 j 的子序列.这不就是01背包
        //f[i][j] = f[i-1][j - nums[i]] || f[i-1][j] 选和不选
        //01背包优化成一维形式，i维度不要，内层循环从target递减
        int n = nums.length;
        int target = 0;
        for(int i = 0; i < n; i ++)
            target += nums[i];
        if(target % 2 != 0) return false;
        target /= 2;
        boolean[] f = new boolean [target+1];
        f[0] = true;
        for(int i = 1; i <= n; i ++) {
            for(int j = target; j >= nums[i-1]; j --) {
                f[j] = f[j - nums[i-1]] || f[j];
            }
        }
        return f[target];
    }
}

完全背包

外层是物品(数组)遍历，内层是限制(容量价值)遍历

279. 完全平方数

完全背包问题

class Solution {
    public int numSquares(int n) {
        int[] f = new int[n+1];
        f[1] = 1;  
        for(int i = 1; i <= n; i ++) {
            f[i] = i; // 最坏的情况就是每次+1
            for(int j = 1 ;j <= n; j ++)
                if(i >= j*j)
                    f[i] = Math.min(f[i], f[i - j*j] + 1);
        }
        return f[n];
    }
}

322. 零钱兑换

也是完全背包问题

for(int i = 1; i <= n; i ++ ) {
    for(int j = c[i-1]; j <= amount; j ++) {
        dp[j] = Math.min(dp[j], dp[j-c[i-1]] + 1);
    }
}

Arrays.fill(dp, amount + 1); //因为是最小值，初始化0会一直是0

class Solution {
    public int coinChange(int[] c, int amount) {
        //dp[i]:表示最小个数
        //dp[j] = min(dp[j], dp[j-c[i]] + 1)
        int n = c.length;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1); //因为是最小值，初始化0会一直是0
        dp[0] = 0;
        for(int i = 1; i <= n; i ++ ) {
            for(int j = c[i-1]; j <= amount; j ++) {
                dp[j] = Math.min(dp[j], dp[j-c[i-1]] + 1);
            }
            
        }
        int ans = dp[amount];
        return ans < amount + 1 ? ans : -1;
    }
}

两个字符串DP

LCR 095. 最长公共子序列

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
    //设 f(i,j)表示第一个字符串的前 i个字符和第二个字符串的前 j个字符的最长公共子序列
        //dp[i][j] = max(dp[i-1][j], dp[i][j-1],dp[i-1][j-1] + 1) 或者 max(dp[i-1][j], dp[i][j-1]）
        //忽略text1[i]或者忽略text2[j]
        //这个是 求两个字符串的公共子序列，不需要len 不是遍历len对len分1 2 更长的情况的
        int n = text1.length(), m = text2.length();
        int[][] dp = new int [n+1][m+1];
        int ans = 0;
        for(int i = 1; i <= n; i ++) {
            for(int j = 1; j <= m; j ++) {
                if(Objects.equals(text1.charAt(i-1),text2.charAt(j-1))) 
                    dp[i][j] = Math.max(Math.max(dp[i-1][j], dp[i][j-1]),dp[i-1][j-1] + 1);
                else 
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[n][m];//两个字符串的最长公共子序列直接返回f[n][m].因为公共子序列后面的一定比前面的长。但是递增子序列就不一定了

    }
}

也不一定两个字符串就 设两变量f[i,j]这样

139. 单词拆分

f[i]:前i个能否被拆分【这个问题其实是单个字符串，从set里匹配单个字符串】
如果能找到j<i f[j]=true 并且 s[j~i]在words里面，那么f[i]也能被拆分

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        //f[i]:前i个能否被拆分
        int n = s.length();
        boolean[] f = new boolean[n+1];
        f[0] = true;
        for(int i = 1; i <= n; i ++) {
            //如果能找到j f[j]=true 并且 s[j~i]在words里面，那么f[i]也能被拆分
            for(int j = i-1; j >= 0; j --) { //因为前面都已经匹配了，这样更快
                if(f[j] && words.contains(s.substring(j, i))) 
                    f[i] = true;
            }
        }
        return f[n];
    }
}

JAVA的substring是开始位置，终止位置。终止位置是开区间不包含他

单个数组字符串DP

5. 最长回文子串

单个数组，dp[i][j] = dp[i+1][j-1] && s[i]==s[j]

遍历len len=2需要特判

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n + 1][n + 1];
        //dp[i][j]:字符串相关一般都是从i到j
        //dp[i][j] = dp[i+1][j-1] && s[i]==s[j]
        int res = 0;
        String resStr = "";
        for(int i = 0; i <= n; i ++){
            dp[i][i] = true;
        }
        
        for(int len = 1; len <= n; len ++) {
            for(int i = 0; i + len -1 < n; i ++) {
                int j = i + len -1;
                if(len == 1) {
                    dp[i][j] = true;
                }
                else if(len == 2) {
                    dp[i][j] = s.charAt(i)== s.charAt(j);
                }
                else {
                    dp[i][j] = dp[i+1][j-1] && (s.charAt(i)==s.charAt(j)); 
                }
                if(dp[i][j] && res < len) {
                    res = len; resStr = s.substring(i,j + 1);
                    //substring(int beginIndex, int endIndex) 
                }
            }
        }
        return resStr;
    }
}

300. 最长递增子序列

单个数组， dp[i] = Math.max(dp[i], dp[j] + 1)

public int lengthOfLIS(int[] nums) {
    //dp[i]:到i的最长递增子序列
    //dp[i] = dp[j]+1 
    int n = nums.length;
    int[] dp = new int [n+1];
    int ans = 0;
    for(int i = 1; i <= n ; i ++ ) {
        dp[i] = 1;
        for(int j =1; j <= n; j ++ ) {
            if(nums[i-1] > nums[j-1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);//位置
    }
    return ans;
}

53.最大子数组和

请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

dp[i] = Math.max(dp[i-1], 0) + nums[i]

class Solution {
    public int maxSubArray(int[] nums) {
        int dp[] = new int[nums.length+1];
        int res  = nums[0];
        dp[0] = Math.max(nums[0],0);
        for(int i = 1; i < nums.length; i ++) {
            dp[i] = Math.max(dp[i-1], 0) + nums[i];
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}

152. 乘积最大子数组

要求连续：

由于存在负数，那么会导致最大的变最小的，最小的变最大的。因此还需要维护当前最小值imin
同时求解当前最大值和当前最小值

由于f[i]只和f[i-1] g[i-1]有关，可用两个变量存

class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        int ans = Integer.MIN_VALUE;
        int imax = 1; 
        int imin = 1;
        for(int i = 1; i <= n; i ++ ) {
            if(nums[i-1] < 0){ 
              int tmp = imax;
              imax = imin;
              imin = tmp;
            }
            imax = Math.max(imax * nums[i-1], nums[i-1]);
            imin = Math.min(imin * nums[i-1], nums[i-1]);
            
            ans = Math.max(ans, imax);
        }
        return ans;
    }
}

198. 打家劫舍

要第i家的最大金额：s[i] = u[i-1]+nums[i]; 则一定不要第i-1家
不要第i家的最大金额：u[i]=max(u[i-1], s[i-1]) 也可能不要第i-1家，也可能要

class Solution {
    public int rob(int[] nums) {
        //要：s[i] = u[i-1]+nums[i]; 不要u[i]=max(u[i-1], s[i-1])
        int len = nums.length;
        int[] s = new int[len], u = new int[len];
        s[0] = nums[0];
        u[0] = 0;
        int ans = s[0];
        for(int i = 1; i < len; i ++) {
            s[i] = u[i-1] + nums[i];
            u[i] = Math.max(u[i-1], s[i-1]);
            ans = Math.max(ans, s[i]);
            ans = Math.max(ans, u[i]);
        }
        return ans;
    }
}

三角形

120. 三角形最小路径和

注意两种，只有一条路，j=0和对角线

dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        //dp[i][j]:到达(i,j)的最小路径和
        //dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j]
        int n = triangle.size();
        //边界没处理好
        
        int[][] dp = new int[n+1][n+1];
        for(int i = 1; i <= n; i ++ ) {
            dp[i][0] = triangle.get(i-1).get(0) + dp[i-1][0];//没有(i-1,j-1)那一条路了
            for(int j = 1; j <= i; j ++) {
                if(j == i) dp[i][j] = dp[i-1][j-1] + triangle.get(i-1).get(j-1);//灭有(i-1,j)那条路 对角线
                else dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i-1).get(j-1);
            }
        }
        int ans = Integer.MAX_VALUE;
        for(int i = 1; i <= n; i++) {
            ans = Math.min(ans, dp[n][i]);
        }
        return ans;
    }
}

杨辉三角：

贪心

121. 买卖股票的最佳时机

遍历所有天i,对于第i天，记录前i天的最小值minn，结果是max(Prices[i]-minn)

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        int minn = 100000;
        for(int i = 0; i < prices.length; i ++) {
            minn = Math.min(minn, prices[i]);//前i天的最小值也可以
            ans = Math.max(prices[i]-minn, ans);
        }
        return ans;
    }
}

55. 跳跃游戏

class Solution {
    public boolean canJump(int[] nums) {
       //dp[i]:nums[i]之前能跳到的最远距离，含i
       //跳到dp[i]: i + nums[i]
       //不跳到dp[i]: dp[i-1] i-1之前能跳的最远距离
       int[] dp = new int [nums.length + 1];
       for(int i = 1; i < nums.length; i ++) {//不用管最后一个
            dp[i] = Math.max(dp[i-1], i + nums[i-1]);
            if(dp[i] < i + 1) return false;//不用管最后一个，因为dp[i]肯定能跳到他后一个
       }
       return true;
    }
}

贪心做法：
while(i > last && i > last + nums[last]) last++;
if(last == i) return false; 说明i前面没有一个满足 i <= last + nums[last]的---->说明没有跳板能跳到i的

class Solution {
    public boolean canJump(int[] nums) {
       for(int i = 1, last = 0; i < nums.length; i ++) {
            while(i > last && i > last + nums[last])  last++;
            if(last == i) return false;//说明i前面没有一个满足 i <= last + nums[last]的---->说明没有跳板能跳到i的
       }
       return true;
    }
}

45. 跳跃游戏 II

dp[i]: 跳到nums[i]的最小次数
从i不能跳到last, last++;
从i能跳到last,那么，dp[i]就是dp[last]+1。无论last离i多远

class Solution {
    public int jump(int[] nums) {
        //dp[i]: 跳到nums[i]的最小次数
       int[] dp = new int [nums.length];
       for(int i = 1, last = 0; i < nums.length; i ++) {
       //从1开始，dp[0]=0啦,last从0计算dp[1]
            //从i不能跳到last, last++;
            //从i能跳到last,那么，dp[i]就是dp[last]+1。无论last离i多远
            while(i > last && i > last + nums[last])  last ++;
            dp[i] = dp[last] + 1;
       }
       return dp[nums.length-1];
    }
}

区间问题

763. 划分字母区间

end == i // 当前区间合并完毕
end, start分别存储当前区间的终止位置的最大值，当前区间的起始位置

class Solution {
    public List<Integer> partitionLabels(String S) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] last = new int[26];
        for (int i = 0; i < n; i++) {
            last[s[i] - 'a'] = i; // 每个字母最后出现的下标
        }

        List<Integer> ans = new ArrayList<>();
        int end = 0, start = 0;// 记录当前这一段的起始位置和终止位置
        for (int i = 0; i < n; i++) {
            end = Math.max(end, last[s[i] - 'a']); // 更新当前区间右端点的最大值
            if (end == i) { // 当前区间合并完毕
                ans.add(end - start + 1); // 区间长度加入答案
                start = i + 1; // 下一个区间的左端点. 因为i是一直变的
            }
        }
        return ans;
    }
}

56. 合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (p, q) -> p[0] - q[0]); // 按照左端点从小到大排序
        List<int[]> res = new ArrayList<>();
        
        int l = intervals[0][0], r = intervals[0][1];
        for(int i = 1; i < intervals.length; i ++) {
            int newl = intervals[i][0], newr = intervals[i][1];
            if(newr < r) //包含 
                continue;
            else if(newl <= r && newr >= r) {
                r = newr;
            }
            else if(newl > r) {//两段不重叠
                res.add(new int[]{l,r});
                l = newl;
                r = newr;
            }
        }
        // 最后一个合并后的区间需要添加到结果中
        res.add(new int[]{l, r});
        
        // 将 List<int[]> 转换为 int[][] 并返回
        return res.toArray(new int[res.size()][]);
    }
}