每日一题

动态规划入门50题

01递推

剑指 Offer 10- II. 青蛙跳台阶问题

• 定义一个常量用于取模
• 定义数组f[i]代表跳上i级台阶的方案数
• 示例1得知 f[2]=2
• 示例3得知 f[0]=1,所以f[1]= 1
• 初始化f[0]和f[1]都等于1
• 再进行一次遍历，
• 跳上i阶的方案数 = 跳上i-1阶的方案数 + 跳上i-2阶的方案数
• 然后再对方案数进行取模
• 最后返回跳上n阶的方案数

class Solution {
    #define mod 1000000007
    int f[110];
public:
    int numWays(int n) {
        f[0]=f[1]=1;
        for(int i =2;i<=n;++i)
        {
            f[i] = (f[i-1] + f[i-2])% mod;
        }
        return f[n];
    }
};

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
    int f[110];
public:
    int climbStairs(int n) {
        f[0]=f[1]=1;
        for(int i =2;i<=n;++i)
        {
            f[i] = (f[i-1] + f[i-2]);
        }
        return f[n];
    }
};

//这道题和青蛙跳台阶问题差不多，把取模去掉即可

1342. 将数字变成 0 的操作次数

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。 如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

• 首先定义一个常量1000001，并以f[i]代表i变成0的步数
• 显然f[0] = 0，遍历枚举1到num，如果i是奇数，那么他应该是i-1 到 0 的步数 +1，也就是 f[i-1]+1
• 如果i是偶数，那么他应该是i/2 大 0 的 步数 +1，也就是 f[i/2]+1
• 最后返回f[num]

class Solution {
    #define max_n 1000001
    int f[max_n];
public:
    int numberOfSteps(int num) {
        f[0] = 0;
        for(int i =1;i<= num; ++i)
        {
            if(i % 2 == 1)
            {
                f[i] = f[i-1] +1;
            }
            else
            {
                f[i] = f[i/2] +1;
            }
        }
        return f[num];
    }
};

剑指 Offer II 088. 爬楼梯的最少成本

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。

每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。

请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

斐波那契数列（将原求的加和变成取最小值）

• 首先定义一个maxN，表示总共有多少个台阶
• 定义f[i]代表到达i层的最小花费
• 由手可以选择下标从0或者1的元素作为初始阶梯，所以f[0]和f[1]都是0
• 将楼层个数缓存在n中，然后从2遍历到n
• 到达i层的最小花费，成该是到达i-1层的最小花费 + 从它向上爬的花费f[i-1] + cost[i-1]
• 以及到达i-2层的最小花费 + 从它向上爬的花费f[i-2]+cost[i-2]
• 这两者取个小的，最后返回f[n]

class Solution {
    #define maxN 1024
    int f[maxN];
public:
    int minCostClimbingStairs(vector<int>& cost) {
        f[0] = f[1] = 0;
        int n = cost.size();
        for(int i =2;i<=n;++i)
        {
            f[i] = min(f[i-1] + cost[i-1],f[i-2]+cost[i-2]);
        }
        return f[n];
    }
};

746. 使用最小花费爬楼梯

和上题一样

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

class Solution {
    #define maxN 1024
    int f[maxN];
public:
    int minCostClimbingStairs(vector<int>& cost) {
        f[0] = f[1] = 0;
        int n = cost.size();
        for(int i =2;i<=n;++i)
        {
            f[i] = min(f[i-1] + cost[i-1],f[i-2]+cost[i-2]);
        }
        return f[n];
    }
};

线性DP - O(1)状态转移