动态规划-leetcode174

PS：仅作记录。没有什么参考价值。

一些基本概念，参考博客https://www.cnblogs.com/brucemengbm/p/6875340.html

动态规划里面，比较重要的一点就是，基于题目要求，列出动态规划递归方程。
实际应用中能够按下面几个简化的步骤进行设计：

（1）分析最优解的性质。并刻画其结构特征。

（2）递归的定义最优解。

（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值。

（4）依据计算最优值时得到的信息，构造问题的最优解。

然后，参考一些常见的动态规划解决套路。
https://www.cnblogs.com/wuyuegb2312/p/3281264.html

leetcode174这道题，我在了解动态规划算法之前，只是粗略的想通过循环来实现走格子，然后通过判断条件，保证骑士存活，同时反向获得需要的生命值。

int minHP = 0;
int HP=1;
int currentHP=1;

for (int i=0;i<dungeonRowSize;i++) {
    for (int j=0;j<dungeonColSizes;j++) {
        
        int current = *((int *)dungeon+n*i+j);
      //  int nextI = *((int *)dungeon+n*(i+1)+j); 
      //  int nextJ = *((int *)dungeon+n*i+j+1);
        
        if (currentHP + current) <= 0 && current<= 0) {
            HP += -current;
        } else {
            currentHP += current;
        }
        if (HP < minHP) {
            minHP = HP;
        }
    }
}

其实很明显，这个循环根本不能实现走格子。

后来，还是先看了DP的概念，试图建立动态规划的状态改变方程，哈哈，failed。
后来还是看了别人的解析，，，，学到了很多。