【力扣】从零开始的动态规划

【力扣】从零开始的动态规划

文章目录

• 【力扣】从零开始的动态规划
• • 开头
  • 139. 单词拆分
  • • 解题思路
    • 45. 跳跃游戏 II
    • • 解题思路
      • 5. 最长回文子串
      • • 解题思路
        • 1143. 最长公共子序列
        • • 解题思路
          • 931. 下降路径最小和
          • • 解题思路

              开头

              本力扣题解用5题来引出动态规划的解题步骤，用于本人进阶掌握动态规划,在刷题过程中写下的一些解题步骤与思路，供大家一起学习

              139. 单词拆分

              139. 单词拆分

              给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

              **注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

              解题思路

              ​ 状态表示: dp[i]表示字符串以0到i-1的字符串，能否组成字串

              ​ 初始状态：dp[0]=true，没有字符串的情况肯定为true,如果这个为false,那么后面全部为false

              ​ 状态转移方程:

              ​ 可以把一个字符串来看成两段,0~j-1和j~i,前面一半可以看成dp[j],因为看下状态表示就知道了，dp[i]表示字符串以0到i-1的字符串， 带入j得dp[j]表示字符串以0到j-1的字符串。

              ​ 后一半直接在哈希表中找子串是否存在，找到了就是true,如果两个字串同时为true,那么dp[i]=true

              ​ 因为以0~i的字符串的分解的情况有很多种，只要其中一种为true,那么就是true，直接break；

              ​ 所以动态转移方程为:

                          if(dp[j] && set.contains(s.substring(j,i)))            {                dp[i]=true;                break;            }

              import java.util.HashSet;import java.util.Set;class Solution {    public boolean wordBreak(String s, List wordDict) {        Set set=new HashSet(wordDict);        int n=s.length();        boolean[] dp=new boolean[n+1];        dp[0]=true;        //从第i个字符结束的        for(int i=0;i            for(int j=0;j                if(dp[j] && set.contains(s.substring(j,i)))                {                    dp[i]=true;                    break;                }            }        }        return dp[n];    }}    public int jump(int[] nums) {        int n=nums.length;        int[] dp=new int[n];        Arrays.fill(dp,Integer.MAX_VALUE);        //状态表示：前跳到第i个的最小次数        dp[0]=0;        for(int i=1;i            for(int j=0;j                int l=i-j;                if(nums[j]=l)                {                    dp[i]=Math.min(dp[i],dp[j]+1);                }            }        }        return dp[n-1];    }}                if(j-i    public String longestPalindrome(String s) {        int n=s.length();        //状态表示:i到j是否是一个回文串        boolean[][] dp=new boolean[n][n];        //dp[i][j]=dp[i+1][j-1] && s.charAt(i)==s.charAt(j)        String str="";        for(int i=n-1;i=0;i--)        {            for(int j=i;j                if(s.charAt(i)==s.charAt(j))                {                    if(j-i                    str=s.substring(i,j+1);                }            }        }        return str;    }}    public int longestCommonSubsequence(String text1, String text2) {        int n=text1.length();        int m=text2.length();        int[][] dp=new int[n+1][m+1];        for(int i=1;i            for(int j=1;j                if(text1.charAt(i-1)==text2.charAt(j-1))                    dp[i][j]=dp[i-1][j-1]+1;                else                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);            }        }        return dp[n][m];    }}    public int minFallingPathSum(int[][] matrix) {        int n=matrix.length;        int m=matrix[0].length;        int[][] dp=new int[n][m];        for(int j=0;j            dp[0][j]=matrix[0][j];        }        for(int i=1;i            for(int j=0;j                if(j==0)                    dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j+1])+matrix[i][j];                else if(j==m-1)                    dp[i][j]=Math.min(dp[i-1][j-1],dp[i-1][j])+matrix[i][j];                else                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]))+matrix[i][j];            }        }        int min=Integer.MAX_VALUE;        for(int j=0;j            min=Math.min(min,dp[n-1][j]);        }        return min;    }}