一篇文章让你学会最基本的动态规划

冷不防 2022-12-02 12:29 204阅读 0赞

提到动态规划，仿佛是一个噩梦的开始，那么动态规划是如何出现的呢？为什么有那么多的人会听之而变色，闻之而哑言？

我再知道我要刷动态规划的题的时候，提前就去各大网站视频网站，了解动态规划，先去B站搜索先：第一个播放最多的视频，连看好几次，终于脑袋中有了一些印象，而后又通过这篇文章让我对动态规划更加的了解，以至于不再害怕。

动态规划怎么来的呢？下面我给大家详细的讲解一下我所了解的动态规划；

大家想学的看他的 [动态规划启蒙篇][Link 1]

大家都知道递归，递归是由自己调用自己，去解决重复问题的一种方案，但是呢，在解决重复方案的同时会产生非常之多的重叠子问题，这么多重复的重叠求解的出现无疑是增加了程序运行的速度，于是第一种优化方案就出现了，那就是递推，递推的实现就是在原来求解的基础上，把求得解放入一个数组，在每次求解之前先去这个数组看这个解是够已经存在，已经存在就返回，可以举个例子：

leetcode 120题 [三角形的最小路径和][Link 2]

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

例如，给定三角形：

\[  
     \[2\],  
    \[3,4\],  
   \[6,5,7\],  
  \[4,1,8,3\]  
\]  
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

递归算法：

//递归dfs(深度优先遍历算法)
    func minimumTotal(triangle [][]int) int {
        return dfs(triangle,0,0)
    }
    
    func dfs(triangle [][]int,i,j int)int{
        if len(triangle)==i{
            return 0
        }
        return min(dfs(triangle,i+1,j),dfs(triangle,i+1,j+1))+triangle[i][j]
    }
    func min(a,b int) int{
        if a>b{
            return b
        }else{
            return a
        }
    }

第一次优化：使用递推解决重叠子问题

//递推解决重叠子问题
    func minimumTotal(triangle [][]int) int {
        dp:=make([][]int,len(triangle))
        for i:=0;i<len(triangle);i++{
            dp[i] = make([]int,len(triangle))
        }
        return dfs(triangle,dp,0,0)
    }
    
    func dfs(triangle,dp [][]int,i,j int)int{
        if len(triangle)==i{
            return 0
        }
        if dp[i][j]!=0{
            return dp[i][j]
        }
        dp[i][j] =  min(dfs(triangle,dp,i+1,j),dfs(triangle,dp,i+1,j+1))+triangle[i][j]
        return dp[i][j]
    }
    func min(a,b int) int{
        if a>b{
            return b
        }else{
            return a
        }
    }

那么目前使用递推之后，解决了重叠子问题，那么下一步把它改造为动态规划，动态规划有四个步骤：

1. 状态定义（定义数组元素的含义）dp\[i\]\[j\]表示从i,j出发,到达最后一层的最短路径；

2.初始化

3. 递推求解

使用动态规划目的是做到最优子结构

//按照题意思用了O(n)的空间复杂度做了动态规划,自底向上
    func minimumTotal(triangle [][]int) int {
        if len(triangle)==0||len(triangle[0])==0{
            return 0
        }
        //1. 状态定义,dp[i][j]表示从i,j出发,到达最后一层的最短路径
        length :=len(triangle)
        dp :=make([][]int,length)
    
        //2.初始化
        for i:=0;i<length;i++{
            for j:=0;j<len(triangle[i]);j++{
                if dp[i]==nil{
                    dp[i] = make([]int,len(triangle[i]))
                }
                dp[i][j] = triangle[i][j]
            }
        }
    
        //3.递推求解(和在原来的基础上没有区别)
        for i:=length-2;i>=0;i--{
            for j:=0;j<len(triangle[i]);j++{
                dp[i][j] = min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
            }
        }
        return dp[0][0]
    
    }
    
    func min(a,b int)int{
        if a>b{
            return b
        }
        return a
    }

动态规划算法2

//动态规划算法最优子结构
    func minimumTotal(triangle [][]int) int {
    
        //从下往上遍历一遍,每个元素取得是下一行元素的最小值
    	for i:=len(triangle)-2;i>=0;i--{//从倒数第二行开始,防止越界,最后一行的最小值就是他们本身
    		for j:=0;j<len(triangle[i]);j++{
    			triangle[i][j]+=min(triangle[i+1][j],triangle[i+1][j+1])//triangle中代表的是下一行元素的最小值
    		}
    	}
    	return triangle[0][0]
    }
    
    func min(a,b int) int{
    	if a<b{
    		return a
    	}
    	return b
    }

动态规划算法3，自顶向下

//自顶向下,
    func minimumTotal(triangle [][]int) int {
        if len(triangle)==0||len(triangle[0])==0{
            return 0
        }
        //1. 状态定义,dp[i][j]表示从从0,0开始到达i,j的最短路径
        length :=len(triangle)
        dp :=make([][]int,length)
    
        //2.初始化
        for i:=0;i<length;i++{
            for j:=0;j<len(triangle[i]);j++{
                if dp[i]==nil{
                    dp[i] = make([]int,len(triangle[i]))
                }
                dp[i][j] = triangle[i][j]
            }
        }
    
        //3.递推求解
        for i:=1; i<length;i++{
            for j:=0 ;j<len(triangle[i]);j++{
                //分两种情况:
                    //1. 上一层没有左边值
                    //2. 上一层没有右边值
                    if j-1<0{
                        dp[i][j] = dp[i-1][j]+triangle[i][j]
                    }else if j>=len(dp[i-1]){
                        dp[i][j] = dp[i-1][j-1]+triangle[i][j]
                    }else{
                        dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]
                    }
            }
        }
        result := dp[length-1][0]
        //取最后一个数组中的最小值,就是最小路径和
        for i:=1;i<len(dp[length-1]);i++{
            result = min(result,dp[length-1][i])
        }
        return result
    
    }
    
    func min(a,b int)int{
        if a>b{
            return b
        }
        return a
    }

[Link 1]: https://blog.csdn.net/m0_37907797/article/details/103231054?utm_source=app
[Link 2]: https://leetcode-cn.com/problems/triangle/