「笔记」Introduction-下

想清楚了再写代码！想清楚了再写代码！想清楚了再写代码！
问：如何提升动态规划能力？
1.多刷题，锻炼用状态描述问题，转移解决问题的思维
2.了解经典动态的规划类型，积累状态标识与转移的经验。
问：边界情况弄不清楚怎么办？
1.想清楚了再写！
2.记忆化搜索实现
3.在纸上写思路内容等，强制整理思维。

ps：喂你脚下有坑老师讲的真滴好，刚开始写有关的题，脑子一片浆糊，看答案虽然会有马上看懂的感觉，但是提升却并不多。提升最多的是自己手写在纸上从头到尾推出来的题！不过一开始开始要看答案...积累些经验思维后再推效率可能会高些！

动态规划题目特点

动态规划原本是用来解决最值这类的最优化问题，应用于计数、存在判定（本质依旧是计数）的问题也能工作，所以看到最值、计数、存在性判定这三类问题，不妨思考下实用动态规划来解决。
最值、计数、存在性判定三类问题对应在数塔问题中分别为一条路径的最大数字和是多少、求走出一条路径数字和不超过 55 的方案数、求是否存在一条路径的数字和等于 55。

---

状态表示图解？
总的来说动态规划的核心就是状态表示。好的状态表示，动态规划就完成了大半！我们要确定一个既不是那么复杂导致超时，又不过于简单产生后效性的合理状态表示。有了一个合理的状态表示之后，转移方程、决策边界和代码实现都是稍加思考就能得到了。
个人认为最好的动态规划就是无限接近没有后效性的点，也许是错的。

解题顺序：

Step 1 确定状态表示，包含阶段划分与状态表示
Step 2 写出转移方程：帮助你想清楚状态之间到底是如何转移的
Step 3 确定边界：初始 Cases！
Step 4 如果使用递推，考虑一下子状态枚举的顺序。

动态规划代码实现

两种写代码的方式：记忆化搜索与递推。我认为记忆化搜索是一种相对容易理解好上手的代码方式，递推需要考虑更多的东西，优点是支持加入各种高级优化。

1. 记忆化搜索
   记忆化搜索可以理解为在我们确定的状态上进行搜索，然后通过一个额外的数组保存每一个状态的答案，搜索某一状态时，如果有答案就直接返回，否则继续向下搜索并保存计算过的答案！
   好处有以下几点：
   1. 避免计算一些用不到的状态。（能跑到的都是有可能的状态）
   2. 决策边界容易考虑。（原因同1）
   3. 减少思考量，不用考虑状态之间计算顺序，程序只需要立足当前状态与当前状态的子状态。
   4. 实现容易，写出搜索加记忆化就完成了。
   • 5. 可以使用搜索的奇技淫巧优化。（？不理解）
     写一个比较抽象的模板：

int dp[状态表示];
int dfs(状态表示) {
    if (决策边界) return 决策边界答案; // 决策边界
    if (dp[状态表示] != 无效数值) return dp[状态表示]; // 记忆化
    for (当前状态表示的 子状态) dfs(子状态) 更新 dp[状态表示]; // 状态转移
    return dp[状态表示];
}
int solve() {
    memset(dp, 无效数值, sizeof(dp));
    return dfs(原问题状态);
}

2. 递推
   简单明了用For循环嵌套对所有状态进行枚举，即计算所有状态，然后用转移方程更新状态。
   1. 可以加入各种动态规划优化
   2. 没有记忆化搜索中的系统栈的开销，速度较快

学了那么多终于要实战了！

例题0

64.最小路径和
题目：给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

先确定状态表示，从右上到左下每一斜排为一个阶段。
我们回忆一下上文中题目特点的解题顺序：

1. 确定状态表示，包含阶段划分与状态表示。

• 阶段划分：我们把每个位置上的数设定为，阶段就可以简单划分为不同的第阶段。
• 状态划分：两个参数i和j共同实现了状态的划分，在同一阶段下（i与j之和相等），参数不同就对应了了处于同一阶段不同的状态。

2. 写出转移方程：帮助你想清楚状态之间到底是如何转移的。

• 写出转移方程：我们根据题目中的描述来看，题目中有“每次只能向下或者向右移动一步”，这个动态的描述就对应了我们要求得的转移方程。个人认为转移方程是题目中动态描述和状态表示相结合用代码表示出来用来描述题目中动态的方程。

3. 确定边界：初始 Cases！

• 确定边界：键盘只有一个起点，所以,超出边界是不行的，记忆化搜索没有什么

图解

到这里根据终于理清楚思路了，开始写代码！
因为递推要多考虑枚举顺序，我们先写记忆化搜索的代码。

class Solution {
public:
    int dp[550][550];
    vector<vector<int>> grid;

    int dfs(int x, int y) {
        // 搜不下去就是边界
        if (x == 0 && y == 0) return grid[0][0];
        //设定初始化
        if (x < 0 || y < 0) return 2100000000;
        //给不存在的数字设定一个特大的值，实现边界设定。

        // 记忆化，当读到的数字不是我们设定的特殊值，即更新过时我们直接使用已知的值。
        if (dp[x][y] != -1) return dp[x][y];

        // 状态转移
        dp[x][y] = min(dfs(x - 1, y), dfs(x, y - 1)) + grid[x][y];
        return dp[x][y];
    }
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        this->grid = grid;

        memset(dp, -1, sizeof(dp));
        return dfs(n - 1, m - 1);
    }
};

• 说实话，记忆化的实现并不是特别清楚，之后会在扩展里进行细节到步骤的说明。（没打对勾说明还没做这件事，做完了的事情会打对勾）。
  
  
  接下来说递推

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dp[n][m] = {0};

        // 决策边界
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];

        // 状态转移
        for (int i = 1; i < n; i++){
            for (int j = 1; j < m; j++){
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

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

递推需要考虑枚举顺序,写出状态转移第一步可得：

这里我们需要等号右侧都是已知的，所以我们要先对边界进行计算

即，

//边界决策
dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) dp[i][0] = dp[i - 1][0] + grid[i][0];
        for (int j = 1; j < m; j++) dp[0][j] = dp[0][j - 1] + grid[0][j];

通过以上边界的决策，再加上我们的状态转移最内层第一次循环，我们就得到了dp[1][1]的值
然后for循环中接下来我们会求dp[1][2]，需要的值就是dp[1][1]和dp[0][2]...
以此类推，我们就能获得我们的所有的值。

之所以我们没有和记忆化搜索一样用到实现边界设定的代码。
if (x < 0 || y < 0) return 2100000000;
是因为我们用for已经对范围进行了限定。

总结

1. 动态规划以状态表示为核心，需要确定转移方程与边界情况
2. 满足三条基本性质：最优子结构、无后效性、子问题重叠
3. 解决最值、计数、存在性判定三类问题
4. 使用记忆化搜索或递推地方式实现

---

以上就是Introduction这节课中所学到的全部知识，后期我还会在扩展中对我写过的题目连接到个人思考里，大家感兴趣可以看看。