算法：递归，贪心，分治，动态规划

def fib1(n: Int):Int = {
    if (n <= 1) n else fib1(n-1)+fib1(n-2)
	//     if (n <= 2) n  定义了递归基，如果小于2的情况终止递归
  // 		 fib1(n-1)+fib1(n-2) 递归调用
}

// 使用数组
def fib2(n: Int):Int = {
  // 不需要递推的情况
  if (n <= 1) return n

  val list = new Array[Int](n+1)
  // 递推基
  list(1) = 1
  for (i <- 2 to n) {
    list(i) = list(i-1) + list(i-2)
  }

  list.last
}

// 使用变量
 def fib3(n: Int):Int = {
   if (n <= 1) return n
   
   var first = 0
   var second = 1
   for (_ <- 2 to n) {
     second = first+second
     first = second-first
   }
   second
 }

def fib1(n: Int):Int = {
    if (n <= 1) n else fib1(n-1)+fib1(n-2)
}
// 时间复杂度：O(2^n)
// 空间复杂度：O(n)

def fib2(n: Int):Int = {
  // 不需要递推的情况
  if (n <= 1) return n

  val list = new Array[Int](n+1)
  // 递推基
  list(1) = 1
  for (i <- 2 to n) {
    list(i) = list(i-1) + list(i-2)
  }

  list.last
}
// 时间复杂度：O(n)
// 空间复杂度：O(n)

def fib3(n: Int):Int = {
  if (n <= 1) return n
  
  var first = 0
  var second = 1
  for (_ <- 2 to n) {
    second = first+second
    first = second-first
  }
  second
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)

object StairDemo {
  def main(args: Array[String]): Unit = {
        for (i <- 1 to 5) {
          println(s"$i - ${stair(i)}")
        }
  }

  /**
   * 楼梯有 n 阶台阶，上楼可以一步上 1 阶，
   * 可以一步上 2 阶，走完 n 阶台阶共有多少种不同的走法?
   * @param n
   * @return
   */
  def stair(n: Int):Int = {
    /**
     * 假设第一次走 1 阶，还剩 n – 1 阶，共 f(n – 1) 种走法
     * 假设第一次走 2 阶，还剩 n – 2 阶，共 f(n – 2)种走法
     * 所以f(n)=f(n-1)+f(n-2)
     * f(1) = 1         1
     * f(2) = (1,1) , 2;     2
     * f(3) = f(1)+f(2);       3
     * f(4) = f(n-1)+f(n-2);     5
     */
    if (n<=2) n else stair(n-1)+stair(n-2)
  }
}

/**
 * 只打印步骤
 * @param n
 * @param a
 * @param b
 * @param c
 */
def moveHanoi(n: Int, a: String, b: String, c: String):Unit = {
  // 将n-1个盘子从A移动到B
  // 将编号为n的盘子从A移动到C
  // 将n-1个盘子从B移动到C
  
  if (n > 1) {
    	moveHanoi(n-1, a, c, b)
     	println(s"move $n from $a to $c")
     	moveHanoi(n-1, b, a, c)
  }
  else {
    	println(s"move $n from $a to $c")
  }
   /**
   * 复杂度分析
   * 时间复杂度:O(2^n)
   * 空间复杂度:O(n)
   **/
}
 /**
 * 打印步骤，并统计步数
 * @param n
 * @param a
 * @param b
 * @param c
 * @param prevCount 初始值，会在递归中累加
 * @return 当前循环的结果
 */
def moveHanoi(n: Int, a: String, b: String, c: String, prevCount: Int): Int = {
  // 将n-1个盘子从A移动到B
  // 将编号为n的盘子从A移动到C
  // 将n-1个盘子从B移动到C
  if (n > 1) {
    val count = moveHanoi(n-1, a, c, b, prevCount) + 1
     println(s"$count : move $n from $a to $c")
     moveHanoi(n-1, b, a, c, count)
  }
  else {
    val count = prevCount+1
     println(s"$count : move $n from $a to $c")
     count
  }
}

// 使用栈来实现，去掉递归掉用
def moveHanoi2(n: Int, a: String, b: String, c: String): Unit = {
  // 将n-1个盘子从A移动到B
  // 将编号为n的盘子从A移动到C
  // 将n-1个盘子从B移动到C

  // Boolean, Int, String, String, String
  // isPrint, Int, from, middle, to
  val stack = new mutable.ArrayStack[(Boolean, Int, String, String, String)]()

  /**
   * 使用一个stack来存需要处理的状态，遇到print就打印，遇到其他就展开后重新放回
   */
  if (n > 1) {
    stack.push((false, n-1, b, a, c))
    stack.push((true, n, a, b, c))
    stack.push((false, n-1, a, c, b))
  } else {
    stack.push((true, n, a, b, c))
  }

  while (stack.nonEmpty) {
    val (isPrint, nn, from, middle, to) = stack.pop()
    if (isPrint) {
      println(s"move $nn from $from to $to")
    } else if (nn > 1) {
      stack.push((false, nn-1, middle, from, to))
      stack.push((true, nn, from, middle, to))
      stack.push((false, nn-1, from, to, middle))
    } else {
      stack.push((true, nn, from, middle, to))
    }
  }
}

/**
1、选择重量为 2 的古董，剩重量 28 
2、选择重量为 3 的古董，剩重量 25 
3、选择重量为 4 的古董，剩重量 21 
4、选择重量为 5 的古董，剩重量 16 
5、选择重量为 7 的古董，剩重量 9
结论:按照以上顺序装载货物，并最多装载5件古董!!
*/
def piratePackage():Int = {
  val capacity = 30
  var goods = List(3,5,4,10,7,14,2,11)
  // 按照重量升序
  goods = goods.sorted

  var res = capacity
  var index = 0
  while (res > goods(index)) {
    res -= goods(index)
    index+=1
  }
  index
}

/**
 * 零钱兑换
 * 假设有 25 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少?
 */
def getCoins(money: Int, faces: List[Int]): Unit = {
  val total = money
  val sortedFaces = faces.sorted.reverse

  var count = 0
  var res = total
  var index = 0
  // 假设肯定能兑换成功
  while (res != 0) {
    // 如果可以兑换就兑换，不然就换小面额，继续循环
    if (res >= sortedFaces(index)) {
      res -= sortedFaces(index)
      count+=1
      println(sortedFaces(index))
    } else {
      index+=1
    }
  }

  println(s"coin count: $count")
}

case class Item(weight: Double, value: Double) {
  val dense:Double = value/weight

  override def toString: String = s"item($weight, $value, $dense)"
}
object PackSackDemo {
  def main(args: Array[String]): Unit = {
    val items = List(
      Item(35, 10),
      Item(30, 40),
      Item(60, 30),
      Item(50, 50),
      Item(40, 35),
      Item(10, 40),
      Item(25, 30)
    )

    println("value priority")
    packSackMethod[Double](items, e=>{-e.value})
    println()
    println("weight priority")
    packSackMethod(items, e=>{e.weight})
    println()
    println("dense priority")
    packSackMethod(items, e=>{-e.dense})

    /**
     * value priority
     * selected items List(item(50.0, 50.0, 1.0), item(30.0, 40.0, 1.3333333333333333), item(10.0, 40.0, 4.0), item(40.0, 35.0, 0.875))
     * total value : 165.0
     * res : 20
     *
     * weight priority
     * selected items List(item(10.0, 40.0, 4.0), item(25.0, 30.0, 1.2), item(30.0, 40.0, 1.3333333333333333), item(35.0, 10.0, 0.2857142857142857), item(40.0, 35.0, 0.875))
     * total value : 155.0
     * res : 10
     *
     * dense priority
     * selected items List(item(10.0, 40.0, 4.0), item(30.0, 40.0, 1.3333333333333333), item(25.0, 30.0, 1.2), item(50.0, 50.0, 1.0), item(35.0, 10.0, 0.2857142857142857))
     * total value : 170.0
     * res : 0
     */
  }

  /**
   * 根据排序选择器进行排序，并从左到右开始装包
   * @param items 所有物品
   * @param comp  排序选择器
   * @tparam B double
   */
    //<:Double Double 及其子类
    //>:Double Double 的父类
  def packSackMethod[B<:Double](items: List[Item], comp: Item=>B): Unit = {
    implicit val ord = new Ordering[B] {
      override def compare(x: B, y: B): Int = x.compareTo(y)
    }

    val capacity = 150  //total
    var res = capacity    //current capacity
    val sortedItems = items.sortBy(comp)

    // cache selected items
    val arrayBuffer = new ArrayBuffer[Item]()
    for (it <- sortedItems) {
        if (it.weight.intValue() <= res) {
          res -= it.weight.intValue()
          arrayBuffer += it
        }
    }

    println(s"selected items ${arrayBuffer.toList}")
    println(s"total value : ${arrayBuffer.map(_.value).sum}")
    println(s"res : $res")
  }
}

//递归(自顶向下，出现了重叠子问题)
def coinChange1(n: Int):Int = {
  // 边界状态
  if (n < 1) return Int.MaxValue
  // 设定初始状态 
  if(List(1, 5, 20, 25).contains(n)) return 1
	
  // 状态转移方程
  List(
    coinChange1(n-1),
    coinChange1(n-5),
    coinChange1(n-20),
    coinChange1(n-25)
  ).min + 1
}

//  递推(自底向上，循环)
def coinChange2(n: Int):Int = {
  if (n < 1) return Int.MaxValue
  if(List(1, 5, 20, 25).contains(n)) return 1

  val dp = Array.fill(n+1)(Int.MaxValue)
  dp(1) = 1
  dp(5) = 1
  dp(20) = 1
  dp(25) = 1

  for (i <- 1 to n) {
    if (i > 25) {
      dp(i) = List(dp(i-1), dp(i-5), dp(i-20), dp(i-25)).min+1
    } else if (i > 20) {
      dp(i) = List(dp(i-1), dp(i-5), dp(i-20)).min+1
    } else if (i > 5) {
      dp(i) = List(dp(i-1), dp(i-5)).min+1
    } else if (i > 1) {
      dp(i) = dp(i-1)+1
    }
  }
  dp(n)
}

/**
* 动态规划实现零钱兑换
* @param amount 需要兑换的总额
* @param coins 币的类型
* @return 最小币数，如果不存在就返回-1
*/
def coinChange4(amount: Int, coins: List[Int]):Int = {
  if (amount < 1 || coins == null || coins.isEmpty) return -1

  val dp = Array.fill(amount+1)(0)

  for (i <- 1 to amount) {
    var min = Int.MaxValue

    coins.foreach { face =>
      if (i >= face && dp(i-face) >= 0) {
        min = Math.min(dp(i-face), min)
      }
    }

    if (min == Int.MaxValue) {
      dp(i) = -1
    } else {
      dp(i) = min+1
    }
  }
  dp(amount)
}

def maxSubSequence2(list: List[Int]): Int = {
  /**
   * dp(i) 是以 nums[i] 结尾的最大连续子序列和(nums是整个序列)
   * dp(0) = nums[0]
   * 如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
   * 如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]
   *
   * dp(i) = 最大连续子序列和是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)
   */

  if (list == null || list.isEmpty) return 0

  val dp = new Array[Int](list.size)
  dp(0) = list.head

  for (i <- 1 until list.size) {
    dp(i) = list(i) + (if(dp(i-1)<=0) 0 else dp(i-1))
  }

  dp.max
}

// 使用变量代替数组
def maxSubSequence3(list: List[Int]): Int = {
  /**
   * dp(i) 是以 nums[i] 结尾的最大连续子序列和(nums是整个序列)
   * dp(0) = nums[0]
   * 如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
   * 如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]
   *
   * dp(i) = 最大连续子序列和是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)
   */

  if (list == null || list.isEmpty) return 0

  var lastSum = list.head
  var max = lastSum
  for (i <- 1 until list.size) {
    lastSum = list(i) + (if(lastSum<=0) 0 else lastSum)
    max = Math.max(max, lastSum)
  }

  max
}

// 二维数组实现
def commonNumsSubsequence2(list1: List[Int], list2: List[Int]):Unit = {
  /**
   * 1. 状态函数
   * dp(i)(j) 表示list1的前i个元素 和 list2的前j个元素的最长子序列长度
   *
   * 2. 初始状态
   * dp(i)(0) = 0
   * dp(0)(j) = 0
   *
   * 3. 状态转移函数
   * 假设 list1[i – 1] = list2[j – 1]，那么 dp(i, j) = dp(i – 1, j – 1) + 1
   * 假设 list1[i – 1] ≠ list2[j – 1]，那么 dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }
   */

  if (list1 == null || list2 == null || list1.isEmpty || list2.isEmpty) return 0

  val dp = Array.ofDim[Int](list1.size+1, list2.size+1)

  for (i <- 1 to list1.size; j <- 1 to list2.size) {
    if (list1(i-1) == list2(j-1)) {
      dp(i)(j) = dp(i-1)(j-1) + 1
    } else {
      dp(i)(j) = Math.max(dp(i-1)(j), dp(i)(j-1))
    }
  }

  dp.last.last
}

// 一维数组实现
def commonNumsSubsequence3(list1: List[Int], list2: List[Int]):Unit = {

  if (list1 == null || list2 == null || list1.isEmpty || list2.isEmpty) return

  val dp = new Array[Int](list2.size+1)

  // 处理list2有重复元素，且和list1相等的场景
  // 方法一
//    for (i <- 1 to list1.size) {
//      println()
//      var isFound = false
//      for (j <- 1 to list2.size) {
//        if (list1(i-1) == list2(j-1) && !isFound) {
//          dp(j) = dp(j-1) + 1
//          isFound = true
//        } else {
//          dp(j) = Math.max(dp(j), dp(j-1))
//        }
//        print(dp(j) + ", ")
//      }
//    }

  // 方法二
  for (i <- 1 to list1.size) {
    println()
    var tmp = 0
    for (j <- 1 to list2.size) {
      //暂存上一次循环左上角的值
      val leftTop = tmp
      tmp = dp(j)
      if (list1(i-1) == list2(j-1)) {
        dp(j) = leftTop + 1
      } else {
        dp(j) = Math.max(dp(j), dp(j-1))
      }
    }
  }

	dp.last
}

case class Item(weight: Int, value: Int) 
val items = List(
      Item(2, 6),
      Item(2, 3),
      Item(6, 5),
      Item(5, 4),
      Item(4, 6)
    )
val capacity = 10

// 使用 I * J 二维数据缓存数据
def packSack1(items: List[Item], capacity: Int):Unit = {
  /**
   * * 定义状态方程
   * dp(i, j) 是 最大承重为 j、有前 i 件物品可选 时的最大总价值，i ∈ [0, n]，j ∈ [0, W]
   *
   * * 初始状态
   * dp(i, 0)、dp(0, j) 初始值均为 0
   *
   * * 状态转移方程
   * dp(i,j)=dp(i-1,j-1)
   * 如果只剩最后一件物品时，有两种情况
   * * 不选择该物品:dp(i,j)=dp(i-1,j)
   * * 选择该物品:dp(i,j)=values[i]+dp(i-1,j-weights[i])
   * dp(i,j)返回的是最大总价值 max(dp(i-1,j),values[i]+dp(i-1,j-weights[i]))
   * 如果 j < weights[i – 1]，那么 dp(i, j) = dp(i – 1, j)
   * 如果 j ≥ weights[i – 1]，那么 dp(i, j) = max { dp(i – 1, j), dp(i – 1, j – weights[i – 1]) + values[i – 1] }
   */

  val dp: Array[Array[Int]] = Array.ofDim[Int](items.size+1, capacity+1)
  for (i <- 1 to items.size; j <- 1 to capacity) {
    val it = items(i-1)
    if (j < it.weight) {
      dp(i)(j) = dp(i-1)(j)
    } else {
      dp(i)(j) = Math.max(dp(i-1)(j), dp(i-1)(j-it.weight)+it.value)
    }
  }

  dp.foreach(e => println(e.toList))
  printSelectItems(items, dp)
}

/**
 * 打印选中的商品
 * @param items  完整的商品列表
 * @param dp  动态规划结果表
 */
def printSelectItems(items: List[Item], dp: Array[Array[Int]]): Unit = {
  var i = dp.length-1
  var j = dp.head.length-1
  val selectedItems = new ArrayBuffer[Item]()
  while (i > 0 && j > 0) {
    if (dp(i)(j) > dp(i-1)(j)) {
      selectedItems += items(i-1)
      j -= items(i-1).weight
    }

    i -= 1
  }
  println("selected items")
  println(selectedItems.reverse.toList)
}

// 优化数据结构； 使用 2 * J 二维数据缓存数据
def packSack2(items: List[Item], capacity: Int):Unit = {

  val dp = Array.ofDim[Int](2, capacity+1)
  for (i <- 1 to items.size) {
    val current = i%2
    val last = 1-current
    val it = items(i-1)
    for (j <- 1 to capacity) {
      if (j < it.weight) {
        dp(current)(j) = dp(last)(j)
      } else {
        dp(current)(j) = Math.max(dp(last)(j), dp(last)(j-it.weight)+it.value)
      }
    }
    println(dp(current).toList)
  }

  println(dp.last.last)
}

// 优化数据结构； 使用 一维数据缓存数据
def packSack3(items: List[Item], capacity: Int):Unit = {
  
  val dp = new Array[Int](capacity+1)
  for (i <- 1 to items.size) {
    val it = items(i-1)
    // WARN: 这里需要逆序，防止数据被覆盖
    for (j <- Range(capacity, it.weight-1, -1)) {
      dp(j) = Math.max(dp(j), dp(j-it.weight)+it.value)
    }
    println(dp.toList)
  }
  
  println(dp.last)
}