一的烁、爬樓梯

假設(shè)你正在爬樓梯绎橘。需要 n 階你才能到達(dá)樓頂诉位。
每次你可以爬 1 或 2 個(gè)臺(tái)階骑脱。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個(gè)正整數(shù)苍糠。

示例 1：

輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂叁丧。

1. 1 階 + 1 階
2. 2 階

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。

1. 1 階 + 1 階 + 1 階
2. 1 階 + 2 階
3. 2 階 + 1 階

解題思路

本題是動(dòng)態(tài)規(guī)劃里面最簡單的題目了岳瞭，印象中第一次見到這個(gè)題目還是在藍(lán)橋杯的練習(xí)題中拥娄。
雖然本篇是動(dòng)態(tài)規(guī)劃的入門文章，但是我并不會(huì)說任何書面上寫的動(dòng)態(tài)規(guī)劃算法的定義寝优。這是因?yàn)閯?dòng)態(tài)規(guī)劃的概念還是很復(fù)雜的条舔，看完動(dòng)態(tài)規(guī)劃算法的思路和特性估計(jì)你就被動(dòng)態(tài)規(guī)劃嚇到了。
關(guān)于動(dòng)態(tài)規(guī)劃的定義乏矾，我只說一句個(gè)人看法——?jiǎng)討B(tài)規(guī)劃求的是全局最優(yōu)解孟抗。全局意味著動(dòng)態(tài)規(guī)劃是要全盤考慮問題的。話不多說钻心，我們先從題目解答中開始體會(huì)凄硼。

本題中，我們看到捷沸，爬1階梯只有1種方法摊沉，爬2階梯有2種方法。那我們就能想到痒给，爬3階梯有3種说墨，這是因?yàn)榕?階等于爬2階的基礎(chǔ)上再爬1階。同理爬4階等于在3階的基礎(chǔ)上爬1階和2階的基礎(chǔ)上爬2階苍柏；

這種“站在巨人的肩膀上”的思路就是動(dòng)態(tài)規(guī)劃的思想尼斧。

實(shí)現(xiàn)代碼

首先我們能想到的是使用遞歸的方法。遞歸方法跟我們上面的思路正好反過來试吁。遞歸的思路是爬n階樓梯的方式等于爬n-1階樓梯的次數(shù)加上n-2階樓梯的次數(shù)棺棵。但是遞歸方法不會(huì)保存計(jì)算結(jié)果，導(dǎo)致有很多重復(fù)的計(jì)算，因此超時(shí)也就不可避免了烛恤。

1. 遞歸

class Solution {
    public int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        return climbStairs(n-1)+climbStairs(n-2);
    }
}

運(yùn)行結(jié)果：超時(shí)

2. 動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃的整體思路跟遞歸很像母怜，但是會(huì)通過一個(gè)dp數(shù)組保存計(jì)算結(jié)果。這樣計(jì)算速度就會(huì)快很多缚柏。

class Solution {
    public int climbStairs(int n) {
        int[] steps=new int[n];
        if(n==1){
            return 1;
        }
        steps[0]=1;
        steps[1]=2;
        for(int i=2;i<n;i++){
            steps[i]=steps[i-1]+steps[i-2];
        }
        return steps[n-1];
    }
}

二苹熏、連續(xù)子數(shù)組的最大和

給定一個(gè)整數(shù)數(shù)組 nums ，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素）币喧，返回其最大和柜裸。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]
輸出：6
解釋：連續(xù)子數(shù)組 [4,-1,2,1] 的和最大，為 6 粱锐。

示例 2：

輸入：nums = [1]
輸出：1
示例 3：

輸入：nums = [0]
輸出：0

示例 4：

輸入：nums = [-1]
輸出：-1

示例 5：

輸入：nums = [-100000]
輸出：-100000

提示：

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

進(jìn)階： 如果你已經(jīng)實(shí)現(xiàn)復(fù)雜度為 O(n) 的解法疙挺，嘗試使用更為精妙的 分治法 求解。

解題思路

動(dòng)態(tài)規(guī)劃是本題的最優(yōu)解怜浅。動(dòng)態(tài)規(guī)劃的思路也很清晰铐然。假設(shè)有一個(gè)數(shù)組[-2,1]，那么我們可以看到[-2,1]兩數(shù)的和比數(shù)組第二個(gè)元素1要小恶座。因此連續(xù)子數(shù)組的最大和為1搀暑。當(dāng)數(shù)組變?yōu)?code>[-2,1,-3]的時(shí)候，我們已經(jīng)知道[-2,1]這部分?jǐn)?shù)組的連續(xù)子數(shù)組的最大和為1跨琳。那么1跟[-3]比較是1比較大自点，因此這個(gè)數(shù)組的連續(xù)子數(shù)組的最大和依然為1。

簡而言之脉让，每次數(shù)組新增一個(gè)元素桂敛，都需要跟增加前的數(shù)組的連續(xù)子數(shù)組的最大和相比較，結(jié)果較大的那個(gè)就是新增后數(shù)組的連續(xù)子數(shù)組的最大和溅潜。代碼實(shí)現(xiàn)如下：

實(shí)現(xiàn)代碼

class Solution {
    public int maxSubArray(int[] nums) {
        int dp[]=new int[nums.length];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;i<dp.length;i++){
            //compare the num last status plus current num and current num 
            dp[i]=Math.max(dp[i-1]+nums[i],nums[i]);
            //compare max and dp[i],it will update max
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}

三术唬、游戲幣組合

硬幣。給定數(shù)量不限的硬幣滚澜，幣值為25分粗仓、10分、5分和1分设捐，編寫代碼計(jì)算n分有幾種表示法借浊。(結(jié)果可能會(huì)很大，你需要將結(jié)果模上1000000007)

示例1:

輸入: n = 5
輸出：2
解釋: 有兩種方式可以湊成總金額:
5=5
5=1+1+1+1+1

示例2:

輸入: n = 10
輸出：4
解釋: 有四種方式可以湊成總金額:
10=10
10=5+5
10=5+1+1+1+1+1
10=1+1+1+1+1+1+1+1+1+1

說明：

注意:

你可以假設(shè)：

0 <= n (總金額) <= 1000000

解題思路

這道題的狀態(tài)轉(zhuǎn)移方程似乎不那么容易看出來萝招，不過我們可以列一個(gè)表格來觀察一下蚂斤，看能不能發(fā)現(xiàn)一點(diǎn)什么規(guī)律。

首先我們定義一個(gè)dp數(shù)組和所有的硬幣數(shù)組

 int[] dp = new int[n + 1];
 int[] coins = {1,5,10,25};

并且設(shè)置dp[0]=1,為邊界的條件即寒，作為完美能被一個(gè)硬幣表示的情況為 1橡淆。
dp[i]+=dp[i-coin]當(dāng)i-coin為0時(shí)結(jié)果為1，表示一個(gè)硬幣能表示的情況母赵。

我們可以簡單的得出狀態(tài)轉(zhuǎn)移方程

// 題目中需求對結(jié)果取模1000000007
dp[i] = dp[i] + dp[i - coin] 

代碼實(shí)現(xiàn)

class Solution {
    public int waysToChange(int n) {
       int dp[]=new int[n+1];
       int coins[]={1,5,10,25};
       dp[0]=1;

        for(int coin : coins) {
            for(int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }
        return dp[n];
    }
}