动态规划思想到底是什么举个例子形象的解释一下

动态规划是一种求解多阶段决策过程最优化问题的方法。它将原问题分解成若干个子问题，通过对子问题的解进行组合，得到原问题的解。

例如，假设我们要在一个长度为n的序列中找到一个最长的递增子序列（LIS），可以使用动态规划算法来解决。假设dp[i]表示以第i个元素结尾的最长递增子序列的长度，那么状态转移方程为：

dp[i] = max(dp[j])+1, 其中j<i且a[j]<a[i]

其中，a[i]表示第i个元素的值。这个方程的意思是，以第i个元素结尾的最长递增子序列的长度，等于前面所有小于a[i]的元素中，以其结尾的最长递增子序列长度的最大值加1。

例如，对于序列{1,3,2,4,5,3,6,7}，dp[1]=1，dp[2]=2，dp[3]=2，dp[4]=3，dp[5]=4，dp[6]=3，dp[7]=4，dp[8]=5。最终的最长递增子序列的长度为5，可以通过dp数组中的最大值得到。

这个例子中，动态规划思想的关键在于将原问题分解成若干个子问题，并通过状态转移方程将子问题的解组合成原问题的解。