DP

01背包问题

/**
 *对于方程的描述
 *1.当物品或者容量某一项为空,装入的最大价值都为0
 *2.当遍历到第i类商品的重量大于给出的容量时,是无法装入第i类商品,沿用上一个过程的装入策略即:w[i] > j v[i][j] = v[i-1] [j]
 *3.当遍历到第i类商品的重量是小于给出的容量时,就可以装入第i类商品,理解v[i-1][j-w[i]]
 *装入前i-1类商品到剩余的空间(容量)-->j-wi,->解释是在剩余空间下i-1中类型商品情况下的选择策略 max{}理解为比较与上一个策略的容 
 *量,要此次策略要采取的..
 */
public class DynamicProgramming {


    /*01背包问题
     * 分别有三个物品 要存放到背包(重量为4)中 计算最大的价值
     * 重量:1 4 3
     * 价值:1500 3000 2000
     * 动态规划例题
     * */
    public static void main(String[] args) {
        int[] hight = new int[]{1, 2, 3};
        int[] value = new int[]{1500, 3000, 2000};
        int n = 4;//背包的容量
        int m = value.length;//物品的个数
        //设置一个二维数组表示总价值 加一表示 物品或者容量为0情况
        int[][] val = new int[m + 1][n + 1];
        for (int i = 0; i < val.length; i++) {
            val[i][0] = 0;
        }
        for (int i = 0; i < val[0].length; i++) {
            val[0][i] = 0;
        }
        for (int i = 1; i < val.length; i++) {
            for (int j = 1; j < val[0].length; j++) {
                if (hight[i - 1] > j) {
                    //采用上一个的策略
                    val[i][j] = val[i - 1][j];
                } else {
                    //对该函数的说明   val[i-1][j-hight[i]] 第i个商品的剩余容量
                    val[i][j] = Math.max(val[i - 1][j], value[i - 1] + val[i - 1][j - hight[i - 1]]);
                    //value[i] 是必定能取到的  后一个[j-hight[i]]剩余的空间,后一个的描述是,只有
                    //[j-hight[i]]空间 遍历到val[i]种类型的选择策略
                    //商品的类型是不断增加的
                    //原来函数的标准式:val[i][j] =  Math.max(val[i-1][j] , value[i] + val[i-1][j-hight[i]])
                }
            }
        }
        //遍历
        for (int i = 0; i < val.length; i++) {
            for (int i1 = 0; i1 < val[0].length; i1++) {
                System.out.print(Integer.toString(val[i][i1]) + " ");
            }
            System.out.println();
        }
    }
}

//优化
public class DynamicProgramming1 {
    /**
     * Created with IntelliJ IDEA.
     * Description:
     * User: tongyongtao
     * Date: 2020-10-12
     * Time: 19:16
     * 重量:1 4 3
     * 价值:1500 3000 2000
     * 优化求出最后结果
     */
    public static void main(String[] args) {
        //存储每种商品的重量
        int[] weight = new int[]{1, 4, 3};
        //存储每种商品的价格
        int[] value = new int[]{1500, 3000, 2000};
        //背包的容量是4
        int n = 4;
        //构建一个二维数组用来表示每次选择的价值
        int[][] val = new int[weight.length + 1][n + 1];

        //初始化val[][0] val[0][];
        for (int i = 0; i < val.length; i++) {
            val[i][0] = 0;
        }
        for (int i = 0; i < val[0].length; i++) {
            val[0][i] = 0;

        }
        //由于第一行和第一列都进行的赋值,所以从1开始遍历
        //假设第i个商品的重量是大于本次的容量的则采取上一次的策略
        //如果是小于本次容量的则进行比较   //上一次的策略和本次可以容纳的策略
        //构建方程 max{val[i-1][j] , value[i] + val[i-1][j - weight[i]] }

        //建一个数组来记录信息
        int[][] path = new int[value.length + 1][n + 1];
        for (int i = 1; i < val.length; i++) {
            //容量每次递增
            for (int j = 1; j < val[0].length; j++) {
                //本次商品种类的重量是大于本次的容量的,选择的策略是上一次的
                //此处索引从1开始的
                if (weight[i - 1] > j) {
                    val[i][j] = val[i - 1][j];
                }
                  /* else {
                        //是可以采用本次商品的,策略是与上一次进行比较
                       val[i][j] = Math.max(val[i-1][j] , value[i-1] +val[i-1][j -weight[i-1]] );
                   }*/
                else if (val[i - 1][j] < value[i - 1] + val[i - 1][j - weight[i - 1]]) {
                    val[i][j] = value[i - 1] + val[i - 1][j - weight[i - 1]];
                    path[i][j] = 1;
                } else {
                    val[i][j] = 1;
                }
            }
        }

        for (int i = 0; i < val.length; i++) {
            for (int j = 0; j < val[0].length; j++) {
                System.out.print(val[i][j]);
            }
            System.out.println();
        }

        //从上往下遍历获取最后一次的背包存储情况
        int i = path.length - 1;
        int j = path[0].length - 1;
        while (i > 0 && j > 0) {
            if (path[i][j] == 1) {
                //索引从一开始
                System.out.printf("%d放入背包", i);
                //背包的容量被占据
                j -= weight[i - 1];

            }
            i--;
        }

    }
}

斐波那契问题

public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(fibonacci(12));
        System.out.println(fibonacci1(12));
        System.out.println(fibonacci2(12));
    }

    public static int fibonacci(int number) {
        //递归实现
        if (number == 1 || number == 2) {
            return 1;
        } else {
            return fibonacci(number - 1) + fibonacci(number - 2);
        }
    }

    //动态规划1
    public static int fibonacci1(int number) {
        //考虑建立一个数组存放所有的状态
        //注意容量和索引的不同
        int[] dp = new int[number];
        //初始化0 ,1
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < number; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[number-1];
    }

    //动态规划,考虑压缩
    public static int fibonacci2(int number) {
        //两个变量接收遍历的值
        int first = 1;
        int second = 1;
        for (int i = 3; i <= number; i++) {
              int tmp = first + second;
              first = second;
              second = tmp;
        }
        return  second;
    }
}

爬楼梯问题

public class ClimbStairs {
    /**
     * Created with IntelliJ IDEA.
     * Description:
     * User: tongyongtao
     * Date: 2020-10-11
     * Time: 20:27
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * f(x)=f(x−1)+f(x−2)
     * 动态规划和递归法的区别: 自下而上 自上而下
     * 注意滚动数组的应用
     */
    public static void main(String[] args) {
        climbStairs(12);
        System.out.println(climbStairs1(12));
        System.out.println(climbStairs2(12));
        System.out.println(climbStairs3(12));
    }

    //滚动数组方法
    public static void climbStairs(int n) {
        //f(0)=1
        int p = 0;
        int q = 0;
        int r = 1;
        for (int i = 0; i < n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        System.out.println(r);
    }

    //动态规划算法
    public static int climbStairs1(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i < dp.length; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];

    }

    //dp的优化
    public static int climbStairs2(int n) {
        int prev = 1;
        int cur = 1;
        for (int i = 2; i < n + 1; i++) {
            //tmp只是一个临时变量,用来存储cur的值,然后赋值给prev
            int tmp = cur;
            cur = prev + cur;
            prev = tmp;
        }
        return cur;


    }

    //递归
    public static int climbStairs3(int ints) {
        if (ints <= 2) {
            return ints;
        }
        return climbStairs3(ints - 1) + climbStairs3(ints - 2);
    }
}

买卖股票的时机I

/**
 * Created with IntelliJ IDEA.
 * Description:
 * Date: 2020-10-13
 * Time: 20:25
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 * 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
 * 注意：你不能在买入股票前卖出股票。
 * 例如: [7,1,5,3,6,4] 输出是5;
 * 说明过程:
 * 7 1 5 3 6 4
 * 0 0 4 4 5 5
 * -7 -1 -1 -1 -1
 */
public class MaxProfit {
    public static void main(String[] args) {
        int[] ints = new int[]{7, 1, 5, 3, 6, 4};
        System.out.println(maxProfit1(ints));
        System.out.println(maxProfit2(ints));
        System.out.println(maxProfit3(ints));
        System.out.println(maxProfit4(ints));
        System.out.println(maxProfit5(ints));
    }

    //方法一 暴力匹配
    public static int maxProfit1(int[] prices) {
        int maxProfit = 0;
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length - 1; j++) {
                int tmp = prices[j] - prices[i];
                if (tmp > maxProfit) maxProfit = tmp;
            }
        }
        return maxProfit;
    }

    //方法二 获取最小值和与最大值的差值
    public static int maxProfit2(int[] prices) {
        int minProfit = Integer.MAX_VALUE;
        int maxProfit = 0; //最大的差值
        for (int i = 0; i < prices.length - 1; i++) {
            if (prices[i] < minProfit) minProfit = prices[i];  //获取最小值
            if (prices[i] - minProfit > maxProfit) maxProfit = prices[i] - minProfit;//获取最大的正差值,先买后卖原则
        }
        return maxProfit;
    }

    //方法三 比较简易的动态规划
    //构建方程 max = {f(x),f(x-1)}//f(x-1)是上一次的策略
    public static int maxProfit3(int[] prices) {
        //最小的值
        int min = prices[0];
        //最大的差值
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            //
            if (prices[i] > min) {
                max = Math.max(max, prices[i] - min);
            } else {
                //因为这里 prices[i]是小于min的 替换
                min = prices[i];
            }
        }
        return max;
    }

    //方法四 较为复杂的动态规划
    public static int maxProfit4(int[] prices) {
        //说明:构建两个数组 sell 和 buy
        //对sell的说明:基于上一次策略 如果在本次策略买入会盈利的多少
        //对buy的说明基于本次策略,买入盈利的多少
        int[] sell = new int[prices.length];
        int[] buy = new int[prices.length];
        //初始化 sell buy
        sell[0] = 0;
        buy[0] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
            buy[i] = Math.max(buy[i - 1], -prices[i]);
        }
        //每次选择的策略是基于上一次的选择策略,如果在比较之后是亏损的,则结果是继承的,
        //sell的原则是 与上一次sell的收益相比 本次卖出的收益与上次买入股票价格的差值(buy的值)
        //buy 的原则是 与上一次策略(股票价格的差值)
        return Math.max(sell[prices.length - 1], buy[prices.length - 1]);
    }


    //方法五 对方法四的优化 滚动法
    public static int maxProfit5(int[] prices) {
        //初始化
        int dp = 0;
        int dp1 = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            //sell
            dp = Math.max(dp, dp1 + prices[i]);
            //buy
            dp1 = Math.max(dp1,-prices[i]);
        }
        return Math.max(dp,dp1);
    }
}

买卖股票的时机II

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: tongyongtao
 * Date: 2020-10-19
 * Time: 20:04
 * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
 * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 */
public class MaxProfit2 {
    public static void main(String[] args) {

    }

    public int maxProfit(int[] prices) {
        if (prices.length == 1 | prices.length == 0) {
            return 0;
        }
        //设置两个中间变量接收区域最大最小值
        int min = 0;
        int max = 0;
        int tmp = 0;
        int num = 0;
        for (int i = 1; i < prices.length; i++) {
            tmp = prices[i];
            if (tmp < prices[i - 1] && tmp < prices[i + 1]) {
                min = tmp;
            }
            if (tmp > prices[i - 1] && tmp > prices[i + 1]) {
                max = tmp;
            }
            num += max - min;
        }
        //特例递增 和 递减

        return num;
    }


    //一次遍历
    public int maxProfit1(int[] prices) {
        int sum = 0;
        for (int i = 0; i < prices.length; i++) {
            //只要小于就买,否则不买
            if (prices[i] < prices[i + 1]) {
                sum += prices[i + 1] - prices[i];
            }
        }
        return sum;
    }

    //峰谷法
    public int maxProfit2(int[] prices) {
        int sum = 0;
        //要获取峰和谷
        int i = 0;
        int min = 0;
        int max = 0;
        while (i < prices.length - 1) {

            while (i < prices.length - 1 && prices[i] >= prices[i + 1])
                i++;
            min = prices[i];
            //获取区域最大
            while (i < prices.length - 1 && prices[i] <= prices[i + 1])
                i++;
            max = prices[i];
            sum += max - min;
        }
        return sum;
    }

    //0表示持有现金 1表示持有股票
    //定义一个二维数组
    // int[][] dp = new int[][]; 第一项表示收益  第二项表示状态
    public int maxProfit3(int[] prices) {
        //对初始状态的定义
        int[][] dp = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            //是否持现金要看当前现金 和股票卖出去的收益比值
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);

        }
        //注意  new int[prices.length][2];  dp[prices.length-1][0];数的区别....经常搞错
        return dp[prices.length - 1][0];
    }

    //同样可使用两个数组 或者滚动数组方法
    public int maxProfit4(int[] prices) {
        //定义持有现金和股票
        //初始化
        int cash = 0;
        int stock = -prices[0];

        int preCash = cash;
        int preStock = stock;
        for (int i = 1; i < prices.length; i++) {
            cash = Math.max(preCash, preStock + prices[i]);
            stock = Math.max(stock, preCash - prices[i]);
            //赋值上一项
            preCash = cash;
            preStock = stock;
        }
        return cash;

    }
    //数组方法
    public int maxProfit5(int[] prices) {
        int[] cash = new int[prices.length];
        int[] stock = new int[prices.length];
        //初始化
        cash[0] = 0;
        stock[0] = -prices[0];
        for (int i =1; i < prices.length; i++) {
             cash[i] = Math.max(cash[i-1] ,stock[i-1] + prices[i]);
             stock[i] = Math.max(stock[i-1],cash[i-1]-prices[i]);
        }
        return cash[prices.length-1];
    }
}

凑零钱问题

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:
 * Date: 2020-11-11
 * Time: 22:16
 * 先看下题目：给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，
 * 每种硬币的数量无限，再给一个总金额 amount，问你最少需要几枚
 * 硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
 * <p>
 * <p>
 * coins 中是可选硬币面值，amount 是目标金额
 * int coinChange(int[] coins, int amount);
 * <p>
 * k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
 */
public class MakeTheChange {
    //较好的说明
    //最后一个硬币是1的话，最少硬币数应该为【组成10的最少硬币数】+ 1枚（1块硬币）
    //最后一个硬币是2的话，最少硬币数应该为【组成9的最少硬币数】+ 1枚（2块硬币）
    //最后一个硬币是5的话，最少硬币数应该为【组成6的最少硬币数】+ 1枚（5块硬币）

    public static void main(String[] args) {
        System.out.println(coinChange(new int[]{1, 2, 5}, 11));
    }

    public static int coinChange(int[] coins, int amount) {
        //首先判断数组的容量和金额大小
        if (coins.length <= 0 || amount < 0) {
            return -1;
        }
        if (amount ==0){return 0;}
        //考虑建立一个数组存放每个状态的值,表示dp[i] 要取出金额为i 需要的金币的最小的数量
        int[] dp = new int[amount + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[0] = 0;
            dp[i] = 99999;
            for (int coin : coins) {
                if (i >= coin) {
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        int result = dp[amount] == 99999 ? -1:dp[amount];
        return result;
    }
}

最长上升子序列

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LengthOfLIS {
    /**
     * Created with IntelliJ IDEA.
     * Description:
     * User:
     * Date: 2020-11-12
     * Time: 21:26
     */
    public static void main(String[] args) {
        ArrayList<Integer> inte = new ArrayList<Integer>();
        inte.add(1);
        inte.add(2);
        inte.add(3);
        inte.add(4);
        inte.add(5);
        inte.add(6);
        inte.add(8);
        inte.forEach(System.out::println);
        //(-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引
        System.out.println(Collections.binarySearch(inte, 7));


    }

    public static int lengthOfLIS(int[] nums) {
        //首先边界条件的确定
        if (nums.length <= 0) {
            return 0;
        }
        //考虑就一个数组用来存放状态值,对数组的余地,dp[i] = number 第多少个数的最长上升子序列
        int[] dp = new int[nums.length];
        //考虑最小的长度为一,初始化数组
        Arrays.fill(dp, 1);
        //怎么确定转移方程,既是我们知道dp[i-1] 怎么求dp[i]
        //我们只要找到前面的子问题中最后一位比dp[i]小的最大子问题即可+1
        //使用一个循环求取所有的状态
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                //这里的判断是求取的关键
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        //数组中最大的状态就是最长的最长上升子序列
        int tmp = 0;
        for (int i = 0; i < nums.length; i++) {
            tmp = Math.max(dp[i], tmp);
        }
        return tmp;
    }

    public static int lengthOfLIS1(int[] nums) {
        //使用二分查找
        //思路建立一个集合,首先存储第一次的数,以及如果某前面的数小于后面的数直接添加到集合中
        List<Integer> list = new ArrayList<>(nums.length);

        for (int num : nums) {
            //集合的长度为0的时候或者前面的数小于后面的数就添加到集合中
            if (list.size() == 0 || list.get(list.size() - 1) < num) {
                list.add(num);
            } else {
                //二分法 binarySearch返回值是第一个大于它的索引
                // (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引
                int i = Collections.binarySearch(list, num);
                //如果i>0 说明本来就存在直接替换即可 ,如果小于取反减去1
                list.set((i < 0) ? -i-1 : i , num);
                 //下面的这种写法通过不了
               // list.set((i > 0) ? i : -i - 1, num);
            }
        }
        
        return list.size();
    }
}

最长回文子串

package Arithmetic.DynamicPlanning

//最长回文子串
object LongestPalindrome {
  def main(args: Array[String]): Unit = {
    println(longestPalindrome("cbbd"))
  }

  def longestPalindrome(s: String): String = {
    val length = s.length
    //特例处理
    if (s.length < 2) return s.charAt(0) + ""
    //定义接收回文的长度和qishiweizhi
    var len = 1
    var first = 0
    //创建二维布尔数组
    var array = Array.ofDim[Boolean](length, length)
    for (i <- 0 until length) {
      array(i)(i) = true
    }
    //对角线必然是true,从1开始,先列->行

    for (j <- 1 until length) {
      for (i <- 0 until j) {
        if (s.charAt(i) != s.charAt(j)) {
          array(i)(j) = false
        }

        else {
           //表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2
           if (j - i  < 3) {
            array(i)(j) = true
          }
          else {
            //如果外面的相等则比较里面的里面的
            array(i)(j) = array(i + 1)(j - 1)
          }
        }

        //获取值
        if (array(i)(j)  && (j - i +1 > len)) {
          len = j - i + 1
          first = i
        }
      }
    }

          s.substring(first,first+len)

  }
}

最大子序和

public class MaxSubArray {
    /*
     * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组
     * （子数组最少包含一个元素），返回其最大和
     *
     *
     * 思想:相加数组中的所有元素,直到遇到一个比这个和还要大的元素,舍弃这个和,重新求和,反复进行
     * */
    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        maxSubArray1(nums);
        maxSubArray2(nums);
    }

    //f(i)=max{f(i−1)+a 转移方程 滚动思想

    public static void maxSubArray1(int[] ints) {
        //索引 0-ints.lenth
        //用来接收和
        if (ints.length==0){return;}
        int sum = 0;
        //最大的值
        int max = ints[0];
        for (int x : ints) {
            //转移方程,如果前面的和小于x,则舍弃前面的所有数
            sum = Math.max(sum + x, x);
            //比较与赋值
            max = Math.max(sum, max);
        }
        System.out.println(max);
    }

    //动态规划
    public static void maxSubArray2(int[] ints) {
        //数组的长度
        int length = ints.length;
        //构建一个dp存放以ints[i]为结尾最大子序
        int[] dp = new int[length];
        dp[0] = ints[0];
        for (int i = 1; i < length; i++) {
            // 取当前元素的值 和 当前元素的值加上一次结果的值中最大数
            dp[i] = Math.max(ints[i], dp[i - 1] + ints[i]);
        }
        //遍历dp数据获取最大的最大子序
        int max = 0;
        for (int x : dp) {
            max = Math.max(max, x);
        }
        System.out.println(max);
    }
}

子序列

//转移方程的推导
//当最后两个字符相等的时，即 dp[i][j] = dp[i - 1][j - 1]
//当 s 的长度为 i - 1,t 的长度为 j - 1 时
//若 s 为   t 的子序列，则当 s 的长度为 i ,t 的长度为 j 时，s 也为   t 的子序列
//若 s 不为 t 的子序列，则当 s 的长度为 i ,t 的长度为 j 时，s 也不为 t 的子序列
//当最后两个字符串不相等时，即 dp[i][j] = dp[i][j - 1]
//当 s 的长度为 i,t 的长度为 j - 1 时
//若 s 为   t 的子序列，则为 t 则加一个字符之后，s 的长度为 i ,t 的长度为 j 时，s 也为   t 的子序列
//若 s 不为 t 的子序列，则为 t 则加一个字符之后，s 的长度为 i ,t 的长度为 j 时，s 也为   t 的子序列

def isSubsequence(s: String, t: String): Boolean = {
    val sl = s.length
    val tl = t.length
    if (sl == 0) return true
    if (sl > tl) return false
    var dp = Array.ofDim[Boolean](sl + 1, tl + 1)
    for (i <- 0 to tl) {
      dp(0)(i) = true
    }
    for (x <- 1 to sl; y <- 1 to tl) {
      if (s.charAt(x - 1) == t.charAt(y - 1)) {
        dp(x)(y) = dp(x - 1)(y - 1)
      }
      else {
        dp(x)(y) = dp(x)(y - 1)
      }
    }
    dp(sl)(tl)
  }

跳跃游戏I

object CanJump {
  def main(args: Array[String]): Unit = {
    println(canJump(Array(3, 2, 1, 0, 4)))
    println(canJump1(Array(3, 2, 1, 0, 4)))
  }

  def canJump(nums: Array[Int]): Boolean = {

    //方法一,从前往后跳
    //思路,某一步能跳的最大步径途中的所有经过的数,取最大的步径
    //设置一个val 接收跳到的最大位置
    var max = 0
    for (i <- 0 until nums.length) {
      if (i > max) {
        return false
      }
      max = Math.max(max, i + nums(i))
    }
    if (max >= nums.length) {
      return true
    }
    true
  }

  def canJump1(nums: Array[Int]): Boolean = {
    //从后往前
    //思路,如果倒数第二个能到达,则能到达
        //表示数组的最后一个元素
    var last = nums.length - 1
    //逆向遍历,如果不存在就继续遍历
     for (i <- (0 to  nums.length-2).reverse ){
           println(i)
           if ((i + nums(i)>last)){
               last = i
           }
     }
      return  last ==0
  }
}

使用最小花费爬楼梯

def minCostClimbingStairs(cost: Array[Int]): Int = {
  //踏上topi 有两种选择 踏上前 min(i-2) + cost(i-1) 和 min(i-1) + cost(i)
  //考虑一个数组存放中间值
  val array = new Array[Int](cost.length)
  array(0) = 0
  array(1) = cost(1).min(cost(0))
  for (i <- 2 until cost.length) {
    array(i) = (array(i - 2) + cost(i - 1)).min((array(i - 1) + cost(i)))
  }
  array(cost.length - 1)
}

def minCostClimbingStairs1(cost: Array[Int]): Int = {
   //简单优化
   var min1 = 0
   var min2 = cost(0).min(cost(1))
   var minresult = 0
   for (i <- 2 until cost.length) {
     minresult = Math.min(min1 + cost(i - 1), min2 + cost(i))
     min1 = min2
     min2 = minresult
   }
   minresult
 }

//与上一种方法的区别在于是否包含i
def minCostClimbingStairs2(cost: Array[Int]): Int = {
  //要到达topi 则要比较 minresult(i-1) + cost(i) 和 minresult(i-2) + cost (i)
  var min1 = 0
  var min2 = 0
  var result = 0
  cost.foreach(
    data => {
      result = min1.min(min2) + data
      min1 = min2
      min2 = result
    }
  )
   min1.min(min2)
}

class Solution {
    public int minCostClimbingStairs3(int[] cost) {
        int[] dp = new int[cost.length];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 2], dp[i - 1]) + cost[i];
        }
        return Math.min(dp[cost.length - 2], dp[cost.length - 1]);
    }
}

打家劫舍

//你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影
// 响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
//给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
//输入：[2,7,9,3,1]
//输出：12
//解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
//     偷窃到的最高金额 = 2 + 9 + 1 = 12 。
object Rob {
  def main(args: Array[String]): Unit = {

  }
  def rob(nums: Array[Int]): Int = {
       if(nums == null ||   nums.length ==0) return  0
       if (nums.length==1)  return    nums(0)
       var a :Int = nums(0)
       var b :Int = Math.max(nums(0),nums(1))

          for (i <- 2  until  nums.length){
                  var tmp :Int =  b
                  b  = Math.max(a+nums(i),b)
                  a = tmp
          }
           b
  }
}

public class Rob1 {
    public static void main(String[] args) {
        int[] ints = new int[]{1, 2, 37};
        System.out.println(new Rob1().rob1(ints));
    }

    //数组方法
    public int rob(int[] nums) {
        //要判断是否为null 和 为 0
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1], nums[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[nums.length - 1];
    }

    //使用滚动数组方法
    public int rob1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
         //视为n-1项
        int first = nums[0];
        int second = Math.max(nums[1], nums[0]);
        for (int i = 2; i < nums.length; i++) {
               int  tmp =  second;
               //这是结果
               second = Math.max(first + nums[i],second);
               first = tmp;
        }

        return  second;

    }
}

不同路径

import java.util
//一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
//机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
//问总共有多少条不同的路径？

object UniquePaths {
  def main(args: Array[String]): Unit = {
    println(uniquePaths1(3, 7))
    println(uniquePaths2(3, 7))
  }

  def uniquePaths(m: Int, n: Int): Int = {
    var array = Array.ofDim[Boolean](m, n)
    for (i <- 0 to m - 1) {
      for (j <- 0 to n - 1) {
        array(i)(j) = false
      }
    }
    for (i <- array) {
      println(i.mkString(","))
    }

    1
  }

  def uniquePaths1(m: Int, n: Int): Int = {
    val array = Array.ofDim[Int](m, n)
    for (i <- 0 until m) {
      array(i)(0) = 1
    }
    for (i <- 0 until n) {
      array(0)(i) = 1
    }
    for (i <- 1 until m) {
      for (j <- 1 until n) {
        array(i)(j) = array(i - 1)(j) + array(i)(j - 1)
      }
    }
    array(m - 1)(n - 1)
  }

  def uniquePaths2(m: Int, n: Int): Int = {
    var array = new Array[Int](n)
    util.Arrays.fill(array, 1)
    for (i <- 1 until m) {
      for (j <- 1 until n) {
        array(j) += array(j - 1)
      }
    }
    array(n - 1)
  }

}