动态规划经典问题

柔光的暖阳◎ 2022-09-25 02:19 226阅读 0赞

from:https://segmentfault.com/a/1190000004498566\#articleHeader4

## 动态规划 ##

代码实现在[https://github.com/Jensenczx/CodeEveryday][https_github.com_Jensenczx_CodeEveryday]  
维基百科对动态规划的定义

动态规划（英语：Dynamic programming，简称DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题\[1\]和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。

通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化（en:memoization）存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用.

简言之动态规划的思路是通过寻找最优子结构同时记录最优结构，从而将复杂的大问题转化为小问题的求解过程，最近针对于动态规划做了些练习，找到些解题的思路和感觉，下面针对于几个问题来逐步的分析下动态规划。

## 动态规划问题实例 ##

解决动态规划类问题，分为两步：1.确定状态，2.根据状态列状态转移方程  
确定该状态上可以执行的操作，然后是该状态和前一个状态或者前多个状态有什么关联，通常该状态下可执行的操作必定是关联到我们之前的几个状态。

### 1.数字三角形（典型的二维数组问题） ###

问题描述  
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

> \[2\],  
> \[3,4\],  
> \[6,5,7\],  
> \[4,1,8,3\]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

有一个像这样的数字三角形:

７  
　　　　　　３　８  
　　　　　８　１　０  
　　　　２　７　４　４  
　　　４　５　２　６　５

从顶点开始,每个数字向下层走只能有左下和右下两个方向,求出到达最后一行时最大的路径之和.（原题）

状态转移方程：dp\[i\]\[j\]=max(dp\[i-1\]\[j-1\],dp\[i-1\]\[j\])+a\[i\]\[j\];

\---最小值问题转移方程：dp\[i\]\[j\]=min(dp\[i-1\]\[j-1\],dp\[i-1\]\[j\])+a\[i\]\[j\];//注意边界！！！

如果采用朴素算法，我们需要记录每次的行走轨迹，然后对其大小进行比较，最终得出结果，行走轨迹的统计是呈现指数递增的，所以我们要采用动态规划的方法来解决。根据我们的解决方法，先确定状态，也就是每次向下走的一步即为一个状态，然后是状态转移方程，从上一个状态到下一个状态，如果确定最优，当前状态的结果，取决于上一个状态，找到上一个状态，然后确定上一个状态到当前状态转移的方程。记录下每一个状态，我们通过一个二维数组来实现。----典型的两层循环

public int minimumTotal(int[][] triangle) {
            // write your code here
            if(triangle==null||triangle.length==0)
                return 0;
            int len = triangle.length;
            //用来记录每一步的状态
            int [][] cost = new int[len][len];//初始化
            cost[0][0]=triangle[0][0];//第一行为自身
            for(int i=1; i<len; i++){//i=1---后面需要减一
                for(int j=0; j<triangle[i].length; j++){//遍历第i行
                //计算上一个状态的时候，防止出现越界问题
                    int lower = max(0,j-1);//防止j-1<0；
                    int upper = min(j,triangle[i-1].length-1);
                //状态转移方程
                    cost[i][j]= min(cost[i-1][lower],cost[i-1][upper])+triangle[i][j];
                }
            }
            int minCost = Integer.MAX_VALUE;
            for(int k=0; k<triangle[len-1].length; k++){
                minCost = min(minCost,cost[len-1][k]);
            }
    
           return minCost;
        }

**2.背包问题两讲**

这里解决了两张背包问题，一个是确定最多可以装的下多少的背包盛放物品问题，还有一个是背包中放置的物品具有价值，要来确定其价值为多少。解决方法都是通过动态规划来解决。

背包问题1  
问题描述  
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A\[i\]：m=30,A\[17,5,6,7,10\]---最满为28

首先寻找状态，确定将什么作为状态，记录状态，有背包和物品，**物品有放和不放两种状态**，放置的时候可能会对应各种容量，当前的容量下可以放置进的最多的物品取决于上一个物品放置时在该状态下所能够达到的最大状态和当前物品的的大小，这样我们在最后，就可以得到每种容量下，所能放置的物品的最大数量。

public int backPack(int m, int[] A) {//m--背包大小---A---每个物品
            // write your code here
               if (A == null || 0 == A.length || m == 0)
                   return 0;//边界条件
              int len = A.length;//物品个数5
              //初始化了一个数组，
              int[][]  sum = new int[len][m+1];//容量
              for(int i=0;i<len;i++){//边界为0初始化为0
                   sum[i][0] = 0;//第i个商品初重
              }
              for(int j=0;j<m+1;j++){//A[0]=17,J,0-30
                   if(j>=A[0]){
                        sum[0][j] = A[0];
                   }
              }         
              for(int i=1;i<len;i++){
                   for(int j=1;j<m+1;j++){
                        if(j>=A[i]){
                             sum[i][j] = max(sum[i-1][j], sum[i-1][j-A[i]]+A[i]);
                        }else{
                             sum[i][j] = sum[i-1][j];
                        }
                   }
              }
              return sum[len-1][m];
        }

背包问题2  
问题描述  
给出n个物品的体积A\[i\]和其价值V\[i\]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

考虑到价值问题，状态不发生变化，只是对于状态我们所记录的内容方式变化，我们现在记录的是其价值，而不是其放置的物品的大小。

### `public int backPackII(int m, int[] A, int V[]) { // write your code here if(m==0||A==null||V==null||0==A.length) return 0; int len = A.length; int [][]val = new int[len][m+1]; for(int i=0;i<len; i++){ val[i][0]=0; } for(int i=0; i<m+1; i++){ if(i>=A[0]) val[0][i]=V[0]; } for(int i=1; i<len; i++){ for(int j=1;j<m+1; j++){ if(j>=A[i]){ val[i][j] = max(val[i-1][j],val[i-1][j-A[i]]+V[i]); }else{ val[i][j]=val[i-1][j]; } } } return val[len-1][m]; }`      ###

### 3.公共子序列，公共子串问题 ###

公共子串  
给出两个字符串，找到最长公共子串，并返回其长度

状态，字符串的每一位对应另一个字符串的每一个位置，因此通过一个**二维数组来表示这每一个状态位**，然后是**找状态转移方程**，转移方程即为其前一个位置的前一个的比对的结果累计当前的结果，如果相同则加1，否则为0

public int longestCommonSubstring(String A, String B) {
            // write your code here
              if(A==null||B==null||A.length()==0||B.length()==0)
                return 0;
            int lenOfA = A.length();
            int lenOfB = B.length();
            //状态记录结构
            int[][] longSubString = new int[lenOfB][lenOfA];
            int max = 0;
            for(int i=0; i<lenOfA; i++){
                if(B.charAt(0)==A.charAt(i)){
                    longSubString[0][i] = 1;
                    max = 1;
                }
            }
            for(int i=1; i<lenOfB; i++){
                for(int j=0; j<lenOfA; j++){
                //状态转移
                    if(B.charAt(i)==A.charAt(j)){
                        if(j-1>=0)
                        longSubString[i][j] = longSubString[i-1][j-1]+1;
                        else 
                             longSubString[i][j]=1;
                        max = Max(longSubString[i][j],max);
                    }
                }
            }
            return max;
        }

公共子序列  
给出两个字符串，找到最长公共子序列(LCS)，返回LCS的长度。

子序列和子串的区别在于，其值不是仅仅取决于其上一个位置的对应于比对的位置的状态，而是要寻找最大的前面的状态值中最大的一个。

public int longestCommonSubsequence(String A, String B) {
            // write your code here
            if(A==null||B==null||A.length()==0||B.length()==0)
                return 0;
            int lenOfA = A.length();
            int lenOfB = B.length();
               int [][] subsLen = new int[lenOfB][lenOfA];
               int max=0;
               for(int i=0; i<lenOfA; i++){
                   if(A.charAt(i)==B.charAt(0)){
                       subsLen[0][i]=1;
                       max = 1;
                   }
               } 
               for(int i=1; i<lenOfB; i++){
                   for(int j=0; j<lenOfA; j++){
                       if(A.charAt(j)==B.charAt(i)){
                           subsLen[i][j]=Max(subsLen,i-1,j-1)+1;
                           if(subsLen[i][j]>max)
                               max = subsLen[i][j];
                       }
                   }
               }
               return max;
    
        }
        
         public int Max(int[][] array,int end1,int end2){
            if(end2<0)
                return 0;
            int max = array[0][0];
            for(int i=0; i<=end1; i++){
                for(int j=0; j<=end2; j++){
                    if(array[i][j]>max)
                        max = array[i][j];
                }
            }
            return max;
        }

### 4.打劫房屋 ###

问题描述  
假设你是一个专业的窃贼，准备沿着一条街打劫房屋。每个房子都存放着特定金额的钱。你面临的唯一约束条件是：相邻的房子装着相互联系的防盗系统，且当相邻的两个房子同一天被打劫时，该系统会自动报警。  
给定一个非负整数列表，表示每个房子中存放的钱， 算一算，如果今晚去打劫，你最多可以得到多少钱 在不触动报警装置的情况下。

我们可以在通过一个数组来记录下来，我们在每个位置打劫，所能得到的钱，在求下一个状态的时候，遍历前面的与其相隔的所有状态，然后找到一个最大的，但是复杂度比较到达到了n2，空间复杂度为n，对于状态，我们需要记录的只有其前一个，还有与其相隔的所有状态的最大值，因此通过两个数字来表示即可。具体转化方式见代码实现。

public long houseRobber(int[] A) {
            // write your code here
              if(A==null||A.length==0)
                return 0;
            int len = A.length;
            if(len==1)
                return A[0];
            long max1 = A[0];
            long max2 = A[1];
            for(int i=2; i<len; i++){
            long tmp = max2;
                max2 = max1+A[i];
                max1 = tmp;
                //在计算最大值的时候的一个转化
                if(max2<max1)
                    max2 = max1;
            }
            return Max(max1,max2);
        }
           public long Max(long a,long b){
            return a>b?a:b;
        }

### 5.编辑距离 ###

题目描述  
给出两个单词word1和word2，计算出将word1 转换为word2的最少操作次数。

你总共三种操作方法：

*  插入一个字符
 *  删除一个字符
 *  替换一个字符

三种操作，因此我们**在一个状态上面可以进行三种状态的变化**，确定每一个状态，通过第二个字符串和第一个字符串的每一个位置的对应作为一个状态，处在该状态上，我们可以进行的操作，改，进行改操作，那么与之关联的前一个状态是其前一个字符对应另一个字符串的当前对应的前一个字符，增，则是说当前字符串的当前位对应到前一个字符串的前一个位置，删，则为当前字符串的当前位对应前一个字符串的前一个位置。为了增加一个增的位置，需要我们在其前面，所以我们在两个字符串的开始处设置一增加的位置。

public class Solution {
        /**
         * @param word1 & word2: Two string.
         * @return: The minimum number of steps.
         */
        public int minDistance(String word1, String word2) {
            // write your code here
           if(word1==null||word2==null)
                return 0;
            int len1 = word1.length();
            int len2 = word2.length();
            if(len1==0||len2==0)
                return Max(len2,len1);
            int [][]dp = new int[len2+1][len1+1];
            for(int i=0; i<=len1; i++){
                dp[0][i]=i;
            }
            for(int i=0; i<=len2; i++){
                dp[i][0]=i;
            }
               for(int i=1; i<=len2; i++){
                   for(int j=1; j<=len1; j++){
                       if(word2.charAt(i-1)==word1.charAt(j-1)){
                       //状态转化，分别别是删，增，改
                           dp[i][j] = Min(Min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]);
                       }else{
                           dp[i][j] = Min(Min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
                       }
                   }
               }
               return dp[len2][len1];
        }
        
        public int Max(int a,int b){
            return a>b?a:b; 
        }
    
        public int Min(int a,int b){
            return a<b?a:b; 
        }
    }

### 5.N皇后问题 ###

n皇后问题是将n个皇后放置在n\*n的棋盘上，皇后彼此之间不能相互攻击。  
给定一个整数n，返回所有不同的n皇后问题的解决方案。

对于n皇后的问题，下一个皇后的布局位置将与之前的所有王后布局有关，因此通过动态规划，没安置一个皇后就作为一个状态，然后判断之前的已经安放的所有皇后的状态，确定是否可以按这一个皇后，通过递归的方式实现。

public int num1(int n){
        if(n<1)
            return 0;
        int[] record = new int[n];
        return process(0,record,n); 
    }
    
    public int process(int i,int []record,int n){
        if(i==n)
            return 1;
        int res = 0;
        for(int j=0; j<n; j++){
            if(isValid(record,i,j)){
                record[i]=j;
                res+=process(i+1,record,n);
            }
        }
        return res;
    }
    
    public boolean isValid(int[]record,int i,int j){
        for(int k=0; k<i; k++){
            if(j==record[k]||Math.abs(record[k]-j)==Math.abs(i-k)){
                return false;
            }
        }
        return true;
    }

### 后记 ###

对于动态规划的更多问题，将会继续更新，陆续也会写一些贪心算法等常见的算法类型。

[https_github.com_Jensenczx_CodeEveryday]: https://github.com/Jensenczx/CodeEveryday