leetcode经典动态规划解题报告

leetcode70 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解答：
递推公式：

设f(n)为n阶楼梯的爬法
f(n)=f(n-1)+f(n-2) n>2
f(n)=1 n=1
f(n)=2 n=2
到达第n阶楼梯，有两种方法，一种是从第n-1阶楼梯，走一步到；另一种是从n-2阶楼梯，走两步到。

根据以上的递归公式，我们很容易写出下面的代码：

public int climbStairs(int n) {
       if (n<3){
           return n;
       }
       int[] dp=new int[n+1];
       dp[1]=1;
       dp[2]=2;
       for(int i=3;i<=n;i++){
           dp[i]=dp[i-1]+dp[i-2];
       }
       return dp[n];
   }

通过观察，不难发现我们只需要保存两个状态即可.

public int climbStairs(int n) {
       if (n<3){
           return n;
       }
       int p1=2; //f(n-1)
       int p2=1; //f(n-2)
       for(int i=3;i<=n;i++){
          int cur=p1+p2;
          p2=p1;
          p1=cur;
       }
       return p1;
   }

leetcode198 打家劫舍

题目描述：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

解答：
设小偷走到第n个房屋旁，他的最大收入为f(n),
那么有递推公式：
f(n)=max(f(n-2)+s[n],f(n-1)) 其中s[n]第n个房子可以窃到金额。

这个公式的含义是，当小偷走到第n个房子时，他其实有两种选择，偷或上家偷了不偷这家。小偷只需要选一个最优方案即可。

根据递推公式我们很容易得到以下的代码：

public int rob(int[] nums) {
        int n=nums.length;
        if (n==0){
            return 0;
        }else if (n==1){
            return nums[0];
        }else if (n==2){
            return Math.max(nums[0],nums[1]);
        }
        int[] dp=new int[n+1];

dp[1]=nums[0];
        dp[2]=Math.max(nums[0],nums[1]);

for (int i=3;i<=n;i++){
            dp[i]= Math.max(dp[i-1],dp[i-2]+nums[i-1]);
        }

return dp[n];
    }

实际上我们只需要保存两个状态即可，也无需这么多的特判代码。简化后的代码如下：

public int rob(int[] nums) {
       int p1=0; //f(n-1)
       int p2=0; //f(n-2)

for (int i=0;i<nums.length;i++){
           int cur=Math.max(p2+nums[i],p1);
           p2=p1;
           p1=cur;
       }

return p1;
   }

这道题还有一些延申题目：

leetcode213 打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

解答：
这道题目和上面题目的不同在于房子是环形排布的。也就是说，如果第一个房子被偷了，那么最后一个房子就不能被偷。也就是说第一个房子偷不偷可以影响最后一个房子的情况，我们只需要把两种情况都计算一下即可。

public int rob(int[] nums) {
    if (nums==null||nums.length==0){
        return 0;
    }
    if (nums.length==1){
        return nums[0];
    }
    return Math.max(helper(nums,0,nums.length-2),helper(nums,1,nums.length-1));
}

public int helper(int[] nums,int start,int end){
    int p1=0;// f(n-1)
    int p2=0;// f(n-2)
    for (int i=start;i<=end;i++){
        int cur=Math.max(p2+nums[i],p1);
        p2=p1;
        p1=cur;
    }
    return p1;
}

leetcode53最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

解答：
设以下标n结尾的子序和为f(n)

因此我们可以得到递推公式：
f(n)=max(f(n-1),0)+nums[n]

public int maxSubArray(int[] nums) {
        if (nums==null||nums.length==0){
            return 0;
        }

int max=0;
        for (int i=1;i<nums.length;i++){
            nums[i]=Math.max(nums[i-1],0)+nums[i];
            max=Math.max(max,nums[i]);
        }
        return max;
    }

从递推公式中可以知道我们需要保存前一个状态，我们可以直接利用原数组即可。

leetcode322 零钱找零

题目描述：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

解答：
设总金额n找零所需的最少硬币数为f(n)
那么我们可以得到递推公式
f(n)=min(f(n-c))+1 c 为硬币面值

public int coinChange(int[] coins, int amount) {
       int[] dp=new int[amount+1];
       int max=amount+1;
       Arrays.fill(dp,max);
       dp[0]=0;
       for (int i=1;i<dp.length;i++){
           for (int coin : coins) {
               if (i >= coin) {
                   dp[i]=Math.min(dp[i],dp[i-coin]+1);
               }
           }
       }
       return dp[amount]>amount?-1:dp[amount];
   }

leetcode120 三角形最小路径和

题目描述：

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

假如到达第i层的第j个位置，那么只能从第i-1层的j-1/j位置到达。
我们设到达第i层第j个节点的最小路径和为dp[i][j]
那么我们可以得到以下递推公式：
dp[i][j]=min(dp[i-1][j-1],dp[i-1][j])+d[i][j]

值得注意的是两边要特殊处理。

public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[n][n];
        //左边特殊处理
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            //右边特殊处理
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[n - 1][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }

leetcode300 最长上升子序列

题目描述：

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例:
输入: [10,9,2,5,3,7,101,18]
输出: 4 
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

public int lengthOfLIS(int[] nums) {
       if (nums.length==0){
           return 0;
       }
       int res=0;
       int[] dp=new int[nums.length];
       Arrays.fill(dp,1);
       for (int end=0;end<nums.length;end++){
           for (int start=0;start<end;start++){
               if (nums[start]<nums[end]){
                   dp[end]=Math.max(dp[end],dp[start]+1);
               }
           }
           res=Math.max(res,dp[end]);
       }
       return res;
   }

leetcode64 最小路径和

题目描述：

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

解答：
我们假设到达坐标(i,j)的最小路径和为f(i,j)
因为到达(i,j)要么从上面过来，要么从左边过来。
因此我们可以得到这样的递推公式：
f(i,j)=min(f(i-1,j),f(i,j-1))+grid[i][j]
注意第一行和第一列要特殊处理。

public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m][n];
        dp[0][0]=grid[0][0];
        //第一行
        for (int col=1;col<n;col++){
            dp[0][col]=dp[0][col-1]+grid[0][col];
        }
        //第一列
        for (int row=1;row<m;row++){
            dp[row][0]=dp[row-1][0]+grid[row][0];
        }
        for (int row=1;row<m;row++){
            for (int col=1;col<n;col++){
                dp[row][col]=Math.min(dp[row-1][col],dp[row][col-1])+grid[row][col];
            }
        }
        return dp[m-1][n-1];


    }

leetcode174 地下城游戏

题目描述：

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。
编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

解答：
这道题我们不能从左上角向右下角进行动态规划；我们需要从右下角到左上角进行动态规划。
设从(i,j)到终点所需的最小初始值为dp[i][j]
也就是说当我们到达坐标(i,j)时，只要路径和不小于dp[i][j]就能到达终点。
我们可以得到状态转移方程：
dp[i][j]=max(min(dp[i+1][j],dp[i][j+1])-dungeon(i,j),1)

public int calculateMinimumHP(int[][] dungeon) {
     int n = dungeon.length, m = dungeon[0].length;
     int[][] dp = new int[n + 1][m + 1];
     for (int i = 0; i <= n; ++i) {
         Arrays.fill(dp[i], Integer.MAX_VALUE);
     }
     dp[n][m - 1] = dp[n - 1][m] = 1;
     for (int i = n - 1; i >= 0; --i) {
         for (int j = m - 1; j >= 0; --j) {
             int minn = Math.min(dp[i + 1][j], dp[i][j + 1]);
             dp[i][j] = Math.max(minn - dungeon[i][j], 1);
         }
     }
     return dp[0][0];
 }