爬楼梯

文章目錄

1. 1. 题目要求
2. 2. 解题思路
3. 3. code
4. 4. 参考文章

看了一道题挺有意思的。

题目要求

由于第m个台阶上有好吃的薯条，所以薯片现在要爬一段m阶的楼梯.
薯片每步最多能爬k个阶梯，但是每到了第i个台阶，薯片身上的糖果都会掉落ai个，现在问你薯片至少得掉多少糖果才能得到薯条？
输入

多组数据输入，每组数据第一行输入两个数字m(1<m<=1000),k(1<=k<m),接下来有m行，每一行输入ai(0<ai<=1000)，表示第i个台阶会掉落的糖果.
输出

对于每组数据，输出至少要牺牲的糖果数.
样例输入

5 2
1 2 3 4 5
6 2
6 5 4 3 2 1

样例输出

9
9

解题思路

所以我们可以总结出一个公式：
cost[i] = min{cost[i - n], cost[i - n + 1], cost[i - n + 2], ...... cost[i - 1]} + ai

code

package mengyunzhi.com;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Dynamic {
    public Dynamic() {}

    public static void main(String[] args) {
        Dynamic dynamic = new Dynamic();
        //输入数组
        Scanner scanner = new Scanner(System.in);
        System.out.println("输入楼梯的阶数和最多能跳多少个阶梯");
        int stairsOrder = scanner.nextInt();
        int orderNumber = scanner.nextInt();

        //开辟一个int数组用来记录相应的糖果数
        int[] costs = new int[stairsOrder + 1];
        costs[0] = 0;       //小兔子从第0个阶梯开始

        System.out.println("请依次输入楼梯对应的代价");
        for (int i = 1; i <= stairsOrder; i++) {
            costs[i] = scanner.nextInt();
        }

        //开辟一个数组用来记录跳到每个楼梯时牺牲的总的糖果数
        List<Integer> orderCosts = new ArrayList<Integer>();
        //付给初值 第零个台阶没有牺牲糖果
        orderCosts.add(0);

        //开始计算个楼梯时牺牲的总的最小的糖果数
        for (int i = 1; i <= stairsOrder; i++) {
            //算出开始循环的初始值大小
            int startLoopNumber = (i - orderNumber) < 0 ? 0 : (i - orderNumber);

            //获取楼梯自己牺牲的总的最小的糖果数
            Integer stairsOrderCost = dynamic.getMinCost(startLoopNumber, orderCosts) + costs[i];

            //牺牲的总的最小的糖果数赋值给对应的台阶
            orderCosts.add(stairsOrderCost);
        }

        System.out.println("牺牲的总的最小的糖果数是：");
        System.out.println(orderCosts.get(orderCosts.size() - 1));
    }

    public Integer getMinCost(int startLoopNumber, List<Integer> orderCosts) {
        //初始化一个最小值
        Integer minCost = orderCosts.get(startLoopNumber);

        for (int i = startLoopNumber; i < orderCosts.size(); i++) {
            if (minCost > orderCosts.get(i)) {
                minCost = orderCosts.get(i);
            }
        }

        //返回相应的最小的牺牲的糖果数
        return minCost;
    }

}

参考文章

图灵杯 爬楼梯