Java教程

动态规划例题

本文主要是介绍动态规划例题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

走路

题目描述

有一条很长的数轴,一开始你在0的位置。接下来你要走n步,第i步你可以往右走ai或者bi。
问n步之后,0到m的每个位置,能不能走到?

输入格式

第一行,两个整数n,m。
接下来n行,每行两个整数ai,bi。

输出格式

一行,一共m+1个数,每个数都是0或1表示能否走到,数字之间不用空格隔开。

样例输入
3 10
1 2
2 6
3 3
样例输出
00000011001
思路

输出要求是走到最后一步之后, 可以走到的所有位置,如果最后一步走到了位置i,那么倒数第二步就需要走到i-a或者i-b,所以就考虑动态规划,用布尔数组来表示是否能走到i的位置,而每次转移就是考虑i-a或者i-b能不能走到,依次从后往前推到,这里的思路类似于走楼梯

动态规划代码
#include<iostream>

using namespace std;

const int N = 100010;

int n, m;
bool st[110][N];

int main()
{
    cin >> n >> m;
    st[0][0] = true;
    for ( int i = 1; i <= n; i ++ )
    {
        int a, b;
        cin >> a >> b;
        if (a > b) swap(a, b);
        for ( int j = m; j >= a; j -- )
        {
            st[i][j] |= st[i - 1][j - a];
            if (j >= b) st[i][j] |= st[i - 1][j - b];
        }
    }

    for ( int i = 0; i <= m; i ++ )
    {
        if (st[n][i]) cout << "1";
        else cout << "0";
    }

    return 0;
}

走楼梯变形(最多连续三次走2级台阶)

题目描述

楼梯有 n 阶,上楼可以一步上一阶,也可以一步上二阶。
但你不能连续三步都走两阶,计算走到第n阶共有多少种不同的走法。

输入格式

一行,一个数字,表示n。

输出格式

输出走楼梯的方式总数。

输入样例
6
输出样例
12
思路

n最大100,dfs时间复杂度为O(2^100),铁定tle(亲测)
动态规划思路:二维数组来记录,一维记录当前所在位置,二维记录前面已经有了连续几次2步,题目限制原因,二维只需要考虑0,1,2,所以数组开dp[N][3],因为要用的i-2,所以千万要记得在循环之前把1和2处理出来,然后进行循环即可

这篇关于动态规划例题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!