最小花费爬楼梯

class Solution {
    int f[1100];                                                   // (1)用f[i]代表到达第i层的消耗的最小体力值
public:
    int minCostClimbingStairs(vector& cost) {
        f[0] = 0, f[1] = 0;                                        // (2)初始化
        for(int i = 2; i <= cost.size(); ++i) {
            f[i] = min(f[i-1] + cost[i-1], f[i-2] + cost[i-2]);    // (3)状态转移
        }
        return f[cost.size()];
    }
};

最大的连续子数组,返回其最大和

思路分析:

连续子数组问题,可以考虑前一个元素已经计算出来的状态下一个元素的求解.

class Solution {
    int f[30010];
public:
    int maxSubArray(vector& nums) {
        int maxValue = nums[0];
        f[0] = nums[0];                          // (1)初始值
        for(int i = 1; i < nums.size(); ++i) {
            f[i] = nums[i];
            if(f[i-1] > 0) {
                f[i] += f[i-1];                  // (2)状态转移
            }
            maxValue = max(maxValue, f[i]);      // (3)过程中取最大值
        }
        return maxValue;
    }
};

作为一个专业大盗，要开始执行偷窃任务。房屋按照线性排列，每间房内都藏有一定的现金，影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会报警。给定一个代表每个房屋存放金额的非负整数数组，计算 不触动警报装置 的情况下 ，一夜之内能够偷窃到的最高金额。

思路分析:如果第i个房间被偷,那么第i-1个房间一定不能被偷

class Solution {
    int f[110];
public:
    int rob(vector& nums) {
        f[0] = nums[0];                            
        int ans = f[0];                             // (1)代表第0个房间进行偷窃的最大现金
        for(int i = 1; i < nums.size(); ++i) {
            f[i] = nums[i];                         // (2)这种情况代表第i个房间进行偷窃,并且前面i-1都不进行偷窃
            for(int j = 0; j < i - 1; ++j) {
                f[i] = max(f[i], nums[i] + f[j]);   // (3)根据策略执行状态转移
            } 
            ans = max(f[i], ans);                   // (4)每次取第i个房间作为最后一个偷窃房间所等到的最大现金作为候选值
        }
        return ans;
    }
};

一个机器人位于一个 m × n m imes nm×n 网格的左上角。机器人每次只能 向下 或者 向右 移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？

class Solution {
    int f[110][110];                             // (1)f[i][j] 代表从(1,1)到(i,j)的方案数
public:
    int uniquePaths(int m, int n) {
        for(int i = 1; i <= n; i++) {
            f[1][i] = 1;                         // (2)初始化列数为1的情况
        }
        for(int i = 1; i <= m; ++i) {
            f[i][1] = 1;                         // (3)初始化列数为1的情况
        }

        for(int i = 2; i <= m; ++i) {
            for(int j = 2; j <= n; ++j) {
                f[i][j] = f[i-1][j] + f[i][j-1]; // (4)利用二维递推进行求解
            }
        }
        return f[m][n];
    }
};