动态规划 2016-7-16

[SnackMen]

72. Edit Distance 120. Triangle 87. Scramble String

[SnackMen]

/*
   [AC] 120 Triangle
*/
public class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        for(int i=triangle.size()-2;i>=0;i--){
            for(int j=0;j<i+1;j++){
                List<Integer> list=triangle.get(i);
                if(triangle.get(i+1).get(j)>triangle.get(i+1).get(j+1)){
                    list.set(j,triangle.get(i+1).get(j+1)+triangle.get(i).get(j));
                }
                else{
                    list.set(j,triangle.get(i+1).get(j)+triangle.get(i).get(j));
                }
                triangle.set(i,list);
            }
        }
        return triangle.get(0).get(0);
    }
}

[dayang]

/**
 * [AC] LeetCode 72
 * @param {string} word1
 * @param {string} word2
 * @return {number}
 */
var minDistance = function(word1, word2) {
    if(word1.length === 0)
        return word2.length;
    if(word2.length === 0)
        return word1.length;
    var len1 = word1.length,len2 = word2.length,cost;
    var dp = [];
    for(var i = 0; i <= len1; i++){
        dp.push([i]);
        for(var j = 1; j <= len2; j++){
            dp[i].push(j);
        }
    }

    for(i = 0; i < len1; i++){
        for(j = 0; j < len2; j++){
            cost = word1[i] === word2[j] ? 0 : 1;
            dp[i+1][j+1] = Math.min(Math.min(dp[i][j+1] + 1,dp[i+1][j] + 1),dp[i][j] + cost);
        }
    }

    return dp[len1][len2];
};

[dayang]

/**
 * [AC] LeetCode 120
 * @param {number[][]} triangle
 * @return {number}
 */
var minimumTotal = function(triangle) {
    var nums = [0,triangle[0][0]];
    var n;
    for(var i = 1; i < triangle.length; i++){
        for(var j = 0; j <= i; j++){
            n = i * (i + 1) / 2 + j + 1;
            if(j === 0){
                nums.push(nums[n - i] + triangle[i][j]);
            }else if(i === j){
                nums.push(nums[n - i - 1] + triangle[i][j]);
            }else{
                nums.push(Math.min(nums[n - i],nums[n - i - 1]) + triangle[i][j]);
            }
        }
    }
    var min = nums[nums.length - 1];
    for(i = nums.length - 2; i >= nums.length - triangle.length; i--){
        min = Math.min(min, nums[i]);
    }
    return min;
};

[zhaokuohaha]

LeetCode-72-编辑距离-C#-不容易啊

public class Solution
{
    public int MinDistance(string word1, string word2)
    {
        int l1 = word1.Length;
        int l2 = word2.Length;
        int[,] dp = new int[l1+1, l2+1];
        for(int i=0; i<=l1; i++)
        {
            dp[i, 0] = i;
        }
        for (int j = 0; j <= l2; j++)
        {
            dp[0, j] = j;
        }

        for(int i=1; i<=l1; i++)
        {
            for(int j=1; j<=l2; j++)
            {
                int min = word2[j-1] == word1[i-1] ? 0 : 1;
                dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), min+dp[i-1,j-1]);
            }
        }
        return dp[l1,l2];
    }
}

[zhaokuohaha]

LeetCode-120-C

public class Solution
{
    public int MinimumTotal(IList<IList<int>> triangle)
    {
        if (triangle.Count == 0) return 0;
        int[][] dp = new int[triangle.Count][];
        for(int i=0; i<triangle.Count; i++)
        {
            dp[i] = new int[triangle[i].Count];
            for (int j = 0; j < triangle[i].Count; j ++)
            {
                if (i > 0)
                {
                    if (j == 0)
                        dp[i][j] = dp[i - 1][j] + triangle[i][j];
                    else if (j == triangle[i].Count - 1)
                        dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                    else
                        dp[i][j] = Math.Min(dp[i - 1][j -1 ], dp[i - 1][j]) + triangle[i][j];
                }
                else { dp[i][j] = triangle[i][j]; }
            }
        }
        return dp[triangle.Count - 1].Min();
    }
}