Elliot

动态规划

• 刷题笔记0x07：不同路径

  算法动态规划2020/12/19

  这篇文章讨论了一个机器人从网格左上角移动到右下角的不同路径数问题。它首先介绍了问题的描述，然后提出了一个递归公式 `f(x, y) = f(x-1, y) + f(x, y-1)` 来计算从起点到坐标点 `(x, y)` 的路径数。接着，文章解释了如何使用二维数组来避免数组索引出现负数，并提供了代码实现。最后，文章还提到了可以用排列组合的方法来解决这个问题。

• 刷题笔记0x08:石子游戏

  动态规划2020/12/19

  这篇文章给出了一个动态规划算法来求解游戏“Nim”的必胜策略，这个问题的条件是：有两堆石子，两人轮流任意取走一堆中任意数量的石子，最后不能取走石子的人输掉游戏。文章旨在回答谁能够赢下游戏，即谁能够让对手不能取走石子。该算法使用了一个三维数组 `dp[i][j][2]` 来存储游戏状态，其中 `i` 表示先手能取石子的位置的最小值，`j` 表示先手能取石子的位置的最大值，`2` 表示先手和后手两种情况。算法通过递推的方式来计算 `dp` 数组，最终得出先手能否赢下游戏的结论。

• 刷题笔记0x09：单词拆分

  动态规划算法2020/12/19

  这篇文章介绍了如何使用动态规划解决一个字符串分割问题，即判断一个给定的字符串能否被空格拆分为一个或多个在字典中出现的单词。文章从分析题意、设计状态转移方程到代码实现，最后还探讨了代码优化方案。文章思路清晰，代码简洁，是一篇优秀的算法题解。