动态规划较为简单的两个示例

动态规划是编程算法里边经常会用到的一种解决问题的思路，这里向大家介绍两个相对比较简单的示例。

示例1：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

示例2：给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

其中，第1题中可以将路径数目用二维数组path[m-1][n-1]来表示，path[i][j]就表示为从[0][0]位置起始开始走到[i][j]位置可能的路径。具体的实现方法和代码注释请参考链接。data-structures-algorithms/dp/unique-paths.cpp at main · kindlytree/data-structures-algorithms (github.com)

第2题，假设需要拼接的字符串的长度为s，则可以用一个can_concat[s+1]的数组来标记每一个从开始到index的位置是否可以有字典的单词标记出来。具体代码可以参考链接：data-structures-algorithms/dp/word-break.cpp at main · kindlytree/data-structures-algorithms (github.com)