多步操作最优解

路径和最小

贪心
DP

64. 最小路径和 mid

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

说明：每次只能向下或者向右移动一步。

解法 DP

java

class Solution {
    public int minPathSum(int[][] grid) {

        int r = grid.length, c = grid[0].length;
        int[][] dp = new int[r][c];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < r; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < c; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }
        for (int i = 1; i < r; i++) {
            for (int j = 1; j < c; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[r - 1][c - 1];
    }
}

120. 三角形最小路径和 mid

给定一个三角形 triangle，找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是下标与上一层结点下标相同或者等于上一层结点下标 + 1 的两个结点。
也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

1994 年的 IOI, 现在都成入门了

java

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        if (n == 1) return triangle.get(0).get(0);
        int[][] sum = new int[n][n];
        sum[0][0] = triangle.get(0).get(0);
        int res = Integer.MAX_VALUE;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                int cost = Integer.MAX_VALUE;
                if (j != 0) cost = Math.min(cost, sum[i - 1][j - 1]);
                if (j != i) cost = Math.min(cost, sum[i - 1][j]);
                sum[i][j] = triangle.get(i).get(j) + cost;
                if (i == n - 1) res = Math.min(res, sum[i][j]);
            }
        }
        return res;
    }
}

最少操作次数

72. 编辑距离 hard

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

汉明距离以前也是经典题目, 现在都成 mid 了
字符串转移通常弄成二维的, 考虑如下:
dp[i][j] 代表 word1[:i] 转换成 word2[:j] 需要最少步数

java

class Solution {
    public int minDistance(String word1, String word2) {

        int n1 = word1.length(), n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];

        for (int i = 1; i <= n1; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= n2; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],
                            Math.min(dp[i][j - 1], dp[i - 1][j]));
                }
            }
        }
        return dp[n1][n2];
    }
}

132. 分割回文串 II hard

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文。返回符合要求的最少分割次数。

先找到所有的回文串; 注意, 找所有回文串用不用 dp 的时间复杂度是一样的, 可以不用 dp
到 i 的切割次数 = 1+min(去掉最后一段的次数)

java

class Solution {
    public int minCut(String s) {
        char[] arr = s.toCharArray();
        int n = s.length();
        boolean[][] f = new boolean[n][n];
        /*
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                boolean equal = arr[i] == arr[j];
                if (j - i <= 1) f[i][j] = equal;
                else f[i][j] = equal && f[i + 1][j - 1];
            }
        }
        */
        for (int i = 0; i < n; i++) {
            int l = i, r = i;
            while (l >= 0 && r < n && arr[l] == arr[r]) {
                f[l--][r++] = true;
            }
            l = i;
            r = i + 1;
            while (l >= 0 && r < n && arr[l] == arr[r]) {
                f[l--][r++] = true;
            }
        }
        // [0, i] 的切割次数
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = i;
            if (f[0][i]) {
                // 第1段不需要切割
                dp[i] = 0;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (f[j + 1][i])
                    dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
        return dp[n - 1];
    }
}

279. 完全平方数 mid

给你一个整数 n，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

解法 1 DP

类似背包, $f [i] = m i n (f [i - x * x]) + 1$

java

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                min = Math.min(min, dp[i - j * j]);
            }
            dp[i] = min + 1;
        }
        return dp[n];
    }
}

解法 2 数学

4 平方和定理. 欧拉, 数学的神

java

class Solution {
    public int numSquares(int n) {
        // 4平方和定理 1 2 3 4
        if (perfect(n)) return 1;
        if (perfect4(n)) return 4;
        for (int i = 1; i * i < n; i++) {
            if (perfect(n - i * i)) return 2;
        }
        return 3;
    }

    private boolean perfect(int n) {
        int a = (int) Math.sqrt(n);
        return a * a == n;
    }

    private boolean perfect4(int n) {
        while (n % 4 == 0) n /= 4;
        return 7 == n % 8;
    }

}

921. 使括号有效的最少添加 mid

只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。给定一个括号字符串 s ，在每一次操作中，你都可以在字符串的任何位置插入一个括号
例如，如果 s = "()))" ，你可以插入一个开始括号为 "(()))" 或结束括号为 "())))" 。

返回为使结果字符串 s 有效而必须添加的最少括号数。

可以用栈贪心, 也可以计数
单独的右括号消耗一次添加

java

class Solution {
    public int minAddToMakeValid(String s) {
        int res = 0;
        int cnt = 0;
        int n = s.length();
        for (char c : s.toCharArray()) {
            if (c == '(') cnt++;
            else {
                if (cnt > 0) cnt--;
                else res++;
            }
        }
        res += cnt;
        return res;
    }
}

收益最大

121. 买卖股票的最佳时机 easy

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

一次遍历, 同时更新最小值和最大收益

java

class Solution {
    public int maxProfit(int[] prices) {
        int income = 0;
        int min = prices[0];
        for (int p : prices) {
            if (p < min) min = p;
            else income = Math.max(income, p - min);
        }
        return income;
    }
}

122. 买卖股票的最佳时机 II mid

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。

一次遍历, 在当日可以买入昨天

java

class Solution {
    public int maxProfit(int[] prices) {
        int income = 0;
        int pre = prices[0];
        for (int p : prices) {
            if (p > pre) income += p - pre;
            pre = p;
        }
        return income;
    }
}

123. 买卖股票的最佳时机 III hard

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解法 DP

对于某一天的总收益, 由前一天转移来
状态: 未建仓持仓-1 平仓-1 持仓-2 平仓-2

java

class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        // 第二天开始
        for (int i = 1; i < n; ++i) {
            // 持仓1
            buy1 = Math.max(buy1, -prices[i]);
            // 平仓1
            sell1 = Math.max(sell1, buy1 + prices[i]);
            // 持仓2
            buy2 = Math.max(buy2, sell1 - prices[i]);
            // 平仓2
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
}

198. 打家劫舍 mid

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        // n = max(n-1, n-2 + e)
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }
        return dp[n - 1];
    }
}

213. 打家劫舍 II mid

剑指 Offer II 090. 环形房屋偷盗

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

分治

java

class Solution {
    private int[] nums;

    public int rob(int[] nums) {
        if (nums.length == 1) return nums[0];
        this.nums = nums;
        return Math.max(dp(0, nums.length - 2), dp(1, nums.length - 1));
    }

    private int dp(int start, int end) {
        if (start > end) return 0;
        int n1 = 0;
        int n2 = 0;
        for (int i = start; i <= end; i++) {
            int n3 = Math.max(n1 + nums[i], n2);
            n1 = n2;
            n2 = n3;
        }
        return n2;
    }
}

309. 最佳买卖股票时机含冷冻期 mid

给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易(多次买卖):

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

注意：你不能同时参与多笔交易(你必须在购买前出售掉之前的股票)。

定义一天的 3 种状态: 平仓,建仓=持仓,空仓

java

class Solution {
    public int maxProfit(int[] prices) {
        int length = prices.length;
        int[][] income = new int[length][4];
        income[0][0] = 0; // 平仓
        income[0][1] = -prices[0]; // 持仓|建仓
        income[0][2] = 0; // 空仓

        for (int i = 1; i < length; i++) {
            // 平仓
            income[i][0] = income[i - 1][1] + prices[i];
            // 建仓|持仓
            income[i][1] = Math.max(income[i - 1][1], income[i - 1][2] - prices[i]);
            // 空仓
            income[i][2] = Math.max(income[i - 1][2], income[i - 1][0]);
        }
        return Math.max(income[length - 1][0], income[length - 1][2]);
    }
}

312. 戳气球 hard

有 n 个气球，编号为 0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1 或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。

解法 1 DP

dp[i][j]表示开区间(i,j)中最大乘积
$d p [i] [j] = k \in (i, j) : m a x (d p [i] [k] + d p [k] [j] + n u m s [i] * n u m s [j] * n u m s [k])$

java

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[] arr = new int[n + 2];
        arr[0] = 1;
        arr[n + 1] = 1;
        System.arraycopy(nums, 0, arr, 1, n);
        int[][] dp = new int[n + 2][n + 2];
        // i,j 是边界
        // i 逆序, 因为最后求的是 dp[0][n + 1]
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                int max = 0;
                for (int k = i + 1; k <= j - 1; k++) {
                    max = Math.max(max, dp[i][k] + dp[k][j] + arr[i] * arr[j] * arr[k]);
                }
                dp[i][j] = max;
            }
        }
        return dp[0][n + 1];
    }
}

解法 2 暴力搜

python

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        n = len(nums)
        val = [1] + nums + [1]

        @cache
        def f(left: int, right: int) -> int:
            if left > right:
                return 0
            mx = 0
            for i in range(left, right + 1):
                mx = max(mx, f(left, i - 1) + val[left - 1] * val[i] * val[right + 1] + f(i + 1, right))
            return mx

        return f(1, n)

337. 打家劫舍 III mid

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。

除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。

给定二叉树的 root 。返回在不触动警报的情况下，小偷能够盗取的最高金额。

解法树上 DP

递归, 传入 1 个节点, 返回打劫和不打劫该节点的 2 个结果

javago

java

class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root); // res[0]打劫 res[1]不打劫
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int rob = left[1] + right[1] + node.val;
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{rob, notRob};
    }
}

func dfs(node *TreeNode) (int, int) {
	if node == nil {
		return 0, 0
	}
	lRob, lNotRob := dfs(node.Left)
	rRob, rNotRob := dfs(node.Right)
	rob := lNotRob + rNotRob + node.Val
	notRob := max(lRob, lNotRob) + max(rRob, rNotRob)
	return rob, notRob
}

func rob(root *TreeNode) int {
	return max(dfs(root))
}

455. 分发饼干 easy

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j]。如果 s[j]>= g[i]，我们可以将这个饼干 j 分配给孩子 i，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

Java

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int ig = 0;//胃口
        int is = 0;//尺寸
        while (ig <= g.length - 1 && is <= s.length - 1) {
            if (s[is] >= g[ig]) ig++;
            is++;
        }
        return ig;
    }
}

605 种花问题 easy

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组 flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

解法贪心

java

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int m = flowerbed.length;
        for (int i = 0; i < m; i++) {
            if ((i == 0 || flowerbed[i - 1] == 0)
                    && flowerbed[i] == 0
                    && (i == m - 1 || flowerbed[i + 1] == 0)) {
                n--;
                i++;
            }
        }
        return n <= 0;
    }
}

714. 买卖股票的最佳时机含手续费 mid

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

java

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        // a:持仓 b:空仓
        int a = -prices[0];
        int b = 0;
        for (int i = 1; i < n; i++) {
            int newA = Math.max(a, b - prices[i]);
            int newB = Math.max(b, a - fee + prices[i]);
            a = newA;
            b = newB;
        }
        return Math.max(a, b);
    }
}

开销最小

322. 零钱兑换 mid

给你一个整数数组 coins，表示不同面额的硬币；以及一个整数 amount 表示总金额。

计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

解法 1 记忆化搜索

python

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        @cache
        def dfs(idx, target):
            if idx < 0:
                return 0 if target == 0 else inf
            if target < coins[idx]:
                return dfs(idx - 1, target)

            return min(dfs(idx - 1, target), 1 + dfs(idx - 1, target - coins[idx]))

        res = dfs(len(coins) - 1, amount)
        return res if res < inf else -1

解法 2 DP

java

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

621. 任务调度器 mid

给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个相同种类的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的最短时间。

跟种花问题有点类似, 相同元素必须间隔 n 的最短排列

解法

建立大小为 n+1 的桶
需要冷却的情况: (高频任务频次-1) * (n+1) + 高频任务个数
无需冷却的情况: task.size

pos0	pos1	pos2
A	B	C
A	B
A	B

java

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] cnt = new int[26];
        int maxFrequence = 0;
        for (char c : tasks) {
            cnt[c - 'A']++;
            maxFrequence = Math.max(cnt[c - 'A'], maxFrequence);
        }
        int maxNum = 0;
        for (int c : cnt) {
            if (c == maxFrequence) maxNum++;
        }
        return Math.max(
                tasks.length,
                (maxFrequence - 1) * (n + 1) + maxNum
        );
    }
}

650. 只有两个键的键盘 mid

最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴上一次复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

注意到如果长度为 n, 需要操作 n 次, 第 1 个只 C,不需要 V

解法递归

如果是质数, 那就只能一个个的 V
如果不是质数, minSteps(i) + n/i

java

class Solution {
    int minSteps(int n) {
        if (n == 1) return 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                return i + minSteps(n / i);
            }
        }
        return n;
    }
}

746. 使用最小花费爬楼梯 easy

剑指 Offer II 088. 爬楼梯的最少成本

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

java

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

926. 将字符串翻转到单调递增 mid

如果一个二进制字符串，是以一些 0（可能没有 0）后面跟着一些 1（也可能没有 1）的形式组成的，那么该字符串是单调递增的。

给你一个二进制字符串 s，你可以将任何 0 翻转为 1 或者将 1 翻转为 0。

返回使 s 单调递增的最小翻转次数。

解法 1 DP

以 1 为结尾的最小开销

java

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int[] d0 = new int[n];
        int[] d1 = new int[n];
        int i = 0;
        for (char c : s.toCharArray()) {
            if (i == 0) {
                d0[i] = 0;
                d1[i] = 0;
            } else {
                d0[i] = d0[i - 1];
                d1[i] = Math.min(d0[i - 1], d1[i - 1]);
            }
            if (c == '0')
                d1[i] += 1;
            else
                d0[i] += 1;
            i++;
        }
        return Math.min(d0[n - 1], d1[n - 1]);
    }
}

压缩

java

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int d0 = 0;
        int d1 = 0;
        for (char c : s.toCharArray()) {
            d1 = Math.min(d0, d1);
            if (c == '0') d1++;
            else d0++;
        }
        return Math.min(d0, d1);
    }
}

解法 2 贪心

枚举每个位置, 它前面全是 0, 它后面全是 1
前缀和快速求数量

java

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        char[] arr = s.toCharArray();
        int tot0 = 0;
        for (char c : arr) {
            if (c == '0') tot0++;
        }
        int res = n - tot0;
        int pre0 = 0;
        for (int i = 0; i < n; i++) {
            int c0 = i - pre0;
            int c1 = tot0 - pre0;
            res = Math.min(res, c0 + c1);
            if (arr[i] == '0') pre0++;
        }
        return res;
    }
}

多步操作最优解 ​

路径和最小 ​

64. 最小路径和 mid ​

120. 三角形最小路径和 mid ​

最少操作次数 ​

72. 编辑距离 hard ​

132. 分割回文串 II hard ​

279. 完全平方数 mid ​

921. 使括号有效的最少添加 mid ​

收益最大 ​

121. 买卖股票的最佳时机 easy ​

122. 买卖股票的最佳时机 II mid ​

123. 买卖股票的最佳时机 III hard ​

198. 打家劫舍 mid ​

213. 打家劫舍 II mid ​

309. 最佳买卖股票时机含冷冻期 mid ​

312. 戳气球 hard ​

337. 打家劫舍 III mid ​

455. 分发饼干 easy ​

605 种花问题 easy ​

714. 买卖股票的最佳时机含手续费 mid ​

开销最小 ​

322. 零钱兑换 mid ​

621. 任务调度器 mid ​

650. 只有两个键的键盘 mid ​

746. 使用最小花费爬楼梯 easy ​

926. 将字符串翻转到单调递增 mid ​

多步操作最优解

路径和最小

64. 最小路径和 mid

120. 三角形最小路径和 mid

最少操作次数

72. 编辑距离 hard

132. 分割回文串 II hard

279. 完全平方数 mid

921. 使括号有效的最少添加 mid

收益最大

121. 买卖股票的最佳时机 easy

122. 买卖股票的最佳时机 II mid

123. 买卖股票的最佳时机 III hard

198. 打家劫舍 mid

213. 打家劫舍 II mid

309. 最佳买卖股票时机含冷冻期 mid

312. 戳气球 hard

337. 打家劫舍 III mid

455. 分发饼干 easy

605 种花问题 easy

714. 买卖股票的最佳时机含手续费 mid

开销最小

322. 零钱兑换 mid

621. 任务调度器 mid

650. 只有两个键的键盘 mid

746. 使用最小花费爬楼梯 easy

926. 将字符串翻转到单调递增 mid