什么是动态规划

  • （Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

什么问题可以用动态规划的思想解决

  • 问题中的状态必须满足最优化原理
  • 问题中的状态必须满足无后效性。

最优化原理

  • 一个过程的最优策略具有这样的性质，即无论其初始状态及初始决策如何，其以后诸决策对以第一个决策所形成的状态作为初始状态的过程而言，必须构成最优策略。

无后效性

  • 下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结。

    意思是：当前的状态已经是一个选择出来的最优状态，而且其之前的状态不会对当前的选择造成影响。

总结一下就是：无后效性质是一个限制条件。即我们可以对之前的决策作出总结才行，如果无法作出总结，就不能使用动态规划去解决问题。

下面用两个力扣上的两个算法题当作例子

例1

  1. 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

    说明：每次只能向下或者向右移动一步。

    示例:

    输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。

    来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/minimum-path-sum

    从该题可以发现，

    设 f(i,j) 函数为最优路径决策函数。

    状态转移方程如下： 当，i = 0, f(0,j) = f(0,j-1) + grid(0,j)

    当，j = 0 , f(i,0) = (f(i-1,0) + grid(i,0)

    当，i>0 && j>0 , f(i,j) = MIN(f(i,j-1) , f(j,i-1) ) + grid(i,j)

    可以看出，是符合无后效性的。

    代码示例:所用代码为 Swift

    class Solution {
       func minPathSum(_ grid: [[Int]]) -> Int {
          
        let rows = grid[0].count
        let columns = grid.count
        var tempArr = Array<[Int]>.init(repeating: Array.init(repeating: 0, count: rows), count: columns)
           
        tempArr[0][0] = grid[0][0]
           
        if rows == 1 && columns == 1{
            return grid[0][0]
        }
   
        for j in 1...rows - 1 {
            tempArr[0][j] = tempArr[0][j - 1] + grid[0][j]
        }
        if columns == 1 {
            return tempArr[columns - 1] [rows - 1]
        }
           
        for i in  1...columns - 1 {
            tempArr[i][0] = tempArr[i - 1][0] + grid[i][0]
        }
        if rows == 1 {
            return tempArr[columns - 1] [rows - 1]
        }
           
        for i in 1...columns - 1 {
            for j in 1...rows - 1 {
                let gr = grid[i][j]
                let tem = tempArr[i - 1][j] < tempArr[i][j - 1] ? tempArr[i - 1][j] : tempArr[i][j - 1]
                tempArr[i][j] = gr + tem
            }
        }
           
        return tempArr[columns - 1][rows - 1]
    }
 }

    利用了一个中间矩阵，作为存矩阵grid(i,j)点的最优路径。

    例2

  2. 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

    示例 1:

    输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

    来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof

    可以看出此题可以用动态规划去解决，因为第 i 个位置存在的最长不重复字符串是有唯一解的。即决策可以有一个总结。

    设f(i)为当到达第i个位置时最长字符串长度函数。g(s)意思是出去记录的字符的下标，在这里用字典记录并更新字符在字符串中所占的位置。

    设 idx 为判断的起始点，并作为起始点的记录。

    状态转移方程如下： 当，g(s) < 0 ， f(i) = f(i - 1) + 1

    当， idx <= g(s) < = i-1 ， f(i) = MAX(f(i - 1), i - idx)

    示例代码如下：

    class Solution {
   
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var a = 0
        lengthOfLongestSubstring_sub(s,&a)
        return a
    }
      
   func lengthOfLongestSubstring_sub(_ str: String, _ len : inout Int) -> Void {
        if str.isEmpty {
            len = 0;
            return
        }
           
        var idx = -1
        var i = 0
        var dic = Dictionary<Character,Int>.init()
           
        for c in str {
            if dic[c] != nil {
                let tem = dic[c]!
                idx =  idx < tem ? tem : idx
                   
            }
            len = len > i - idx   ? len : i - idx
            dic[c] = i
            i = i + 1
        }
    }
}

    动态规划给出了解决问题的思想，并没有给出具体解决方案。这个需要自己练习观察，才能更好的发现问题的规律。

    邮箱：15652628678@163.com