hot100之多维动态规划

输入有误 發表於 2025-6-27 14:11:00

<blockquote>
<p>我是比较爱用自底向上的自底向上方法不会计算多余情况，也不用memo存储</p>
</blockquote>
<h3 id="不同路径062">不同路径（062）</h3>
<pre><code class="language-java">class Solution {
public int uniquePaths(int m, int n) {
   int[][] dp = new int;
   for (int i = 0; i < m;i++){
         dp = 1;
   }
   for (int j = 0; j < n; j++){
         dp = 1;
   }

   for (int i = 1; i < m; i++){
         for (int j = 1; j < n; j++){
            dp = dp + dp;
         }
   }

   return dp;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>对0行0列初始化，后进行合流</p>
<h3 id="最小路径和064">最小路径和（064）</h3>
<pre><code class="language-java">class Solution {
public int minPathSum(int[][] grid) {
   int m = grid.length;
   int n = grid.length;
   int[][] dp = new int;
   dp = grid;

   for (int i = 1; i < m; i++){
         dp = dp + grid;
   }
   for (int j = 1; j < n; j++){
         dp = dp + grid;
   }

   for (int i = 1; i < m; i++){
         for (int j = 1; j < n; j++){
            dp = Math.min(dp, dp) + grid;
         }
   }

   return dp;
}
}

</code></pre>
<ul>
<li>分析</li>
</ul>
<p>同样是初始化，再合流</p>
<p>根据dp数组的依赖关系，可以进行空间优化</p>
<h3 id="最长回文子串005">最长回文子串（005）</h3>
<pre><code class="language-java">class Solution {
public String longestPalindrome(String s) {
   String res = " ";
   for (int i = 0; i < s.length(); i++){
         String str1 = longestSubPalindrome(i, i, s);
         String str2 = longestSubPalindrome(i, i+1, s);
         res = res.length() > str1.length() ? res : str1;
         res = res.length() > str2.length() ? res : str2;
   }
   return res;
}

private String longestSubPalindrome(int lef, int rig, String s){
   while (0<=lef && rig < s.length() && s.charAt(lef) == s.charAt(rig)){
         lef--;
         rig++;
   }
   return s.substring(lef+1, rig);
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>想到扩散是比较自然的，时间复杂度也不高</p>
<h3 id="最长公共子序列1143">最长公共子序列（1143）</h3>
<pre><code class="language-java">class Solution {
public int longestCommonSubsequence(String text1, String text2) {
   char[] charArray1 = text1.toCharArray();
   char[] charArray2 = text2.toCharArray();

   int m = charArray1.length;
   int n = charArray2.length;

   int[][] dp = new int;
   for(int i = 1; i <= m; i++){
         for (int j = 1; j <= n; j++){
            if (charArray1 == charArray2){
               dp = dp + 1;
            }
            else dp = Math.max(dp, dp);

         }
   }
   return dp;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>可以看作有两个指针，匹配的话两个指针一起右移，不匹配移动其中一个指针找到新的匹配</p>
<h3 id="编辑距离072">编辑距离（072）</h3>
<pre><code class="language-java">class Solution {
public int minDistance(String word1, String word2) {
   char[] charArray1 = word1.toCharArray();
   char[] charArray2 = word2.toCharArray();
   int m = charArray1.length;
   int n = charArray2.length;
   int[][] dp = new int;

   for (int i = 0; i < m; i++){
         dp = i+1;
   }
   for (int j = 0; j < n; j++){
         dp = j+1;
   }

   for (int i = 1; i <= m; i++){
         for (int j = 1; j <= n ; j++){
            if (charArray1 == charArray2){
               dp = dp;
            }
            else dp = Math.min(dp ,Math.min(dp, dp)) + 1;
         }
   }
   return dp;
}
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>跟上题差不多，不匹配时多了一个情况变为<移动A指针><移动B指针><移动双指针></p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18952181

頁: [1]

琼殿技术论坛's Archiver

hot100之多维动态规划