//解法一：
public int Fibonacci(int n) {
if (n <= 1)
return n;
int[] fib = new int[n + 1];
fib[1] = 1;
for (int i = 2; i <= n; i++)
fib[i] = fib[i - 1] + fib[i - 2];
return fib[n];
}//解法二：是对解法一的优化
public int Fibonacci(int n) {
if (n <= 1)
return n;
int pre1 = 0, pre2 = 1;
int fib = 0;
for (int i = 2; i <= n; i++) {
fib = pre1 + pre2;
pre1 = pre2;
pre2 = fib;
}
return fib;
}public int JumpFloor(int target) {
if(target<=2){
return target;
}
int pre1 = 1;
int pre2 = 2;
for(int i=3;i<=target;i++){
int next = pre1 + pre2;
pre1 = pre2;
pre2 = next;
}
return pre2;
}//思路一：
// 公式法
// 跳上 n 级台阶，可以从 n-1 级跳 1 级上去，也可以从 n-2 级跳 2 级上去... ，那么
// f(n) = f(n-1) + f(n-2) + ... + f(0) (I)
// 跳上 n-1 级台阶，可以从 n-2 级跳 1 级上去，也可以从 n-3 级跳 2 级上去...，那么
// f(n-1) = f(n-2) + f(n-3) + ... + f(0) (II)
// (I) - (II) 式，可得
// f(n) - f(n-1) = f(n-1)
// 即
//f(n) = 2*f(n-1)
public int JumpFloorII(int target) {
return (int) Math.pow(2, target - 1);
}//思路二：
//动态规划：dp[i] 表示跳上 i 级别的台阶总共的跳法
//思路一种 f(n) = 2*f(n-1)
//这里就是 dp[i] = 2*dp[i-1]
public int JumpFloorII(int target) {
if(target<=1){
return target;
}
//dp[i] 表示跳上 i 级别的台阶总共的跳法
int[] dp = new int[target+1];
Arrays.fill(dp,1);
for(int i=2;i<=target;i++){
dp[i] = 2*dp[i-1];
}
return dp[target];
}public int RectCover(int target) {
if (target==1){
return 1;
}
if(target==2){
return 2;
}
int pre1 = 1;
int pre2 = 2;
int res = 0;
for(int i=3;i<=target;i++){
res = pre1 + pre2;
pre1 = pre2;
pre2 = res;
}
return res;
}//思路：
//动态规划思路
//dp[i] 表示以 array[i] 结尾的元素连续子数组的最大连续和
//dp[i-1]>0 时，dp[i] = dp[i-1] + array[i]
//否则，dp[i] = array[i]//写法一：
//时间复杂度：O(n)
//空间复杂度：O(n)
//连续子数组的最大和
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==1){
return array[0];
}
int n = array.length;
//dp[i] 表示以array[i]结尾的元素连续子数组的最大连续和
int[] dp = new int[n];
dp[0] = array[0];
int res= Integer.MIN_VALUE;
for(int i=1;i<n;i++){
if(dp[i-1]>0){
dp[i] =dp[i-1]+array[i]; //array[i] 加上任意一个 > 0 的数都会大于原来的数
}else{
dp[i] = array[i];
}
res = Math.max(res,dp[i]);
}
return res;
}//写法二:
//时间复杂度：O(n)
//空间复杂度：O(1)
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==1){
return array[0];
}
int n = array.length;
int pre1 = array[0];
int res= Integer.MIN_VALUE;
for(int i=1;i<n;i++){
int pre2 = (pre1>0)?(pre1+array[i]):array[i];
pre1 = pre2;
res = Math.max(res,pre2);
}
return res;
}//思路：
//第一个是 1，接下来可以是 1 * 2 , 1 * 3 , 1 * 5，此时最小的显然是 2
//第二个是 2，接下来可以是 2 * 2 , 2 * 3 , 2 * 5，此时就要把这次得到的三个 4,6,10 和上一次剩下的两个3,5 比较大小，找出最小的，即 3
//第三个是 3，接下来可以是 3 * 2 , 3 * 3 , 3 * 5
//...
public int GetUglyNumber_Solution(int index) {
if(index<=1){
return index;
}
int[] dp = new int[index+1];
dp[1] = 1;
int i2 = 1, i3 = 1, i5 = 1;
for(int i=2;i<=index;i++){
int next2=dp[i2]*2;
int next3=dp[i3]*3;
int next5=dp[i5]*5;
dp[i] = min3(next2,next3,next5);
if(dp[i]==next2){
i2++;
}
if(dp[i]==next3){
i3++;
}
if(dp[i]==next5){
i5++;
}
}
return dp[index];
}
private int min3(int a,int b,int c){
int tmp = a<b?a:b;
return (tmp<c)?tmp:c;
}//思路：
//动态规划
//dp[i] 表示将 i 分割成几个整数的最大成乘积和
public int integerBreak(int n) {
if(n==1){
return 0;
}
//dp[i] 表示将 i 分割成几个整数的最大成乘积和
int[] dp = new int[n+1];
dp[1] = 0;
dp[2] = 1;
for(int i=3;i<=n;i++){
for(int j=1;j<i;j++){
dp[i] = max3(dp[i],j*(i-j),j*dp[i-j]);
}
}
return dp[n];
}
private int max3(int a,int b,int c){
int tmp=a>b?a:b;
return tmp>c?tmp:c;
}
@Test
public void test(){
int n=10;
System.out.println(integerBreak(n));
}public int getMost(int[][] board) {
int m=board.length;
int n=board[0].length;
//dp[i][j] 到 board 位置的最大价值
int[][] dp=new int[m][n];
dp[0][0]=board[0][0];
for(int j=1;j<n;j++){
dp[0][j] = dp[0][j-1] + board[0][j];
}
for(int i=1;i<m;i++){
dp[i][0] = dp[i-1][0] + board[i][0];
}
for(int i=1;i<m;i++){
for(int j=1;j<n;j++){
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1])+board[i][j];
}
}
return dp[m-1][n-1];
}扔 n 个骰子，向上面的数字之和为 S。给定 n，请列出所有可能的 S 值及其相应的概率。
举例
举例 1：
输入：n = 1
输出：[[1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]
解释：掷一次骰子，向上的数字和可能为1,2,3,4,5,6，出现的概率均为 0.17。
举例 2：
输入：n = 2
输出：[[2,0.03],[3,0.06],[4,0.08],[5,0.11],[6,0.14],[7,0.17],[8,0.14],[9,0.11],[10,0.08],[11,0.06],[12,0.03]]
解释：掷两次骰子，向上的数字和可能在[2,12]，出现的概率是不同的。
//思路：
//dp[i][j] 表示扔 i 个骰子，向上面的数字之和为 j 出现的次数
public List<Map.Entry<Integer, Double>> dicesSum(int n) {
final int faces = 6;
final int num = faces*n; //n 个骰子向上的数字和的最大值
// dp[i][j] 表示扔 i 个骰子，向上面的数字之和为 j 出现的次数
long[][] dp=new long[faces+1][num+1];
//只有一个骰子
for(int j=1;j<=faces;j++){
dp[1][j] = 1;
}
//扔 i 个骰子
for(int i=2;i<=n;i++){
for(int j=i;j<=num;j++){
// i 的骰子的数字和最小为 i（和最小的情况，就是这 i 个骰子向上的值都为 1）
for(int k=1;k<=faces && k<=j;k++){
dp[i][j] += dp[i-1][j-k];
}
}
}
final double totalNum = Math.pow(6,n);
//总共有 totalNum 中可能的数字和
//统计频率
Map<Integer,Double> records = new HashMap<>();
for(int j=n;j<=num;j++){
records.put(j,dp[n][j]/totalNum);
}
return new ArrayList<>(records.entrySet());
}//思路：
//动态规划：dp[i] 表示字符串 s 的前 i 个字符解码的个数
//注意：遇到 '0' 字符是不能解码的
public int numDecodings(String s) {
if(s==null || s.length()==0){
return 0;
}
int n =s.length();
int[] dp = new int[n+1];
dp[0]=1; // 没有字符则只有一种解码方式
dp[1]=s.charAt(0)=='0'?0:1; //字符 '0',不能进行解码
for(int i=2;i<=n;i++){
//解码一位字符
int one = Integer.parseInt(s.substring(i-1,i));
if(one!=0){
dp[i] += dp[i-1];
}
if(s.charAt(i-2)=='0'){ ////字符 '0',不能进行解码
continue;
}
int two=Integer.parseInt(s.substring(i-2,i));
if(two<=26){
dp[i] += dp[i-2];
}
}
return dp[n];
}