0807学习

agile Posted on Aug 7 2023

面试动态规划路径 leetcode学习

-   不同路径-62
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
![robot_maze.png](https://tools.nxcloud.club:12500/images/2023/08/07/robot_maze.png)
`输入：m = 3, n = 7
输出：28`
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 109

---
![20230807-053852-1.jpg](https://tools.nxcloud.club:12500/images/2023/08/07/20230807-053852-1.jpg)

---

```C#
public int UniquePaths2(int m, int n)
{
    var dp = new int[m][];
    for (var i = 0; i < m; i++)
    {
        dp[i] = new int[n];
        dp[i][0] = 1;
    }

Array.Fill(dp[0], 1);
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

return dp[m - 1][n - 1];
}

public int UniquePaths(int m, int n)
{
    if (m == 1)
    {
        return 1;
    }

var dp = new int[2][];
    for (var i = 0; i < 2; i++)
    {
        dp[i] = new int[n];
        dp[i][0] = 1;
    }

Array.Fill(dp[0], 1);
    var index = new[] { 0, 1 };
    var last = 0;
    for (int i = 1; i < m; i++)
    {
        for (int j = 1; j < n; j++)
        {
            var index0 = index[0];
            var index1 = index[1];
            if (i % 2 == 1)
            {
                dp[index1][j] = dp[index0][j] + dp[index1][j - 1];
                last = index1;
            }
            else
            {
                dp[index0][j] = dp[index1][j] + dp[index0][j - 1];
                last = index0;
            }
        }
    }

return dp[last][n - 1];
}
```

-    不同路径 II-63
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1：![robot1.jpg](https://tools.nxcloud.club:12500/images/2023/08/07/robot1.jpg)
`输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右`
提示：
m == obstacleGrid.length
n == obstacleGrid[i].length
1 <= m, n <= 100
obstacleGrid[i][j] 为 0 或 1

---
![20230807-055556-1.jpg](https://tools.nxcloud.club:12500/images/2023/08/07/20230807-055556-1.jpg)
---

```C#
public int UniquePathsWithObstacles(int[][] obstacleGrid)
{
    var row = obstacleGrid.Length;
    var column = obstacleGrid[0].Length;
    var dp = new int[row][];
    var num = 1;
    for (var i = 0; i < row; i++)
    {
        dp[i] = new int[column];
        if (obstacleGrid[i][0] == 1)
        {
            num = 0;
        }

dp[i][0] = num;
    }

num = 1;
    for (var i = 0; i < column; i++)
    {
        if (obstacleGrid[0][i] == 1)
        {
            num = 0;
        }

dp[0][i] = num;
    }

for (int i = 1; i < row; i++)
    {
        for (int j = 1; j < column; j++)
        {
            if (obstacleGrid[i][j] == 1)
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
    }

return dp[row - 1][column - 1];
}
```

-   最小路径和
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例 1：
![minpath.jpg](https://tools.nxcloud.club:12500/images/2023/08/07/minpath.jpg)
`输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。`
提示：
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

---
[![20230807-062109-1.jpg](https://tools.nxcloud.club:12500/images/2023/08/07/20230807-062109-1.jpg)](https://tools.nxcloud.club:12500/image/7xQn)
---

```C#
public int MinPathSum(int[][] grid)
{
    var row = grid.Length;
    var column = grid[0].Length;
    var dp = new int[row][];
    var last = 0;
    for (int i = 0; i < row; i++)
    {
        dp[i] = new int[column];
        dp[i][0] += last + grid[i][0];
        last = dp[i][0];
    }

for (int i = 1; i < column; i++)
    {
        dp[0][i] += grid[0][i] + dp[0][i - 1];
    }

for (int i = 1; i < row; i++)
    {
        for (int j = 1; j < column; j++)
        {
            dp[i][j] += grid[i][j] + Math.Min(dp[i][j - 1], dp[i - 1][j]);
        }
    }

return dp[row - 1][column - 1];
}
```

-   三角形最小路径和-120
给定一个三角形 triangle ，找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

---
[![Snip20230808_5.png](https://tools.nxcloud.club:12500/images/2023/08/08/Snip20230808_5.png)](https://tools.nxcloud.club:12500/image/70Gg)

---

```C#
public int MinimumTotal(IList<IList<int>> triangle)
{
    if (triangle.Count == 1)
    {
        return triangle[0][0];
    }

index++;
            startI = i + 1;
            flag = index == length - 1;
        }
        else
        {
            dp[i] = Math.Min(dp[i - index], dp[i - index - 1]) +
                    triangle[index][i - startI];
            if (flag)
            {
                minDp = Math.Min(dp[i], minDp);
            }
        }
    }

return minDp;
}

public int MinimumTotal2(IList<IList<int>> triangle)
{
    var length = triangle.Count;
    if (length == 1)
    {
        return triangle[0][0];
    }

if (i == length - 1)
            {
                minValue = Math.Min(minValue, triangle[i][j]);
            }
        }
    }

return minValue;
}
```

-   下降路径最小和-931
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

---
![Snip20230808_6.png](https://tools.nxcloud.club:12500/images/2023/08/08/Snip20230808_6.png)
---

```C#
public int MinFallingPathSum(int[][] matrix)
{
    var n = matrix.Length;
    if (n == 1)
    {
        return matrix[0][0];
    }

var dp = new int[2][];
    for (var i = 0; i < 2; i++)
    {
        dp[i] = new int[n];
    }

Array.Copy(matrix[0], dp[0], n);
    var min = int.MaxValue;
    for (int i = 1; i < n; i++)
    {
        var indexTarget = i % 2 == 0 ? 0 : 1;
        var indexLast = i % 2 == 0 ? 1 : 0;
        var flag = i == n - 1;
        for (int j = 0; j < n; j++)
        {
            if (j == 0)
            {
                dp[indexTarget][j] = Math.Min(dp[indexLast][j], dp[indexLast][1]) + matrix[i][j];
            }
            else if (j == n - 1)
            {
                dp[indexTarget][j] = Math.Min(dp[indexLast][j - 1], dp[indexLast][j]) + matrix[i][j];
            }
            else
            {
                dp[indexTarget][j] =
                    Math.Min(dp[indexLast][j], Math.Min(dp[indexLast][j - 1], dp[indexLast][j + 1])) + matrix[i][j];
            }

if (flag)
            {
                min = Math.Min(min, dp[indexTarget][j]);
            }
        }
    }

return min;
}
```

-   下降路径最小和 II-1289
给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。
非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

---

![Snip20230808_7.png](https://tools.nxcloud.club:12500/images/2023/08/08/Snip20230808_7.png)

---

```C#
public int MinFallingPathSum(int[][] grid)
{
    var length = grid.Length;
    if (length == 1)
    {
        return grid[0][0];
    }

for (int i = 1; i < length; i++)
    {
        var currentMinSum = int.MaxValue;
        var currentMinGSum = int.MaxValue;
        var minIndex = 0;
        //获取每一行和最小值，以及次小值
        //注意不是获取当前行最小值，是和最小值，以及次小值
        for (int j = 0; j < length; j++)
        {
            var currentSum = ((cMinIndex != j) ? minSum : minGSum) + grid[i][j];
            if (currentMinSum > currentSum)
            {
                currentMinGSum = currentMinSum;
                minIndex = j;
                currentMinSum = currentSum;
            }
            else
            {
                if (currentMinGSum > currentSum)
                {
                    currentMinGSum = currentSum;
                }
            }
        }

cMinIndex = minIndex;
        minSum = currentMinSum;
        minGSum = currentMinGSum;
    }

return minSum;
}
```

-   最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

---

```C#
public int MaxSubArray(int[] nums)
{
    var length = nums.Length;
    if (length == 1)
    {
        return nums[0];
    }

var dp = nums[0];
    var maxDp = dp;
    for (int i = 1; i < length; i++)
    {
        dp = Math.Max(nums[i], dp + nums[i]);
        maxDp = Math.Max(dp, maxDp);
    }

return maxDp;
}
```

---

-   爬楼梯-70
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

---

```C#
public int ClimbStairs(int n)
{
    var f = 1;
    var s = 2;
    if (n <= 2)
    {
        return n;
    }

var dp = 0;
    for (var i = 2; i < n; i++)
    {
        dp = f + s;
        f = s;
        s = dp;
    }

return dp;
}
```

---

-   买卖股票的最佳时机-121
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
     
---

```C#
public int MaxProfit(int[] prices)
{
    if (prices.Length <= 1)
    {
        return 0;
    }

return maxDp;
}

public int MaxProfit2(int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

var dp = new int[length][];
    for (int i = 0; i < length; i++)
    {
        dp[i] = new int[2];
    }

//dp[*][0] //第0 天不持有股票
    dp[0][0] = 0;
    // dp[*][1] //第0 天持有股票
    dp[0][1] = -prices[0];
    for (int i = 1; i < length; i++)
    {
        //当天不持有股票的最大利润= 前一天不持有股票的利润 和持有股票的利润  的最大值
        dp[i][0] = Math.Max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        //当天持有股票的最大利润= 前一天持有股票的利润 和 当天不持有股票的利润 的最大值
        dp[i][1] = Math.Max(dp[i - 1][1], -prices[i]);
    }

return dp[length - 1][0];
}
```

---

-    买卖股票的最佳时机 II-122
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     总利润为 4 。
示例 3：
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
提示：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

---

```C#
public int MaxProfit(int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

var dp = new int[length][];
    for (int i = 0; i < length; i++)
    {
        dp[i] = new int[2];
    }
    // dp[i][0] 第i天的持有现金，剩余的现金
    // dp[i][1] 第i天的持有股票，剩余的现金
    // 第一天持有现金，现金余额（或利润）是0
    dp[0][0] = 0;
    // 第一天持有股票，钱是借的，利润为负
    dp[0][1] = -prices[0];
    for (int i = 1; i < length; i++)
    {
        // dp[i-1][0] 昨天持有现金，不动
        // dp[i-1][1] 昨天持有股票，今天卖出，收入现金prices[i]
        dp[i][0] = Math.Max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        // dp[i-1][1] 昨天持有股票，不动
        // dp[i-1][0] 昨天持有现金，今天买入，减少现金prices[i]
        dp[i][1] = Math.Max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }
    // 最后一天的现金
    return dp[length - 1][0];
}
```

---

-   买卖股票的最佳时机含冷冻期
给定一个整数数组prices，其中第  prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

---

```C#
public int MaxProfit(int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }
// dp[i][j] 代表第 i 天在 j 状态下的最大利润
        // j 代表今天持有股票的状态，0 为未持有，1 为持有
    var dp = new int[length][];
    for (int i = 0; i < length; i++)
    {
        dp[i] = new int[2];
    }

dp[0][0] = 0;
    dp[0][1] = -prices[0];
    dp[1][0] = Math.Max(dp[0][0], dp[0][1] + prices[1]);
    dp[1][1] = Math.Max(dp[0][1], dp[0][0] - prices[1]);
    for (int i = 2; i < length; i++)
    {
     // 今天未持有的最大利润是以下两者中的最大值：
            // 1. 昨天未持有，今天未持有
            // 2. 昨天持有，今天卖出
        dp[i][0] = Math.Max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
      // 如果今天持有，其中就有一种可能就是今天买的，那么就必须考虑前天的状态
        // 因为前天的状态会影响今天的行为：
        // 1. 昨天持有，今天持有
        // 2. 昨天未持有，此时只能考虑前天未持有状态。否则违反冷冻期规定
        // 而昨天未持有，前天未持有的收益为 dp[i - 2][0]
        dp[i][1] = Math.Max(dp[i - 1][1], dp[i - 2][0] - prices[i]);
    }

return dp[length - 1][0];
}
```
---

-   买卖股票的最佳时机含手续费-714
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

---

```C#
public int MaxProfit(int[] prices, int fee)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

var dp = new int[length][];
    for (int i = 0; i < length; i++)
    {
        dp[i] = new int[2];
    }

dp[0][0] = 0;
    dp[0][1] = -prices[0];
    for (int i = 1; i < prices.Length; i++)
    {
        dp[i][0] = Math.Max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
        dp[i][1] = Math.Max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
    }

return dp[length - 1][0];
}
```

---

-   买卖股票的最佳时机 III-123
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

---

```C#
public int MaxProfit(int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

var dp = new int[length][][];
    for (var i = 0; i < length; i++)
    {
        dp[i] = new int[3][];
        for (var j = 0; j < 3; j++)
        {
            dp[i][j] = new int[2];
        }
    }

dp[0][1][0] = 0;
    dp[0][1][1] = -prices[0];
    dp[0][2][0] = 0;
    dp[0][2][1] = -prices[0];
    for (var i = 1; i < length; i++)
    {
        dp[i][2][0] = Math.Max(dp[i - 1][2][0], dp[i - 1][2][1] + prices[i]);
        dp[i][2][1] = Math.Max(dp[i - 1][2][1], dp[i - 1][1][0] - prices[i]);
        dp[i][1][0] = Math.Max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i]);
        // dp[i - 1][0][0] = 0;
        dp[i][1][1] = Math.Max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i]);
    }

return dp[length - 1][2][0];
}

public int MaxProfit2(int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

var buy1 = -prices[0];
    var buy2 = -prices[0];
    var sell1 = 0;
    var sell2 = 0;
    for (var i = 1; i < length; i++)
    {
        sell2 = Math.Max(sell2, buy2 + prices[i]);
        buy2 = Math.Max(buy2, sell1 - prices[i]);
        sell1 = Math.Max(sell1, buy1 + prices[i]);
        buy1 = Math.Max(buy1, -prices[i]);
    }

return sell2;
}

public int MaxProfit3(int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

var dp1 = new int[length]; //从低到高，dp1[i]表示第i天以及之前的区间所获得的最大利润
    var dp2 = new int[length]; //从高到低，dp2[i]表示第i天开始直到最后一天期间所获得的最大利润
    var min = prices[0];
    var max = prices[length - 1];
    dp1[0] = -prices[0];
    for (var i = 1; i < length; i++)
    {
        dp1[i] = Math.Max(dp1[i - 1], prices[i] - min);
        min = Math.Min(prices[i], min);
    }

for (int i = length - 2; i >= 0; i--)
    {
        dp2[i] = Math.Max(dp2[i + 1], max - prices[i]);
        max = Math.Max(max, prices[i]);
    }

for (var i = 1; i <= length - 1; i++)
    {
        max = Math.Max(dp1[i - 1] + dp2[i], max);
    }

return Math.Max(dp1[length - 1], max);
}
```

---

-    买卖股票的最佳时机 IV-188
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 2：
输入：k = 2, prices = [3,2,6,5,0,3]
输出：7
解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

---

情况四是最通用的情况，对于每一天需要使用不同的 k 值更新所有的最大收益，对应持有 0 份股票或 1 份股票。如果 k 超过一个临界值，最大收益就不再取决于允许的最大交易次数，而是取决于股票价格数组的长度，因此可以进行优化。那么这个临界值是什么呢？

一个有收益的交易至少需要两天（在前一天买入，在后一天卖出，前提是买入价格低于卖出价格）。如果股票价格数组的长度为 n，则有收益的交易的数量最多为 n / 2（整数除法）。因此 k 的临界值是 n / 2。如果给定的 k 不小于临界值，即 k >= n / 2，则可以将 k 扩展为正无穷，此时问题等价于情况二

---

```C#
public int MaxProfit(int k, int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

if (k >= length / 2)
    {
        return __MaxProfit(prices);
    }

var dp = new int[length][][];
    for (var i = 0; i < length; i++)
    {
        dp[i] = new int[k + 1][];
        for (var j = 0; j <= k; j++)
        {
            dp[i][j] = new int[2];
        }
    }

for (var i = 1; i <= k; i++)
    {
        dp[0][i][0] = 0;
        dp[0][i][1] = -prices[0];
    }

for (int i = 1; i < length; i++)
    {
        for (var j = 1; j <= k; j++)
        {
            dp[i][j][0] = Math.Max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
            dp[i][j][1] = Math.Max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
        }
    }

return dp[length - 1][k][0];
}

public int MaxProfit2(int k, int[] prices)
{
    var length = prices.Length;
    if (length <= 1)
    {
        return 0;
    }

if (k >= length / 2)
    {
        return __MaxProfit(prices);
    }

var dp = new int[k + 1][];
    for (var j = 0; j <= k; j++)
    {
        dp[j] = new int[2];
    }

for (var i = 1; i <= k; i++)
    {
        dp[i][0] = 0;
        dp[i][1] = -prices[0];
    }

for (int i = 1; i < length; i++)
    {
        for (var j = 1; j <= k; j++)
        {
            var sell = Math.Max(dp[j][0], dp[j][1] + prices[i]);
            var buy = Math.Max(dp[j][1], dp[j - 1][0] - prices[i]);
            dp[j][0] = sell;
            dp[j][1] = buy;
        }
    }

return dp[k][0];
}

private int __MaxProfit(int[] prices)
{
    var sell = 0;
    var buy = -prices[0];
    for (var i = 1; i < prices.Length; i++)
    {
        var sell2 = Math.Max(sell, buy + prices[i]);
        var buy2 = Math.Max(buy, sell - prices[i]);
        sell = sell2;
        buy = buy2;
    }

return sell;
}
```

-   二叉树中的最大路径和-124
二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。
路径和 是路径中各节点值的总和。=
给你一个二叉树的根节点 root ，返回其 最大路径和

![Snip20230809_8.png](https://tools.nxcloud.club:12500/images/2023/08/09/Snip20230809_8.png)

---

```C#
private int __maxSum = int.MinValue;

public int MaxPathSum(TreeNode root)
{
    if (root == null)
    {
        return 0;
    }

__Help(root);
    return __maxSum;
}

private int __Help(TreeNode root)
{
    if (root.left == null && root.right == null)
    {
        __maxSum = Math.Max(__maxSum, root.val);
        return root.val;
    }

var left = 0;
    if (root.left != null)
    {
        left = __Help(root.left);
    }

var right = 0;
    if (root.right != null)
    {
        right = __Help(root.right);
    }

var r = root.val;
    var lr = left + right;
    var lrMax = Math.Max(left, right);
    var max = Math.Max(lr, lrMax);
    __maxSum = Math.Max(__maxSum, Math.Max(max + r, r));

return Math.Max(r, lrMax + r);
}
```
---

-   最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

---
```C#
public int LengthOfLIS(int[] nums)
{
    if (nums.Length <= 1)
    {
        return 1;
    }

var dp = new int[nums.Length];
    Array.Fill(dp, 1);
    var max = 1;
    for (var i = 1; i < nums.Length; i++)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (nums[j] < nums[i])
            {
                dp[i] = Math.Max(dp[j] + 1, dp[i]);
            }
        }

max = Math.Max(dp[i], max);
    }

return max;
}

// 10,9,2,5,6,3,4,5,7,101,18
// dp数组中表现如下,分别插入
//10
//9
//2
//2,5
//2,5,6
//2,3,6
//2,3,4
//2,3,4,5
//2,3,4,5,7
//2,3,4,5,7,101
//2,3,4,5,7,18
//返回长度6
public int LengthOfLIS2(int[] nums)
{
    var length = nums.Length;
    if (length <= 1)
    {
        return 1;
    }

dp[right + 1] = nums[i];
        }
    }

return len;
}
```

---

-   零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [186, 419, 83, 408], amount = 6249
输出：20

---

```C#
/*
    完全背包之求凑满背包的最少物品数:
    容量->amount; 物品重量->coins[i]; 价值->1; 优化目标->求恰好凑满背包的物品最小价值
    1.状态定义:dp[j]为凑满容量为j的背包所需最少物品数
    2.状态转移:考虑coins[i]
        2.1 当j<coins[i]时:装不下,继承上一个dp[j]的值
        2.2 当j>=coins[i]时:可以装得下,可以选择装或者不装中价值小的(物品数小的)进行转移
            即:dp[j]=min(dp[j],dp[j-coins[i]]+1])
    3.初始化:容量为0,最少要装0个就可以装满->dp[0]=0,看转移方程,其他的要初始化为Integer.MAX_VALUE
    4.遍历顺序:这里求最少的物品数,因此排列与组合均可,这里先物品后容量,物品顺序无所谓,容量必须正序(完全背包)
    5.返回形式:返回如果dp[amount]有转移直接返回,如果没有转移返回-1
     */
public int CoinChange(int[] coins, int amount)
{
    if (amount == 0)
    {
        return 0;
    }

return dp[amount] > amount ? -1 : dp[amount];
}

private int __num;

//递归实现
public int CoinChange2(int[] coins, int amount)
{
    if (amount == 0)
    {
        return 0;
    }

__num = int.MaxValue;
    __HelpDfs(coins, amount, 0);

return __num == int.MaxValue ? -1 : __num;
}

private void __HelpDfs(int[] coins, int amount, int count)
{
    if (amount < 0)
    {
        return;
    }

if (amount == 0)
    {
        __num = Math.Min(__num, count);
    }

foreach (var t in coins)
    {
        __HelpDfs(coins, amount - t, count + 1);
    }
}

//记忆化搜索
public int CoinChange3(int[] coins, int amount)
{
    if (amount == 0)
    {
        return 0;
    }

var dp = new int[amount + 1];
    Array.Fill(dp, int.MaxValue);
    dp[0] = 0;

return __Help(dp, coins, amount);
}

private int __Help(int[] dp, int[] coins, int amount)
{
    if (amount < 0)
    {
        return -1;
    }

if (dp[amount] != int.MaxValue)
    {
        return dp[amount];
    }

if (amount == 0)
    {
        return 0;
    }

var num = int.MaxValue;
    for (var i = coins.Length - 1; i >= 0; i--)
    {
        var t = __Help(dp, coins, amount - coins[i]);
        if (t >= 0 && t < num)
        {
            num = t + 1;
        }
    }

dp[amount] = num == int.MaxValue ? -1 : num;
    return dp[amount];
}
```

---

-   打家劫舍-198
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 400

---

```C#
public int Rob(int[] nums)
{
    if (nums.Length <= 1)
    {
        return nums[0];
    }

var dp = new int[nums.Length];
    dp[0] = nums[0];
    dp[1] = Math.Max(nums[0], nums[1]);
    for (int i = 2; i < nums.Length; i++)
    {
        //i-1偷了，i不能偷，i-2没有偷，i可以偷
        dp[i] = Math.Max(dp[i - 1], dp[i - 2] + nums[i]);
    }

return dp[nums.Length - 1];
}

public int Rob2(int[] nums)
{
    if (nums.Length <= 1)
    {
        return nums[0];
    }

var first = nums[0];
    var second = Math.Max(nums[0], nums[1]);
    for (int i = 2; i < nums.Length; i++)
    {
        var temp = Math.Max(second, first + nums[i]);
        first = second;
        second = temp;
    }

return second;
}
```

---
-    打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000

---

```C#
public int Rob(int[] nums)
{
    var length = nums.Length;
    if (length == 1)
    {
        return nums[0];
    }

if (length == 2)
    {
        return Math.Max(nums[0], nums[1]);
    }

var dp1 = new int[length - 1];
    var dp2 = new int[length - 1];
    dp1[0] = nums[0];
    dp1[1] = Math.Max(nums[0], nums[1]);
    dp2[0] = nums[length - 1];
    dp2[1] = Math.Max(nums[length - 1], nums[length - 2]);
    for (int i = 2; i < length - 1; i++)
    {
        dp1[i] = Math.Max(dp1[i - 1], dp1[i - 2] + nums[i]);
        var j = length - i - 1;
        dp2[i] = Math.Max(dp2[i - 1], dp2[i - 2] + nums[j]);
    }

return Math.Max(dp2[length - 2], dp1[length - 2]);
}

public int Rob2(int[] nums)
{
    var length = nums.Length;
    if (length == 1)
    {
        return nums[0];
    }

if (length == 2)
    {
        return Math.Max(nums[0], nums[1]);
    }

return Math.Max(__RobMax(nums, 0, length - 2), __RobMax(nums, 1, length - 1));
}

private int __RobMax(int[] nums, int start, int end)
{
    var first = nums[start];
    var second = Math.Max(nums[start], nums[start + 1]);
    for (var i = start + 2; i <= end; i++)
    {
        var temp = Math.Max(second, first + nums[i]);
        first = second;
        second = temp;
    }

return second;
}
```

---
-   打家劫舍 III-337
小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

---
![Snip20230810_11.png](https://tools.nxcloud.club:12500/images/2023/08/10/Snip20230810_11.png)

---

![Snip20230810_10.png](https://tools.nxcloud.club:12500/images/2023/08/10/Snip20230810_10.png)

---

```C#
public int Rob(TreeNode root)
{
    var r = __Help(root);
    return Math.Max(r[0], r[1]);
}

private int[] __Help(TreeNode r)
{
    if (r == null)
    {
        return new[] { 0, 0 };
    }

var left = __Help(r.left);
    var right = __Help(r.right);
    //
    var select = r.val + left[1] + right[1];
    var unselect = Math.Max(left[0], left[1]) + Math.Max(right[0], right[1]);
    return new[] { select, unselect };
}
```

---
-   [股票问题系列通解](https://leetcode.cn/circle/article/qiAgHn/)