动态规划入门刷题

动态规划入门刷题

题目一

int min(int a,int b) {
    if (a < b) return a;
    return b;
}
int minCostClimbingStairs(int* cost, int costSize) {
    int f[1010];
    //f[0] = cost[0];
    //f[1] = cost[1];
    for (int i = 2;i <= costSize;i++) {
        f[i] = min(f[i-2] + cost[i-2],f[i-1] + cost[i-1]);
    }
    return f[costSize];
}

题目二

int max(int a,int b) {
    if (a <= b) return b;
    return a;
}
int lengthOfLIS(int* nums, int numsSize) {
    int f[2510];
    for (int i = 0;i < numsSize;i++) {
        f[i] = 1;
        for (int j = 0;j < i;j++) {
            if (nums[i] > nums[j]) f[i] = max(f[i],f[j]+1);
        }
    }
    int res = -1e9;
    for (int i = 0;i < numsSize;i++) {
        res = max(res,f[i]);
    }
    return res;
}

题目三

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        int f[10010];
        memset(f,0x3f,sizeof f);
        f[0] = 0;
        for (int i = 1;i <= amount;i++) {
            for (int j = 0;j < n;j++) {
                if (i >= coins[j]) 
                    f[i] = min(f[i],f[i-coins[j]] + 1);
            }
        }
        return f[amount] > 1e9?-1:f[amount];
    }
};

题目四

class Solution {
public:
    int maxSales(vector<int>& sales) {
        int n = sales.size();
        int f[100010];
        f[0] = sales[0];
        for (int i = 1;i < n;i++) {
            f[i] = max(f[i-1] + sales[i],sales[i]);
        }
        int res = sales[0];
        for (int i = 0;i < n;i++) {
            res = max(res,f[i]);
        }
        return res;
    }
};

题目五

const int N = 110;
class Solution {
public:
int mem[N];
    int dfs(int x) {
        if (mem[x]) return mem[x];
        if (x == 0) return 1;
        int res = 0;
        for (int i = 1;i < x;i++) {
            if (x >= i)
                res = max(res,max(i*(x-i),dfs(x-i)*i));
        }
        return mem[x] = res;
    }
    int integerBreak(int n) {
        return dfs(n);
    }
};

int max(int x, int y){
    return x > y ? x : y;
}

int integerBreak(int n) {
    //  dp[i] 表示对数字i进行拆分，得到的最大乘积为dp[i];
    int* dp = (int*) malloc( sizeof(int) * (n + 1) );
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 1;

    for(int i = 3; i <= n; i++){
        //  10 -> 1,9->2,8->3,7->4,6->5,5->6,4->7,3->8,2->9,1
        //  循环过i的一半时，后续的计算都是重复的
        for(int j = 1; j <= i / 2; j++){
            //      (i - j)表示不进行拆分 dp[i - j] 表示对(i - j)进行拆分
            dp[i] = max( dp[i], max(j * (i - j), j * dp[i - j]) );
        }
    }

    return dp[n];
}