几句话读懂动态规划：动态规划与数学归纳法

2024-07-09 18:18| 来源: 网络整理| 查看: 265

昨天晚上今天凌晨在写动态规划的练习题从两点折腾到四点一连折腾了两个小时有看了一会参考书还是没有搞明白。整什么无向图啊路径啊一点也不新手友好。在这里插入图片描述但后来慢慢的看了看题目和源代码，今天下午突然反应过来：

这不就是数学归纳法么

跟大家分享一下。

在这里插入图片描述首先，我们来回顾一下数学归纳法：

数学归纳法分为两种 1. 这两种的共同点都是已经知道了n=1的时候的情况 2.两者都知道了中间的信息只不过一种知道的只是k-1的信息另一种知道的是1~k-1的所有信息 3.目的都是求n = k时候的函数值

而对应到动态规划的递归写法

上文中的1对应的正好是边界条件上文中的2这对应的正是我们假定已经知道的信息（都可以通过1中的边界求出来）上文中对应的三正是偶们要求的目标

那么解决动态规划这类的问题就变成了以下三步：

抓住边界（作为递归边界，是数学归纳时候的初始状态）找到状态转移方程（也就是数学归纳法中第k项和第k-1项或者前k-1项的关系）之后进行根据上面两点写出递归函数，进行适当的优化。

在这里插入图片描述废话不多说，上例子

例1：完全加括号的矩阵连乘问题

问题描述见我的上一篇博客：https://blog.csdn.net/weixin_42222917/article/details/83342269 这里我们发现：

边界条件是：

当一个括号里只有一个元素的时候：也就是每一个元素都被单独用括号括在一起了（）这个时候返回0，作为边界条件

n = k 最终的结果（也就是第n项）在这里的意义就是所有的括号都被打开之后

而n= k-1则是还差一个括号，所i有的括号都被打开

而n= k 和 n = k-1的关系则是

在这里插入图片描述

例子2：

最长公共子序列问题参见 https://blog.csdn.net/weixin_42222917/article/details/83342710 在这里，

边界条件是：当着两个串中有一个的长度小于零的时候，返回0 n=k 代表着两个最长字串的最长公共子序列 n = k-1 ~n=0 代表了这两个串的子串的最长公共子序列而他们之间的关系如下图

在这里插入图片描述

【本文地址】

公司简介

联系我们