Problem: 198. 打家劫舍

題目描述

思路

1.構(gòu)建多階段決策模型：n個(gè)房屋對(duì)應(yīng)n個(gè)階段，每一個(gè)階段決定一個(gè)房間是偷還是不偷，兩種決策：偷、不偷
2.定義狀態(tài)：不能記錄每個(gè)階段決策完之后，小偷可偷的最大金額，需要記錄不同決策對(duì)應(yīng)的最大金額，也就是：這個(gè)房屋偷-對(duì)應(yīng)的最大金額；這個(gè)房屋不偷-對(duì)應(yīng)的最大金額。int[n][2]記錄每個(gè)階段的狀態(tài)，dp[i][0]表示第i個(gè)物品不偷，當(dāng)下剩余的最大金額；dp[i][1]表示第i個(gè)物品偷，當(dāng)下剩余的最大金額；
3.定義狀態(tài)轉(zhuǎn)移方程：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1])即表示假設(shè)不偷則當(dāng)前階段可以獲得的最大值為上一個(gè)房屋偷或者不偷的二者中的最大金額；dp[i][1] = dp[i - 1][0] + nums[i]即表示假設(shè)當(dāng)前階段偷則當(dāng)前可以獲得的最大金額為上一個(gè)房屋不偷加上當(dāng)前當(dāng)前房屋的金額

解題方法

1.獲取nums數(shù)組的長(zhǎng)度為n；并定義int類型數(shù)組dp：int[][] dp = new int[n][2];
2.初始化dp[0][0]為0，dp[0][1]為nums[0];
3.完成動(dòng)態(tài)轉(zhuǎn)移方程；
4.返回max(dp[n - 1][0], dp[n - 1][1])

復(fù)雜度

時(shí)間復(fù)雜度:

$O(n)$;其中$n$為數(shù)組nums的長(zhǎng)度

空間復(fù)雜度:

$O(n)$文章來源地址http://www.zghlxwxcb.cn/news/detail-809875.html

Code

class Solution {
    /**
     * Get the maximum amount
     *
     * @param nums Given array(Store the amount of each house)
     * @return int
     */
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[][] dp = new int[n][2];
        //dp[i][0] represents the maximum amount
        // that can currently be obtained without stealing
        dp[0][0] = 0;
        //dp[i][1] represents the maximum amount
        // that can be obtained when not stealing
        dp[0][1] = nums[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][0] + nums[i];
        }
        return Math.max(dp[n - 1][0], dp[n - 1][1]);
    }
}

到了這里，關(guān)于力扣198. 打家劫舍（java 動(dòng)態(tài)規(guī)劃）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！