【算法】动态规划

持续更新中…

1、常规动态规划

Fibonacci数列

Fibonacci数列

动态规划做法：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<int> dp(sqrt(n));
    dp[0] = 0, dp[1] = 1;
    int s1 = 0, s2 = 0;
    for (int i = 2; i < n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
        if (dp[i] > n)
        {
            while (dp[i] != n)
            {
                s1++;
                dp[i]--;
            }
            while (dp[i - 1] != n)
            {
                s2++;
                dp[i - 1]++;
            }
            break;
        }
    }
    cout << min(s1, s2) << endl;
    return 0;
}

滚动数组做法：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    int a = 0, b = 1, c = 1;
    while (true)
    {
        if (c >= n) break;
        a = b;
        b = c;
        c = a + b; // 这几个顺序不能乱，c = a + b最后算
    }  
    cout << min((c - n), (n - b)) << endl;
    return 0;
}

杨辉三角

杨辉三角

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<vector<int>> v(n, vector<int>(n, 1));
    for (int y = 0; y < n; y++)
    {
        for (int x = 0; x < y + 1; x++)
        {
            if (y > 1)
            {
                if (x > 0 && x < y)
                    v[x][y] = v[x][y - 1] + v[x - 1][y - 1];
            }
            printf("%5d", v[x][y]);
        }
        cout << endl;
    }
    return 0;
}

最小花费爬楼梯

NC296 最小花费爬楼梯

• 注意要爬到楼顶，最后一个数之后才是楼顶，所以dp数组要多开一个空间。

下面的dp[i]表示到第i个台阶所花费的钱。 因此到楼顶就是dp[n]。

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

下面的dp[i]表示从第i个台阶到楼顶所花费的钱。

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

孩子们的游戏

• 孩子们的游戏

经典的约瑟夫环问题，也可以利用链表和数组模拟来做。本题通过动态规划可以找到一个规律。

其中 dp[i] 表示 i 个孩子的时候谁拿到了那个礼物。

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        int f = 0; // 第一个孩子拿到礼物的就死他自己
        for (int i = 2; i <= n; i++)
            f = (f + m) % i;
        return f;
    }
};

2、背包问题

3、最长公共子序列

4、最长递增子序列

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~