左程云动态规划笔记(自写)

动态规划笔记 动态规划是一种算法思想，解决问题的思路是将问题拆分成小问题，然后逐步解决小问题，最后将解决方案组合起来。今天，我们将学习动态规划的基本概念和实践应用。 动态规划计算模型 动态规划计算模型可以分为两种：从左往右尝试模型和范围尝试模型。 从左往右尝试模型 从左往右尝试模型是指从左边开始尝试，直到达到目标结果。例如，汉诺塔问题就是一个典型的从左往右尝试模型。汉诺塔问题的解决思路是将一个圆盘从A柱子移到C柱子，过程中借助B柱子。 范围尝试模型 范围尝试模型是指在一个范围内尝试不同的解决方案，例如机器人走路问题。机器人走路问题的解决思路是从初始位置M移动到目标位置K，过程中可以走左边或右边。 机器人走路问题 机器人走路问题是指机器人从初始位置M移动到目标位置K的走法有多少种。这个问题可以使用动态规划解决。解决思路是将机器人的移动分为两个方向：左边和右边，然后使用递归函数来解决问题。 最长公共子序列问题 最长公共子序列问题是指两个字符串中最长的公共子序列。这个问题可以使用动态规划解决。解决思路是将两个字符串分为小问题，然后逐步解决小问题，最后将解决方案组合起来。 最长回文自序问题 最长回文自序问题是指一个字符串中最长的回文自序列。这个问题可以使用动态规划解决。解决思路是将字符串分为小问题，然后逐步解决小问题，最后将解决方案组合起来。 字符串转化问题 字符串转化问题是指将一个数字字符组成的字符串转化成对应的字母字符串。这个问题可以使用动态规划解决。解决思路是将字符串分为小问题，然后逐步解决小问题，最后将解决方案组合起来。 动态规划是一种非常有用的算法思想，可以解决很多复杂的问题。通过实践和练习，我们可以更好地掌握动态规划的思想和技术。 代码实现 下面是机器人走路问题的代码实现： ```cpp int RobotWork(int N, int P, int M, int K) { if (P == 0) { if (M == K) return 1; else return 0; } else { if (M == 1) { return RobotWork(N, P - 1, 2, K); } else if (M == N) { return RobotWork(N, P - 1, M - 1, K); } else { return RobotWork(N, P - 1, M - 1, K) + RobotWork(N, P - 1, M + 1, K); } } } ``` 下面是字符串转化问题的代码实现： ```cpp int process(vector<char> str, int i) { if (i == str.size()) { return 1; } else { return process(str, i + 1) + process(str, i + 2); } } ``` 这些代码实现了动态规划的思想，即将问题拆分成小问题，然后逐步解决小问题，最后将解决方案组合起来。