知识卡片

普通读书笔记卡 · 5654.c.3.b.3.a.1

先定义状态含义再写转移

理解等级:中级

动态规划先明确一次决策及状态变量,逐字说明每个表项回答哪个子问题,再列出可能来源、合并运算、基本情况和求值顺序。计算某状态前,所依赖的状态必须已经可用。

“最大/最小”等字眼只能提示候选,不能证明一定适合DP;计数问题也可能适用。若状态含义、来源覆盖或边界无法解释,就应回到具体决策,而不是先画表再猜公式。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      描述决策,定义状态,建立 表,推导状态转移方程,确定边界条件等。 为了更形象地展示解题步骤,我们使用一个经典问题“最小路径和”来举例。 给定一个 的二维网格grid ,网格中的每个单元格包含一个非负整数,表示该单元格 的

    参考来源

    - 位置:《Hello 算法--Go版本》第14章《动态规划》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/7.html;spine 6,归一字符[15537,15647)) - 结论依据:实际问题判断加减项及三步最小路径解题流程,保留启发而非硬分类。 - 原始内容:描述决策,定义状态,建立 表,推导状态转移方程,确定边界条件等。 为了更形象地展示解题步骤,我们使用一个经典问题“最小路径和”来举例。 给定一个 的二维网格grid ,网格中的每个单元格包含一个非负整数,表示该单元格 的