力扣11.2

2742. 给墙壁刷油漆

给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：

• 一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
• 一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。

请你返回刷完 n 堵墙最少开销为多少。

数据范围

• 1 <= cost.length <= 500
• cost.length == time.length
• 1 <= cost[i] <= 106
• 1 <= time[i] <= 500

分析1

参考灵神的题解
最初的dfs思想是dfs(i,j,k)表示要刷即将i+1-n的墙，当前付费时间为j，免费时间为k的最少开销，考虑dfs的边界条件

• $ifj-k>=n-ireturn0$，即目前剩下的付费时间能够让剩下的墙都让免费油漆匠来刷
• $ifj>=nreturn0x3f3f3f3f$，所有的油漆匠都使用完，此时返回一个极大值，因为最后答案是取min，因此会忽略这个值

转移为

• $dfs(i,j,k)=min(dfs(i+1,j+time[i],k)+cost[i],dfs(i+1,j,k+1))$

但这样状态太多了，并且时间会超出，必须使用记忆化优化，我们考虑优化状态
我们发现每次比较的都是付费时间和免费时间的相对大小，因此可以将付费时间和免费时间合并为两者的差值

此时

• $dfs(i,j)=min(dfs(i+1,j+time[i])+cost[i],dfs(i+1,j-1))$

边界条件为

• $ifj>=n-ireturn0$
• $ifj>=nreturn0x3f3f3f3f$

这里定义一个dp数组进行记忆化，注意dp的第二维由于是差，因此可能是负数，需要偏移n个单位

代码

class Solution {
public:
    const static int N = 505;
    int dp[N][2 * N]; 
    int n;
    vector<int> cost, time;
    int dfs(int i, int j) { 
        if(j >= n - i) return 0;
        if(i >= n) return 0x3f3f3f3f;
        int& res = dp[i][j + n];
        if(res != -1) return res;
        return res = min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));
    }
    int paintWalls(vector<int>& cost1, vector<int>& time1) {
        cost = cost1;
        time = time1;
        n = cost.size();
        memset(dp, -1, sizeof(dp));
        return dfs(0, 0);
    }
};

分析2

参考灵神的题解
使用01背包进行分析，我们考虑什么时候能选择第i个付费粉刷匠，总墙数维j，需要满足，此时$付费个数+免费个数=j$

• $前i个付费时间和>=j-前i个付费个数$

将前j个付费个数拆成1+1+1…的形式并移项
此时变成了

• ${\sum }_{k=0}^{i-1}time[k]+1\ge j$

这样就变成了【至少型】01背包问题，这题的价值为cost，体积为time，容量为总墙数，前i个物品，体积至少为j的价值为多少。

再使用滚动数组优化一下

代码

class Solution {
public:
    const static int N = 505;
    int dp[2 * N]; 
    int n;
    int paintWalls(vector<int>& cost, vector<int>& time) {
        n = cost.size();
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0;
        for(int i = 0; i < n; i ++ ) {  
            for(int j = n; j >= 0; j -- ) {
                int c = time[i] + 1;
                dp[j] = min(dp[j], dp[max(0, j - c)] + cost[i]);
            }
        }
        return dp[n];
    }
};

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

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

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

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

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

数据范围

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

分析

完全背包

代码

typedef long long LL;
class Solution {
public:
    const static int N = 5005;
    string dp[N];
    string max(string a, string b) {
        if(a[0] == '-') return b;
        else if(b[0] == '-') return a;
        if(a.size() > b.size()) return a;
        else if(a.size() < b.size()) return b;
        int na = a.size();
        for(int i = 0; i < na; i ++ ) {
            if(a[i] > b[i]) return a;
            else if(a[i] < b[i]) return b;
        }
        return a;
    }
    string largestNumber(vector<int>& cost, int target) {
        int n = cost.size();
        for(int i = 0; i <= target; i ++ ) {
            dp[i] = "-";
        }
        dp[0] = "";
        for(int i = n - 1; i >= 0; i -- ) {
            for(int j = cost[i]; j <= target; j ++ ) {
                string l = dp[j - cost[i]] + char((i + 1) + '0');
                dp[j] = max(dp[j], l);
            }
        }
        sort(dp[target].begin(), dp[target].end());
        if(dp[target][0] == '-') return "0";
        reverse(dp[target].begin(), dp[target].end());
        return dp[target];
    }
};