c++动态规划实例及代码两题

题目1：爬楼梯

题目描述：

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

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

注意：给定 n 将是一个正整数。

示例1:

输入: 2

输出: 2

解释: 有两种方法可以爬到楼顶。

1. 1 步 + 1 步

2. 2 步

示例2:

输入: 3

输出: 3

解释: 有三种方法可以爬到楼顶。

1. 1 步 + 1 步 + 1 步

2. 1 步 + 2 步

3. 2 步 + 1 步

代码实现：

int climbStairs(int n){
    if(n == 1) return 1;
    if(n == 2) return 2;
    int a = 1, b = 2, c;
    for(int i = 3; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

题目2：最长回文子序列

题目描述：

给定一个字符串 s ，找到其中最长的回文子序列，并返回该序列的长度。

可以假设 s 的最大长度为 1000 。

示例1:

输入：

"bbbab"

输出：

4

一个可能的最长回文子序列为 "bbbb" 。

示例2:

输入：

"cbbd"

输出：

2

一个可能的最长回文子序列为 "bb" 。

代码实现：

int longestPalindromeSubseq(char * s){
    int len = strlen(s);
    int dp[len][len];
    for(int i = len - 1; i >= 0; i--) {
        dp[i][i] = 1;
        for(int j = i + 1; j < len; j++) {
            if(s[i] == s[j]) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = fmax(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    return dp[0][len-1];
}