一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 388|回复: 2
收起左侧

[动态规划] dp problem

[复制链接] |试试Instant~ |关注本帖
love1point 发表于 2015-8-9 11:01:41 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Why in some dp problem, when we define the dp array, sometimes we define the length of array is (length + 1), but sometimes is (length).

Example such as Unique Paths (int[][] dp = new int[m][n];) and Edit distance(int[][] dp = new int[word1.length() + 1][word2.length() + 1];)

Any discussion is appreciated.
  1. public class Solution {
  2.     public int uniquePaths(int m, int n) {
  3.         if(m == 0 || n == 0)
  4.         {
  5.             return 0;
  6.         }
  7.         
  8.         if(m == 1 || n == 1)
  9.         {
  10.             return 1;
  11.         }
  12.         
  13.         int[][] dp = new int[m][n];
  14.         
  15.         for(int i = 0; i < m; i++)
  16.         {
  17.             dp[i][0] = 1;
  18.         }
  19.         
  20.         for(int j = 0; j < n; j++)
  21.         {
  22.             dp[0][j] = 1;
  23.         }
  24.         
  25.         for(int i = 1; i < m; i++)
  26.         {
  27.             for(int j = 1; j < n; j++)
  28.             {
  29.                 dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  30.             }
  31.         }
  32.         return dp[m - 1][n - 1];
  33.     }
  34. }
复制代码
  1. public class Solution {
  2.     public int minDistance(String word1, String word2) {
  3.         int len1 = word1.length();
  4.         int len2 = word2.length();
  5.         
  6.         int[][] dp = new int[word1.length() + 1][word2.length() + 1];
  7.         
  8.         for(int i = 0; i <= word1.length(); i++)
  9.         {
  10.             dp[i][0] = i;
  11.         }
  12.         
  13.         for(int j = 0; j <= word2.length(); j++)
  14.         {
  15.             dp[0][j] = j;
  16.         }
  17.         
  18.         for(int i = 0; i < word1.length(); i++)
  19.         {
  20.             for(int j = 0; j < word2.length(); j++)
  21.             {
  22.                 char c1 = word1.charAt(i);
  23.                 char c2 = word2.charAt(j);
  24.                 if(c1 == c2)
  25.                 {
  26.                     dp[i + 1][j + 1] = dp[i][j];
  27.                 }
  28.                 else
  29.                 {
  30.                     dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1] + 1, dp[i + 1][j] + 1), dp[i][j] + 1);
  31.                 }
  32.             }
  33.         }
  34.         return dp[len1][len2];
  35.     }
  36. }
复制代码
muybienw 发表于 2015-8-9 20:36:04 | 显示全部楼层
个人理解,这个要看dp的东西是什么含义,unique paths里面dp[i][j]就是坐标 i, j这个位置的情况,length * length就已经覆盖所有情况了;而edit distance里面,i,j可以理解为两个字符串分别到 i, j 位置的匹配情况,额外加一行一列,正好处理了两个string是 "",即空字符串的情况。一般string的dp处理,都是用length + 1的。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 00:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表