动态规划-刷题记录

动态规划刷题思路

1.确认dp数组代表的含义

2.确认dp数组的算法公式

3.确认dp数组的初始值

4.确认循环开始和方向

5.验证dp数组含义

leetcode题目

一、爬楼梯-斐波那契数列

leetcode70 爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

1.dp数组代表，当前i有几种方法可以达到

2.dp[i]可以通过dp[i-1]往上爬一步，或者dp[i-2]往上爬2步达到

dp[i]=dp[i-1]+dp[i-2]

3.初始值：i从1开始 到n dp[1]=1,dp[2]=2

4.确认从1开始到n

代码：

  1. class Solution {
  2.     public int climbStairs(int n) {
  3.         if(n<3){
  4.             return n;
  5.         }
  6.         //定义1个数组，数组类型为整数
  7.         int[] dp=new int[n+1];
  8.         dp[1]=1;
  9.         dp[2]=2;
  10.         for(int i=3;i1;i++){
  11.             dp[i]=dp[i-1]+dp[i-2];
  12.         }
  13.         return dp[n];
  14.         
  15.     }
  16. }

关注点：数组长度从索引0开始，但是取值从索引1开始，所以在定义数组长度时，为n+1

使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

索引：从0到n-1，需要达到的台阶索引为n

1.数组代表什么，代表达到当前索引需要的最小代价

2.数组算法：dp[i]等于dp[i-1]向上爬一步花费的cost[i-1]、dp[i-2]向上爬二步花费的cost[i-2]的最小值 ；dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])

3.初始值：可以从0或1开始，所以dp[0]=0,dp[1]=0

4.遍历 从0开始 到n结束

  1. class Solution {
  2.     public int minCostClimbingStairs(int[] cost) {
  3.         int n=cost.length;
  4.         int[] dp=new int[n+1];
  5.         dp[0]=0;
  6.         dp[1]=0;
  7.         if(n<2){
  8.             return 0;
  9.         }
  10.         for(int i=2;i1;i++){
  11.             dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
  12.         }
  13.         return dp[n];
  14.         
  15.     }
  16. }

二、不同路径-矩阵

不同路径

62. 不同路径 - 力扣（LeetCode）

1.确认数组代表的含义：dp[i][j]=到达i*j矩阵的右下角有几种方式

2.算法公式 dp[i][j]= dp[i-1][j]+ dp[i][j-1]

3.初始值：dp[1][1]=1，dp[1][2]=1，dp[2][1]=1

初始化取值错误：dp[i][1]=1,dp[1][j]=1

4.遍历方法：从左到右

  1. class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         int[][]dp=new int[m+1][n+1];
  4.         for(int i=1;i1;i++){
  5.             dp[i][1]=1;
  6.         }
  7.         for(int j=1;j1;j++){
  8.             dp[1][j]=1;
  9.         }
  10.         for(int i=2;i1;i++){
  11.             for(int j=2;j1;j++){
  12.                 dp[i][j]= dp[i-1][j]+ dp[i][j-1];
  13.                 System.out.println(i+" "+j+" "+dp[i][j]);
  14.             }
  15.         }
  16.         return dp[m][n];
  17.         
  18.     }
  19. }

不同路径II-有障碍物版本

63. 不同路径 II - 力扣（LeetCode）

具体思路，有障碍物的地方dp[i][j]数组等于0-因为无法到达这个路径

1.确定数组的含义：dp[i][j]到达i,j这个位置有多少条道路

2.dp[i][j]=dp[i-1][j]+ dp[i][j-1]

3.初始化取值：

3.1 dp[i][0]=1,dp[0][j]=1

3.2 dp[x][y]=0--原数组中等于1的位置

三、动态规划在字符串中的应用

最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

1.确认字符串的含义dp[i][j]代表s[i:j]是否为回文串

2.逻辑式：dp[i+1][j-1]=true&&dp[i]==dp[j]

3.初始值：i=j时，肯定是,j=i+1,相等的时候是

4.遍历方法：从左到右 j从i开始

  1. class Solution {
  2.     public String longestPalindrome(String s) {
  3.     int n = s.length();
  4.     if (n < 2) {
  5.         return s;
  6.     }
  7.     int max_len = 1;
  8.     int begin = 0, end = 0;
  9.     boolean[][] dp = new boolean[n][n];
  10.  
  11.     // 每个字符自身肯定是一个回文
  12.     for (int i = 0; i < n; i++) {
  13.         dp[i][i] = true;
  14.     }
  15.  
  16.     // 检查所有长度为2的子串
  17.     for (int i = 0; i < n - 1; i++) {
  18.         if (s.charAt(i) == s.charAt(i + 1)) {
  19.             dp[i][i + 1] = true;
  20.             max_len = 2;
  21.             begin = i;
  22.             end=i+1;
  23.         }
  24.     }
  25.  
  26.     // 检查长度大于2的子串
  27.     for (int len = 3; len <= n; len++) {
  28.         for (int i = 0; i <= n - len; i++) {
  29.             int j = i + len - 1;
  30.             if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
  31.                 dp[i][j] = true;
  32.                 if (len > max_len) {
  33.                     max_len = len;
  34.                     begin = i;
  35.                     end = j;
  36.                 }
  37.             }
  38.         }
  39.     }
  40.  
  41.     // 构建最长回文子串
  42.     return s.substring(begin, end + 1);
  43. }
  44. }

最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

注：本文转载自blog.csdn.net的q1046634291的文章"https://blog.csdn.net/q1046634291/article/details/144675626"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！