接上文：LEETCODE常见算法之动态规划DP超详细白话讲解(上)
上一篇文章，我们使用了一道简单的例子来解释了动态规划的解题思路。本文我们来挑战一道相对复杂的问题，来对动态规划有一个更加深刻的理解。
先看例题：
LEETCODE 1312. 让字符串成为回文串的最少插入次数
给你一个字符串 s ，每一次操作你都可以在字符串的任意位置插入任意字符。
请你返回让 s 成为回文串的 最少操作次数 。
「回文串」是正读和反读都相同的字符串。
动态规划是Leetcode中比较常见的一类题型，面试时也经常被问到，还记得刚开始刷题时，我对这种题目非常恐惧，经常一头雾水，完全找不到思路。甚至看了别人的讲解后依然一知半解。但随着刷题量的增加，突然发现动态规划也没有那么复杂，绝大部分的题目都是大同小异，甚至让我感觉很多Hard级别的题目中，动态规划题目是相对容易的。本篇文章，我决定用实际的例子来分析，让大家明白动态规划到底是何方神圣。
先看下动态规划的定义：
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
摘自维基百科
定义里有一句话非常关键，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。如果你无法理解这句话的含义没有关系，下面我们会用实际的例子来说明。
另外，什么题适合使用动态规划来解题呢？这是一个非常有价值的问题，虽然我还没有刷满Leetcode的全部题目，不过我还是总结出了两点心得：
继续阅读题目大意：
有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
注意空字符串可被认为是有效字符串。
题目大意：
方阵中战斗力最弱的 K 行
给你一个大小为 m * n 的方阵 mat，方阵由若干军人和平民组成，分别用 1 和 0 表示。
请你返回方阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
继续阅读