动态规划

总结：

通过边界出发，通过状态转移方程扩散到整个dp数组。

leetcode第198题--打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例1：

输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例2：

输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

分析：
1.递归：我们要算第i个位置nums[i]的最好情况，有两种可能，选择nums[i]和不选nums[i]。假设opt(i)代表第i个位置的最优解。如果选择了nums[i]就一定不能选nums[i-1]，最优解为nums[i]+opt(i-2)；如果不选nums[i]，最优解为opt(i-1)。

class Solution {
    public int rob(int[] nums) {
        return rec_opt(nums, nums.length - 1);
    }

    public int rec_opt(int[] nums, int i) {
        if (i == 0) {
            return nums[0];
        } else if (i == 1) {
            return Math.max(nums[0], nums[1]);
        } else {
            int A = rec_opt(nums, i - 2) + nums[i];
            int B = rec_opt(nums, i - 1);
            return Math.max(A, B);
        }
    }
}

2.动态规划：使用一个数组来保存每个位置的最优解。

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        if (len == 1) {
            return nums[0];
        }
        int[] opt = new int[len];
        opt[0] = nums[0];
        opt[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < len; i++) {
            int A = opt[i - 2] + nums[i];
            int B = opt[i - 1];
            opt[i] = Math.max(A, B);
        }
        return opt[len - 1];
    }
}

斐波那契数列

求斐波那契数列的第n项
1.递归：

class Solution {
    public int rec_fib(int i) {
        if (i == 1 || i == 2) {
            return 1;
        }
        return rec_fib(i - 2) + rec_fib(i - 1);
    }
}

2.动态规划：

class Solution {
    public int dp_fib(int num) {
        if (num == 1 || num == 2) {
            return 1;
        }
        int[] arr = new int[num];
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i < num; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        return arr[num - 1];
    }
}

走楼梯

有一座高度是n级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法。
这个问题实际上就是斐波那契数列。
1.递归：

class Solution {
    public int rec_getClimbingWays(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        return rec_getClimbingWays(n - 1) + rec_getClimbingWays(n - 2);
    }
}

2.动态规划：

class Solution {
    public int dp_getClimbingWays(int n) {
        if (n < 1) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int[] arr = new int[n];
        arr[0] = 1;
        arr[1] = 2;
        for (int i = 2; i < n; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        return arr[n - 1];
    }
}