LeetCode上DP题整理汇总_leetcode数位dp题目

完全背包变形

5399.数位成本和为目标值的最大数字

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的 最大 整数：

• 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
• 总成本必须恰好等于 target 。
• 添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "997" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5
1
2
3
4
5
6
7
8
9
10
11
12
13

示例 2：

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。
1
2
3

示例 3：

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。
1
2
3

示例 4：

输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"
1
2

提示：

• cost.length == 9
• 1 <= cost[i] <= 5000
• 1 <= target <= 5000

class Solution {
   
    public String largestNumber(int[] cost, int target) {
   
        String[][] ans = new String[10][target + 1];
        ans[0][0] = "";
        String res = null;
        for(int i = 1; i < 10; i ++){
   
            for(int j = cost[i - 1]; j <= target; j ++){
   
                ans[i][j] = ans[i - 1][j]; // 不取时
                if(cost[i - 1] <= j){
   
                    if(ans[i - 1][j - cost[i - 1]] != null)//第一次取
                        ans[i][j] = max(ans[i][j],i + ans[i - 1][j - cost[i - 1]]);
                    if(ans[i][j - cost[i - 1]] != null)// 多次取
                        ans[i][j] = max(ans[i][j],i + ans[i][j - cost[i - 1]]);
                }
            }
            res = max(res,ans[i][target]);
        }

        return res == null ? "0" : res;
    }
    public String max(String a,String b){
   
        if(a == null)return b;
        if(a.length() != b.length())return a.length() > b.length() ? a : b;
        
        for(int i = 0; i < a.length(); i ++){
   
            if(a.charAt(i) > b.charAt(i))return a;
            else return b;
        }
        return a;
    }
}
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
33
34
35
36
37
38

简单动规

LeetCode - 70.爬楼梯

题目描述：有 N 阶楼梯，每次可以上一阶或者两阶，求有多少种上楼梯的方法。

当你在第i层台阶时，你可以从i - 1, i - 2层台阶 过来，故f[i] = f[i - 1] + f[i - 2];

class Solution {
   
    public int climbStairs(int n) {
   
        int[] f = new int[n + 1];
        f[0] = 1;
        for(int i = 1; i <= n; i++){
   
            if(i > 1)f[i] = f[i - 1] + f[i - 2];
            else f[i] = f[i - 1];
        }
        return f[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

由于当前层数只与前一层，和前两层有关，故可以优化空间为O(1)

class Solution {
   
    public int climbStairs(int n) {
   
        int pre = 0, cur = 1;
        for(int i = 1; i <= n; i ++){
   
            int temp = cur;
            cur = pre + cur;
            pre = temp;
        }
        return cur;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode - 198.大家劫舍

题目描述：抢劫一排住户，但是不能抢邻近的住户，求最大抢劫量。

定义数组f(n,2)，f[n]表示抢到第几家，f(n,0)表示第n家没有抢，f(n,1)表示第n家 已经被打劫过了

class Solution {
   
    public int rob(int[] nums) {
   
        int n = nums.length;
        if(n == 0)return 0;
        if(n == 1)return nums[0];
        int[][] f = new int[n][2];
        for(int i = 0; i < n; i++){
   
            if(i == 0)f[i][1] += nums[i];
            if(i == 1){
   
                f[i][1] = f[i - 1][0] + nums[i];
                f[i][0] = f[i - 1][1];
            }
            if(i >= 2){
   
                f[i][1] = Math.max(Math.max(f[i - 1][0],f[i - 2][0]),f[i - 2][1]) + nums[i];
                f[i][0] = Math.max(Math.max(Math.max(f[i - 1][0],f[i - 2][0]),f[i - 1][1]),f[i - 2][1]);
            }
        }
        return Math.max(f[n - 1][0],f[n - 1][1]);
    }
}
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

可以把第二层状态去掉f[n],表示抢劫到第n家的最大价值

转移方程为： f[i] = max(f[i - 2] + nums[i], f[i - 1]);

class Solution {
   
    public int rob(int[] nums) {
   
        int n = nums.length;
        if(n == 0)return 0;
        int[] f = new int[n];
        for(int i = 0; i < n; i ++){
   
            if(i == 0)f[i] = nums[0];
            if(i == 1)f[i] = Math.max(nums[0],nums[1]);
            if(i >= 2)f[i] = Math.max(f[i - 2] + nums[i],f[i - 1]);
        }
        return f[n - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

由上一题可知，此状态只与前一家，或者前两家有关，所以可以优化空间复杂度为O(1)

class Solution {
   
    public int rob(int[] nums) {
   
        int n = nums.length;
        int pre1 = 0, pre2 = 0;
        for(int i = 0; i < n; i ++){
   
            int cur = Math.max(pre2 + nums[i],pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

LeetCode - 213. 打家劫舍 II

题目描述：如上，但是房子排列成环形而已；

由于成环，故我们偷了第1家，就不能偷最后一家，不偷第一家，就可以偷最后一家；

所以我们有两种情况：偷第一家，和不偷第一家，其他情况转换为上一题求解

class Solution {
   
    public int rob(int[] nums) {
   
        if (nums == null || nums.length == 0) {
   
            return 0;
        }
        int n = nums.length;
        if(n == 1)return nums[0];
        return Math.max(robb(nums,1,n),robb(nums,0,n - 1));
    }
    private int robb(int[] nums, int st,int en){
   
        int pre1 = 0, pre2 = 0;
        for(int i = st; i < en; i ++){
   
            int cur = Math.max(pre2 + nums[i],pre1);
            pre2 = pre1;
            pre1 = cur;
        }
        return pre1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

LeetCode - 64. 最小路径和

题目描述：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

由于只能从上和左边过来，故方程为f(i,j) = min(f(i - 1,j),f(i, j - 1)) + grid(i,j);

class Solution {
   
    public final int MAXN = 0x3f3f3f3f;
    public int minPathSum(int[][] grid) {
   
        if(grid.length == 0 || grid[0].length == 0)return 0;
        int n = grid.length, m = grid[0].length;
        // f[i][j] 表示，在i,j走到i,j位置最小的花费
        int[][] f = new int[n + 1][m + 1];
        // 将 第0行，和0列置为 inf，不可达
        Arrays.<
1
2
3
4
5
6
7
8
9
10