[プログラマー]窃盗(JAVA)
759 ワード
問題の説明
泥棒はある村を強奪しようとしている.この村のすべての家は下図のように丸く配置されている.
各家には隣接する家と防犯装置が接続されているため、隣接する家を2軒強奪すると警報が鳴る.
どの家にもお金が入った並びのお金がある場合は、泥棒が盗むことができるお金の最高価格を返すために解関数を書いてください.
せいげんじょうけん
この村の家は3軒以上10万軒以下です.
money配列の各要素は1000以下の整数です.
Code
見逃した場所
1.最後のindexだけが一番だと思います.
2.最初と最後は隣の家です.
泥棒はある村を強奪しようとしている.この村のすべての家は下図のように丸く配置されている.
各家には隣接する家と防犯装置が接続されているため、隣接する家を2軒強奪すると警報が鳴る.
どの家にもお金が入った並びのお金がある場合は、泥棒が盗むことができるお金の最高価格を返すために解関数を書いてください.
せいげんじょうけん
この村の家は3軒以上10万軒以下です.
money配列の各要素は1000以下の整数です.
Code
class Solution {
public int solution(int[] money) {
int len = money.length;
int[][] dp = new int[2][len];
dp[0][0] = money[0];
dp[0][1] = money[0];
dp[1][0] = 0;
dp[1][1] = money[1];
for(int i=2; i<len ; i++) {
dp[0][i] = Math.max(dp[0][i-2]+money[i], dp[0][i-1]);
dp[1][i] = Math.max(dp[1][i-2]+money[i], dp[1][i-1]);
}
return Math.max(dp[0][len-2], dp[1][len-1]);
}
}
Comment見逃した場所
1.最後のindexだけが一番だと思います.
2.最初と最後は隣の家です.
Reference
この問題について([プログラマー]窃盗(JAVA)), 我々は、より多くの情報をここで見つけました https://velog.io/@ujone/프로그래머스-도둑질-JAVAテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol