动态规划（DP）_c++定义数组 int [] dp=new int意思

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。

示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
3.  1 阶 + 1 阶 + 1 阶
4.  1 阶 + 2 阶
5.  2 阶 + 1 阶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int climbStairs(int n) {
        if(n<=2) return n;
        else {
            int res = 0;
            int i = 1,j = 2;
            int k = 3;
            while(k<=n){
                res = i + j;
                i = j;
                j = res;
                k++;
            }
            return res;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n+1];
        if(n<=2) return n;
        else {
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 2;
            for(int i=3;i<=n;i++) {
                dp[i] = dp[i-1] + dp[i-2];
            }
        return dp[n];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

斐波那契数列：
设跳n个台阶有f(n)种方法，
爬1个：1种
爬2个：2种
爬n个：面临两种选择：
（1） 第一次爬1个，此时剩余n-1个台阶，有f(n-1)种方法
（2） 第一次爬2个，此时剩余n-2个台阶，有f(n-2)种方法
所以f(n) = f(n-1) + f(n-2)
1
2
3
4
5
6
7
8

121. 买卖股票的最佳时机

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。

示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
1
2
3
4
5
6
7
8

class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length <= 1){
            return 0;
        }
        int min = prices[0],max = 0;
        for(int i = 1;i < prices.length;i++){
            max = Math.max(max,prices[i] - min);
            min = Math.min(min,prices[i]);
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

322. 零钱兑换

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

示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3 
解释: 11 = 5 + 5 + 1

说明:你可以认为每种硬币的数量是无限的。
1
2
3
4
5
6
7
8
9

比较典型的动态规划问题:
假设 f(n) 代表要凑齐金额为 n 所要用的最少硬币数量，那么有：
f(n) = min(f(n - c1), f(n - c2), ... f(n - cn)) + 1
其中 c1 ~ cn 为硬币的所有面额。
1
2
3
4

在这里插入代码片
1

53. 最大子序和

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

示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
1
2
3
4
5
6

class Solution {
    public int maxSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for(int num:nums){
            if(sum>0){
                sum += num;
            } else {
                sum = num;
            }
            res = Math.max(res,sum);
        }
        return res;
    }
}

//假设sum<=0，那么后面的子序列肯定不包含目前的子序列，所以令sum = num；
//如果sum > 0对于后面的子序列是有好处的。res = Math.max(res, sum)保证可以找到最大的子序和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
    public int maxSubArray(int[] nums) {
        int Maxsum=nums[0],sum=0;
        for (int i = 0; i < nums.length; i++) {
           sum+=nums[i];
           if(sum>Maxsum) Maxsum=sum;
           if(sum<0) sum=0;
        }
       return Maxsum;
    }
}
1
2
3
4
5
6
7
8
9
10
11

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。
1
2
3
4
5
6
7
8
9

class Solution {
    public int rob(int[] nums) {
       int n = nums.length;
       if(n <= 1) return n == 0 ? 0 : nums[0];
       int[] dp = new int[n];
       dp[0] = nums[0];
       dp[1] = Math.max(nums[0],nums[1]);
       for(int i = 2;i < n;i++){
           dp[i] = Math.max(dp[i-1],nums[i]+dp[i-2]);
       } 
       return dp[n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
    public int rob(int[] nums) {
       int res1 = 0,res2=0;
       for(int i = 0;i<nums.length;i++){
           if(i%2==0){
               res1 += nums[i];
               res1 = Math.max(res2,res1);
           }else{
               res2 += nums[i];
               res2 = Math.max(res2,res1);
           }
       } 
       return Math.max(res1,res2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

303. 区域和检索 - 数组不可变

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，
包含 i,  j 两点。

示例：
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
1
2
3
4
5
6
7
8

class NumArray {
    private int[] sums;

    public NumArray(int[] nums) {
        sums = new int[nums.length];
        if(nums.length == 0){
            return;
        }
        sums[0] = nums[0];
        for(int i = 1;i < nums.length; i++){
            sums[i] += sums[i-1] + nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        if (i == 0) {
            return sums[j];
        } else {
            return sums[j] - sums[i - 1];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

你知道的越多，你不知道的越多。
有道无术，术尚可求，有术无道，止于术。
如有其它问题，欢迎大家留言，我们一起讨论，一起学习，一起进步