动态规划 八月八日

#该博客根据九章算法视频课程总结#

        动态规划，用空间换时间的算法，避免重复节点的计算，将计算过的结果记录在hash等容器中，用来减少在计算的时间，也叫作记忆化搜索。

目录

目录

#该博客根据九章算法视频课程总结#

动态规划题的特点：

1.计数

2.求最大值最小值

3.求存在性

动态规划题四个步骤

1.确定状态

递归和动态规划的区别：

2.转移方程

3.初始条件和边界情况

 4.计算顺序

例题：

        1.有三种面值的硬币，2 5 7 使用最少的硬币拼出27元。

2.机器人

3.青蛙

4.最长回文字符串（力扣）

5.接雨水（力扣）

---

---

动态规划题的特点：

1.计数

•         有多少种方式走到右下角
•         有多少种方式选出K个数求出最大值Sum

2.求最大值最小值

•         从左下角走到右下角路径的最大数字之和
•         最长上升子序列的值

3.求存在性

•         取石子游戏，先手是否必胜
•         能不能选出K个数使得和为Sum

动态规划题四个步骤

1.确定状态

        简单地说，解动态规划题需要开一个数组，每个数组的F[i]或F[i][j]代表什么

        确定状态需要两个意识：

                1.最后一步（最后的一个数）

                2.子问题

递归和动态规划的区别：

 在图中我们看到，用递归法求解，计算中，有很多点使我们重复计算多次的，当数据量极大的时候，时间复杂度是很大的。为了避免该问题，我们将计算过的值记录下来，以减少计算的时间。

2.转移方程

 [ ]代表数组的下标。

3.初始条件和边界情况

 4.计算顺序

例题：

        1.有三种面值的硬币，2 5 7 使用最少的硬币拼出27元。

class Solution {
    public int demo(int[] A,int M) {
 
        /*
            假设最后一个硬币是a 则剩下的钱为27-a
            f(27)=f(27-a)+1
            转移方程则为 f(27)=min{f(27-2)+1,f(27-5)+1,f(27-7)+1}
            f(x)=min{f[x-2]+1,f[x-5]+1,f[x-7]+1}
            初始条件：f[0]=0;
            边界情况：x-{2,5,7}>0
        * */
        //建立存储数组
        int[] f=new int[M+1];
        int n=A.length;
 
        f[0]=0;
        for (int i=1;i
            //如果拼不出来，就定义为MAX
            f[i]=Integer.MAX_VALUE;
            for (int j=0;j
                if (i>=A[j]&&f[i-A[j]]!=Integer.MAX_VALUE){
                    f[i]=Math.min(f[i-A[j]]+1,f[i]);
                }
            }
        }
 
        if (f[M]==Integer.MAX_VALUE)
            f[M]=-1;
 
        return f[M];
 
    }
}

2.机器人

1.确定状态

        最后只能从右下角的格子的上或左两个格子

        子问题：有X种方式走到上边的格子，有Y中方式走到左边的格子，则最后有X+Y种方式走到右下角的格子

        问题则转为走到这两个格子的问题，因为机器人只能向下走和向右走，因此当到达最右边和最下边时，就变成了只有一种行进方式。

2.转移方程

        f[i][j]=f[i-1][j]+f[i][j-1]

3.初始条件和边界情况

        初始条件： f[0][0]=1

        边界条件：当i==0或j==0时，机器人都只有一种方式从前一个格子行进过来

4.计算顺序

        依次计算0-n行

public class Solution {
   public int demo(int a,int b){
       int[][] f=new int[a][b];
      
 
       for (int i=0;i
           for (int j=0;j
               if (i==0||j==0){
                   f[i][j]=1;
               }
               f[i][j]=f[i][j-1]+f[i-1][j];
           }
       }
       return f[a-1][b-1];
   }
}

3.青蛙

1.确定状态

        如果青蛙能调到n-1块石头，我们考虑他左后跳的依次。

        满足两个条件：

                1.青蛙能调到石头i

                2.青蛙最后一跳的距离大于等于 n-1-i

                 子问题：

                        f[j]表示青蛙能否调到j石头

2.转移方程

        

 OR表示：枚举，即是在for循环中的可能性，只要有一中可能满足，结果就是true

AND表示：并且

3.初始条件和临界情况

        初始条件：f[0]=true

        临界情况：无

4.计算顺序

        从左到右

class Solution1 {
   public boolean demo(int A[]){
 
       boolean[] f=new boolean[A.length];
       f[0]=true;
       for (int j=1;j
            f[j]=false;
            for (int i=0;i
                if (f[i]==true&&(i+A[i]>=j)){
                    f[j]=true;
                    break;
                }
            }
       }
       return f[A.length-1];
   }
 
}

第二层循环检索的是，在在此之前的石头上青蛙有无可能跳过来。

4.最长回文字符串（力扣）

1.确认状态

        字符串是回文字符串，则他的[i+1,j-1]串也是回文字符串

2.转换方程

                P(i,j)=P(i+1,j−1)∧(Si==Sj)

3.临界条件

                 P(i,i)=true

                  P(i,i+1)=(Si==Si+1)

4.计算顺序

                先填充对角线上的结果，单个字符肯定是回文字符串

public class Solution {
 
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) {
            return s;
        }
 
        int maxLen = 1;
        int begin = 0;
        // dp[i][j] 表示 s[i..j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < len; i++) {
            dp[i][i] = true;
        }
 
        char[] charArray = s.toCharArray();
        // 递推开始
        // 先枚举子串长度
        for (int L = 2; L <= len; L++) {
            // 枚举左边界，左边界的上限设置可以宽松一些
            for (int i = 0; i < len; i++) {
                // 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
                int j = L + i - 1;
                // 如果右边界越界，就可以退出当前循环
                if (j >= len) {
                    break;
                }
               
                if (charArray[i] != charArray[j]) {
                    dp[i][j] = false;
                } else {
                    if (j - i < 3) {//j-1-i-1<1
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
 
                // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
 

5.接雨水（力扣）

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (n == 0) {
            return 0;
        }
 
        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
 
        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }
 
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

从左右两边分别遍历，最后累加差值