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];
        }
    }
}