C# 背包记忆化搜索 代码
public class Solution {
public int PaintWalls(int[] cost, int[] time) {
// 由题意可知:
// 1. n = 付费刷墙个数 + 免费刷墙个数
// 2. 付费刷墙时间和 >= 免费刷墙时间和(免费刷墙个数)
// 由1, 2可得付费刷墙时间和 >= n - 付费刷墙个数即time[a] + time[b] + ... >= n - x (x == time个数)
// 整理得time[a] + 1 + time[b] + 1 + ... >= n
// time[i] + 1看成体积,cost[i]看成价值, 问题转化为从n个物品中总体积至少为n的最小价值总和
int n = cost.Length, INF = 0x3f3f3f3f;
int[,] cache = new int[n, n + 1];
for (int i = 0; i < n; i++){
for (int j = 0; j <= n; j++){
cache[i, j] = -1;
}
}
return DFS(n - 1, n);
// DFS(i, j)表示前i个物品剩余体积至少为j的最小价值总和
int DFS(int i, int j){
// 不需要继续选物品了
if (j <= 0) return 0;
// 顺序不能反, 只有j > 0 且 i < 0才是非法状态
if (i < 0) return INF;
if (cache[i, j] != -1) return cache[i, j];
cache[i, j] = Math.Min(DFS(i - 1, j - time[i] - 1) + cost[i], DFS(i - 1, j));
return cache[i, j];
}
}
}
C# 背包二维DP 代码
public class Solution {
public int PaintWalls(int[] cost, int[] time) {
int n = cost.Length, INF = 0x3f3f3f3f;
int[,] dp = new int[n + 1, n + 1];
for (int i = 0; i <= n; i++){
for (int j = 1; j <= n; j++){
dp[i, j] = INF;
}
}
for (int i = 1; i <= n; i++){
for (int j = 0; j <= n; j++){
int t = j - time[i - 1] - 1;
dp[i, j] = Math.Min(dp[i - 1, Math.Max(t, 0)] + cost[i - 1], dp[i - 1, j]);
}
}
return dp[n, n];
}
}
C# 背包DP优化 代码
public class Solution {
public int PaintWalls(int[] cost, int[] time) {
int n = cost.Length, INF = 0x3f3f3f3f;
int[] dp = new int[n + 1];
Array.Fill(dp, INF);
dp[0] = 0;
for (int i = 1; i <= n; i++){
for (int j = n; j >= 0; j--){
int t = j - time[i - 1] - 1;
dp[j] = Math.Min(dp[Math.Max(t, 0)] + cost[i - 1], dp[j]);
}
}
return dp[n];
}
}
C# 记忆化搜索 代码
public class Solution {
public int PaintWalls(int[] cost, int[] time) {
// DFS(i, j)表示刷前i面墙, 剩余白嫖时间(付费时间-免费时间)的最小开销
// 剩余时间最多只计算到n - 1, 为防止出现负数添加偏移量n, 即m = n * 2 - 1;
// 同时避免n == 1时出现m = 0, 将m设为n * 2, 也可以特判n == 1的情况
int n = cost.Length, m = n * 2;
int INF = 0x3f3f3f3f;
int[,] cache = new int[n, m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
cache[i, j] = -1;
}
}
return DFS(n - 1, n);
int DFS(int i, int j){
// 当剩余时间大于墙的数量, 剩余的墙都可以免费刷
if (j - n > i) return 0;
if (i < 0) return INF;
if (cache[i, j] != -1) return cache[i, j];
// 第i面墙付费DFS(i - 1, j + time[i]) + cost[i],剩余时间累计增加time[i];
// 第i面墙免费DFS(i - 1, j - 1), 消耗一次剩余时间
// 两种情况取最小值
cache[i, j] = Math.Min(DFS(i - 1, j + time[i]) + cost[i], DFS(i - 1, j - 1));
return cache[i, j];
}
}
}